第10章. 红黑树

红黑树(Red Black Tree)

红黑树性质

null节点只是一种记号，并不存储真实数据，也不是红黑树中的实际节点，其作用是方便程序员在设计和编程时理解节点的操作规则，在实际应用中并没有实际意义。

红黑树的等价变换

红黑树和4阶B树(2-3-4树)具有等价性

红黑树是平衡二叉搜索树，而B树是平衡多路搜索树。

红黑树的添加操作

略过

红黑树的删除操作

略过

平均时间复杂度

• 搜索：O(logn)
• 添加：O(logn)，O(1)次的旋转操作
• 删除：O(logn)，O(1)次的旋转操作

AVL树 vs 红黑树(重要)

红黑树相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。