Encyclopedia > Red-Black tree

  Article Content

Red-Black tree

A Red-Black tree is a type of balanced binary tree, a data structure used in computer science. It was invented in 1972 by Rudolf Bayer[?] who called them "symmetric binary B-trees".

A Red-Black tree is a binary tree where each node have color as an extra attribute, either red or black. By constraining the coloring of the nodes it is ensured that the longest path from the root to a leaf is no longer than twice the length of the shortest path. This means that the tree is balanced. A Red-Black tree must satisfy these properties:

  • The root is black
  • All leaves are black.
  • Red nodes can only have black children.
  • All paths from a node to its leaves contain the same number of black nodes.

When nodes are removed or deleted, the tree must be transformed to keep these properties. This is done by repainting or rotating nodes.

A newly added node should be red by default. If the parent node is black, the tree is still valid. If both the parent node is red, and there exists a red uncle node, then they should be repainted black, and the grandparent node should be repainted red. (It may be necessary to continue repainting up to the root.) Otherwise, rotations are necessary. If the root ends up red, it should be repainted black.

See also: AVL tree, B-tree

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Shoreham, New York

... of age or older. The average household size is 2.88 and the average family size is 3.11. In the village the population is spread out with 27.6% under the age of 18, 6.2% ...

This page was created in 68 ms