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.

## Properties

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

- Every node is either red or black
- All
`NIL`

nodes are considered black- A red node does not have a red child
- Every path from a given node to any of its descendant
`NIL`

nodes goes through the same number of black nodes

## 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.

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

*Wikipedia*, July. https://en.wikipedia.org/w/index.php?title=Red%E2%80%93black_tree&oldid=1100748306.