wire / wire-format / red-black-tree
A red-black tree is a self-balancing binary search tree. Each node is red or black. Properties: (1) Every node is red or black. (2) Root is black. (3) Every leaf (NIL) is black. (4) If a node is red, both children are black (no two reds in a row). (5) Every path from root to leaf has the same number of black nodes (black-height). These properties ensure the tree is approximately balanced: height <= 2*log2(n+1).
aka: Red-black tree
spec: Red-black tree
A red-black tree is a self-balancing binary search tree. Each node is red or black. Properties: (1) Every node is red or black. (2) Root is black. (3) Every leaf (NIL) is black. (4) If a node is red, both children are black (no two reds in a row). (5) Every path from root to leaf has the same number of black nodes (black-height). These properties ensure the tree is approximately balanced: height <= 2*log2(n+1).
| field | size | meaning |
|---|---|---|
| Color | 1 bit | Red or black. |
| Property 1 | invariant | Every node is red or black. |
| Property 2 | invariant | Root is black. |
| Property 3 | invariant | Every leaf (NIL) is black. |
| Property 4 | invariant | If a node is red, both children are black (no two consecutive reds). |
| Property 5 | invariant | Every path from root to leaf has the same number of black nodes. |
| Height bound | O(log n) | Height <= 2*log2(n+1). Ensures O(log n) search/insert/delete. |
| Rotation | operation | Left/right rotations rebalance the tree after insert/delete. O(1) per rotation. |
example:
00 00 00 00
Red-black tree (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/red-black-tree
or /wire-format/red-black-tree.json