RedBlackTree

约 195 个字 预计阅读时间 1 分钟

Definition

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. if a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Property

一个有 \(N\) 个内部节点（不包括叶子结点）的红黑树，其高度最大为 \(2\log_2 (N+1)\)。

the proof of the property

关于黑高和点数的关系。

1. 首先我们有 \(N \geq 2^{bh}-1\)，也就是 \(bh \leq \log_2 (N+1)\)；
2. 然后显然有 \(2 bh(Tree) >= h(Tree)\)

B+ Tree

更一般地来说，B+ 树满足如下性质：

property of B+ Tree

@cy's PPT

1. The root is either a leaf or has between \(2\) and \(M\) children.
2. All nonleaf nodes (except the root) have between \(\lceil M/2 \rceil\) and M children.
3. All leaves are at the same depth.

Assume each nonroot leaf also has between \(\lceil M/2 \rceil\) and \(M\) children.