Red and Black Trees

The Red-Black Tree (RBT) was invented by Rudolf Bayer in 1972. However, the red and black colors weren’t associated until 1978, when Leonidas J. Guibas and Robert Sedgewick published their paper, “A Dichromatic Framework for Balanced Trees.” The RBT set out to improve upon the insertion and deletion operation of the AVL tree, another balanced binary search tree.

RBTs follow four main rules:

1. Every node is either red or black.
2. The root of the tree is always black
3. If a node is red, then both its children are black.
4. Every path from a node (including root) to any of its descendants’ NULL nodes has the same number of black nodes.

Example:

Insert (16) ->

Delete (25) ->

Insertion Explanation:
1. To find the place to insert takes the height of the tree, or O(log n).
2. To add the node is O(1).
3. To fix possible double reds, a rotation is O(1).
4. Worst case, the double red can cascade all the way to the root. The cascade is proportional to the height of the tree, so the fixin’ takes O(log n), worst case.
5. Therefore, insertion is O(log n).

Deletion Explanation:
1. Finding the node to delete plus finding the left-most right descendant is proportional to the height of the tree, so it is O(log n).
2. The swapping and deletion is O(1).
3. Each individual fix (rotation, etc.) is O(1).
4. In the worst case, a double-black may get passed up to the root. Since each rotation takes constant time, this would be proportional to the height of the tree, and thus is O(log n).
5. Therefore, the worst-case cost of deletion is O(log n).

Repo: https://github.com/znew10/algorithms-midterm

References:

1. Rudolf Bayer (1972). “Symmetric binary B-Trees: Data structure and maintenance algorithms”. Acta Informatica. 1 (4): 290–306
2. Leonidas J. Guibas and Robert Sedgewick (1978). “A Dichromatic Framework for Balanced Trees”. Proceedings of the 19th Annual Symposium on Foundations of Computer Science. pp. 8–21
3. Andersson, Arne (1993–08–11). “Balanced search trees made simple”. In Dehne, Frank; Sack, Jörg-Rüdiger; Santoro, Nicola; Whitesides, Sue (eds.). Algorithms and Data Structures (Proceedings). Lecture Notes in Computer Science. 709. Springer-Verlag Berlin Heidelberg. pp. 60–71.