Red-black tree

ID: 019be402-8bef-48f3-afbf-6441010dd8cf

ROAM_REFS: [cite:@RedblackTree2022]

LAST_MODIFIED: [2024-02-15 Thu 06:08]

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

ID: 265af7fb-38f7-4e99-8f49-07b7461ef5de

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

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

Implementation

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

def binary_tree_insert(value):
    pass

def insert_fix(inserted_node):
    pass

Deletion

Cases

Bibliography

Backlinks

• Self-balancing binary search tree