(See related pages)
|
|
|
| A red-black tree is a binary search tree in which the root element is colored black,
every other element is colored either red or black, and for which the following two
rules hold:
1. Red Rule: if an element is colored red, none of its children can be colored red. 2. Path Rule: the number of black elements is the same in all paths from the root to elements with one child or with no children. The height of a red-black tree is always logarithmic in n, the number of elements in the tree. The Java Collections Framework implements red-black trees in the TreeMap class. In a TreeMap object each element has a unique key part—by which the element is identified—and a value part, which contains the rest of the element. The elements are stored in a red-black tree in key-ascending order, according to their “natural” order (implementing the Comparable interface) or by the order specified by a usersupplied Comparator object (there is a constructor in which the Comparator object is supplied). For the containsKey, get, put, and remove methods, worstTime(n) is logarithmic in n. The treeSort method is a fast sort based on a TreeMap object. A TreeSet is a Collection in which duplicate elements are not allowed and in which the elements are stored in order (according to the Comparable ordering or a user-supplied Comparator). The TreeSet class is implemented in the Java Collections Framework as a TreeMap in which each element has the same dummy valuepart. For the contains, add, and remove methods, worstTime(n) is logarithmic in n. |