博客

在二叉查找树的频繁动态更新过程中，可能会出现树高远大于



l

o

g

2

n

log_2n






l


o



g










2





​












n





的情况。平衡查找二叉树可以解决这个问题。

一、红黑树

1. 平衡二叉查找树定义

平衡二叉查找树：

二叉树中任意一个节点的左右子树的高度相差不能大于1

. 完全二叉树、满二叉树都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。对于定义，有些平衡二叉查找树

没有完全遵循

。

2. 红黑树（Red-Black Tree）定义

红黑树是个明星树，是一种不严格符合定义的平衡二叉查找树。

对于一颗红黑树：

1. 根节点是黑色的；
2. 每个叶子节点都是
   
   黑色的空节点
   
   （NIL），也就是叶子结点不存储任何数据；
3. 任何相邻的节点都不能同时为红色；
4. 每个节点，从该节点到达其可叶子结点的所有路径，都包含相同数目的黑色节点。

对于要求2，是为了简化红黑树的代码实现而设置的，此节暂不考虑也不标出这一点。

红黑树示例：

3. 红黑树的高度分析

将红色节点去掉，二叉树就变成了四叉树：



因为第4条的规定，从任意节点到可达叶子结点的每个路径，包含相同数目的黑色节点，那么这个分离后的四叉树，类似一个完全二叉树。因为一个完全二叉树的高度近似



l

o

g

2

n

log_2n






l


o



g










2





​












n





, 这里去掉红色节点的“黑树”高度也不会超过



l

o

g

2

n

log_2n






l


o



g










2





​












n





。


将红色节点加回去后

，最长路径就不会超过



2

l

o

g

2

n

2log_2n






2


l


o



g










2





​












n





. 也即红黑树的高度约为



2

l

o

g

2

n

2log_2n






2


l


o



g










2





​












n





.

二、各种平衡查找二叉树的对比

1. Treap, Splay Tree的操作效率很高，但无法避免极端情况下时间复杂度的退化，对于单次操作时间敏感的场景不适用。
2. AVL这种弄高度平衡的二叉树，因为要维持高度平衡，每次插入、删除要做调整，适合不需频繁插入、删除的数据集合。
3. 红黑树是这两种的一种折中，性能稳定，适合工业级应用。

关于红黑树的演变由来，可以参照 https://www.cnblogs.com/tiancai/p/9072813.html 。