David M. Howard dmh2000@cwix.com
Sun Microsystems Certified Java Developer
Red-Black Trees are one of the preferred methods of maintaining binary search trees. A red-black tree is searched in the same way an ordinary binary search tree. There is no extra search cost. Approximate balancing is performed during insertion and deletion operations, and the cost is O(lg n) instead of O(n) for a full rebalance after insertion. The following reference has a good explanation of the characteristics of a red-black tree.
A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK. By constraining the way nodes can be colored on any path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced. Each node of the tree now contains the fields color, key, left, right, and p. If a child or the parent of a node does not exist, the corresponding pointer field of the node contains the value NIL. We shall regard these NIL'S as being pointers to external nodes (leaves) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree. A binary search tree is a red-black tree if it satisfies the following red-black properties:
- Every node is either red or black.
- Every leaf (NIL) is black. (dh: NIL leaf nodes are not shown on the animation, assume every terminal node has two NIL leaves)
- If a node is red, then both its children are black.
- Every simple path from a node to a descendant leaf contains the same number of black nodes.
|
David Howard October 1998