红黑树
平衡性
红黑树是一种平衡树，它首先满足二叉排序树的所有性质。我们在它的每个节点上定义一个颜色——红色或黑色。颜色必须满足以下三个性质：
- 根节点是黑色的。
- 红色节点的儿子必须是黑色的。（等价于：不能出现两个连续的红色节点）
- 对于任意一个节点\(u\)，在它的子树中，从它出发到所有空节点的路径上经过的黑色节点个数全部相等。其中空节点定义为“叶节点的子节点”以及“只有一个子节点的节点的另一个子节点”。
我们对颜色没有其它要求了。由此可见，红黑树的平衡并不是严格的平衡，但它把不平衡的范围限制在了两倍以内——它严格要求黑色节点的数量保持平衡，并通过限制“不能出现连续红色节点”使得深度之差不会超过两倍。考虑根节点，根据性质3从它出发到所有空节点经过的黑节点个数相等，设经过\(M\)个黑节点，那么最长的一条链也不能超过\(2M\)，因为红色节点必须间隔地出现，不然就会出现连续的红色节点了。因此树的高度不能超过\(2M\)，因此总的节点个数就不能超过\(2^{2M}\)。而一条链的长度还必须至少是\(M\)，因此总的节点个数至少得有\(2^M\)。这样我们就得到了由\(M\)确定的节点个数的一个取值范围，\(2^M \leq |V| \leq 2^{2M}\)，解得\(\dfrac{1}{2}\log |V| \leq M \log |V|\)。同时树的高度\(M \leq h \leq 2M\)。由此代入得\(\dfrac{1}{2}\log |V| \leq h \leq 2\log|V|\)。所以\(h = O(\log |V|)\)。