Left Leaning Red-Black Tree
Left Leaning Red Black Tree
A red–black tree is a kind of self-balancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently that search, insertion and deletion operations are all performed in O(log n) time. Left leaning red-black tree is a variant of red-black tree that is designed to be easier to implement.
<!-- HeadMark -->
Left leaning red-black tree is binary search tree that satisfies the following properties:
- Each node is either red or black.
- The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
- All leaves (NIL) are black.
- If a node is red, then both its children are black.
- Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes.
- (Left leaning means that push the red color to the left when possible).
Simplified implementation from gollrb.
Demostration<!-- EndMark -->