0.2.4 Red-Black Trees
Binary search trees
are superior to array-based binary searches because they make
addition and deletion from the data storage structure less costly.
However, as discussed in the binary search tree section, it is
possible to create degenerate trees
which suffer from poor search operation performance. These degenerate
trees look like linked lists; each node in the tree has one child
causing the data lookup to be a linear operation. As said in the
binary search tree section, the optimal shape for a search tree data
structure is a balanced tree
or one in which each node in the tree has either two or no child
nodes.
The red-black tree algorithm is a method for maintaining balanced
search trees. The algorithm is actually based on AVL trees which are
data structures that were proposed by G. M. Adel'son-Vel'skii and
E. M. Landis. As you might expect, in a red-black tree every node is
given a color - either red or black. Further, in a red-black tree,
unlike in a binary search tree, data is only stored at the leaf
nodes
of the data structure. Internal nodes
are used as guides or reference points.
A node's color is determined by the following heuristics:
- 1.
- All leaf nodes in a red-black tree must be black.
- 2.
- On any path from the root of the tree to a leaf, two consecutive
red colored nodes are not allowed.
- 3.
- All the leaves of the tree must have the same number of black
nodes on the path from the root of the red-black tree to that leaf.
This number of black nodes is called the black depth
of a node.
|
Search