In computer science, a red–black tree is a kind of Self-balancing binary search tree. Each Vertex stores an extra bit representing “color” (“red” or “black”), used to ensure that the Tree remains balanced during insertions and deletions.

When the tree is modified, the new tree is rearranged [Tree rotation] and “repainted” to restore the coloring properties that constrain how unbalanced the tree can become in the worst case. The properties are designed such that this rearranging and recoloring can be performed efficiently.

(“Red-Black Tree” 2022)

Properties

  1. Every node is either red or black
  2. All NIL nodes are considered black
  3. A red node does not have a red child
  4. Every path from a given node to any of its descendant NIL nodes goes through the same number of black nodes

(“Red-Black Tree” 2022)

Space Complexity

\(\bigo{n}\)

Time Complexity

Function Amortized Worse case
Search \(\bigo{\log n}\) \(\bigo{\log n}\)
Insert \(\bigo{1}\) \(\bigo{\log n}\)
Delete \(\bigo{1}\) \(\bigo{\log n}\)

Algorithm

Insertion

Insertion begins by placing the new (non-NIL) node, say N, at the position in the binary search tree of a NIL node whose in-order predecessor’s key compares less than the new node’s key, which in turn compares less than the key of its in-order successor. (Frequently, this positioning is the result of a search within the tree immediately preceding the insert operation and consists of a node P together with a direction dir with P->child[dir] == NIL.) The newly inserted node is temporarily colored red so that all paths contain the same number of black nodes as before.

(“Red-Black Tree” 2022)

Insertion may invalidate one or more Properties of the Red-black tree.

Cases

  • 1: Parent is black

    All Properties hold. No further work is necessary.

  • 2: Parent and uncle are both red

    The third Properties

Implementation

class red_black_tree():
    def insert(key, value):
        inserted_node = binary_tree_insert(key, value)
        insert_fix(inserted_node)

    def binary_tree_insert(value):
        pass

    def insert_fix(inserted_node):
        pass

Deletion

Cases

References