wire / wire-format / red-black-tree

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

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Red-black tree

wire format

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

fieldsizemeaning
Color1 bitRed or black.
Property 1invariantEvery node is red or black.
Property 2invariantRoot is black.
Property 3invariantEvery leaf (NIL) is black.
Property 4invariantIf a node is red, both children are black (no two consecutive reds).
Property 5invariantEvery path from root to leaf has the same number of black nodes.
Height boundO(log n)Height <= 2*log2(n+1). Ensures O(log n) search/insert/delete.
RotationoperationLeft/right rotations rebalance the tree after insert/delete. O(1) per rotation.

example:

00 00 00 00

Red-black tree (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/red-black-tree or /wire-format/red-black-tree.json