[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/red_black_tree.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "red-black tree" type: concept related: [Binary Search Tree] source: https://www.jemoka.com/posts/kbhred_black_tree/ confidence: high status: active --- constituents a binary search tree requirements every node is colored red or black root node is black NIL children are black node children of red nodes are black nodes for all nodes x, all parts from x to NIL have the same number of black nodes for all nodes, all paths from x to nil have the same number of black nodes additional information intuition black nodes are balanced — “every path from root to nil would have the same black nodes” red nodes are “spread out” so they don’t mess things up too much Its weaker than perfect balance, and its not too weak to break things. rotation you can “lift” one node as the root of the tree then we have to slide redundant nodes down such that nodes have exactly <= 2 children proxy We need a proxy for balance such that we can claim a tree is “approximately balanced”. proof The high of a red-black tree with \(n\) non-nil nodes is at most \(2 \log \qty(n+1)\) Let’s define \(b\qty(x)\) to be the number of black nodes in any path from \(x\) to NIL, excluding \(x\), including NIL. Claim: there are at least \(2^{b\qty(x)} -1\) non NIL nodes in the subtree underneath \(x\), including \(x\). IH: claim is true for all nodes \(x\) of height at most \(h\). So now consider the root. Our IH from above gives \(n \geq 2^{b\qty(\text{root})} -1\). Now, notice that \(b\qty(\text{root}) \geq \frac{\text{height}}{2}\), because at most every other node is red, and hence \(2b\qty(\text{root})\) must be greater than or equal to height. This gives: \begin{equation} n \geq 2^{\frac{\text{height}}{2}} -1 \implies \text{height} \leq 2 \log \qty(n+1) \end{equation} This gives that the tree is approximately balanced.