1. 红黑树(Red Black Tree)
(1) 定义
红黑树(Red Black Tree):是一种自平衡的二叉搜索树,也叫平衡二叉B树。
- 红黑树必须满足一下5条性质:
- 节点是
或者
![]()
- 根节点是
![]()
- 叶子节点(外部节点,空节点)都是
![]()
节点的子节点都是
节点的parent都是
从根节点到 叶子节点 的所有路径上不能有2个连续的节点
- 从任一节点到 叶子节点 的所有路径都包含相同数目的
节点
红黑树
(2) 红黑树的等价变换
红黑树 和 4阶B树 (2, 4)树 具有等价性
节点与它的
子节点融合在一起,形成1个B树节点
- 红黑树的
节点个数 与 4阶B树的节点总个数 相等
红黑树
等价变换成 4阶B树
(3) 红黑树的添加删除
- B树中,新元素必定是添加到 叶子节点中
- B树中,最后真正被删除的元素都在 叶子节点中
(4) 平均时间复杂度
- 搜索:
![]()
- 添加:
,
次的旋转操作
- 删除:
,
次的旋转操作
(5) AVL树 和 红黑树
AVL树
- 平衡标准比较严格:每个左右子树的高度差不超过1
- 最大高度是:1.44 *
- 1.328(100万个节点,最大树高28)
- 搜索、添加、删除都是
复杂度
添加仅需次旋转调整,删除最多需要
次旋转调整
红黑树
- 平衡标准比较宽松:没有一条路径会大于其他路径的2倍
- 最大高度是:2 *
(100万个节点,最大树高40)
- 搜索、添加、删除都是
复杂度
添加、删除仅需次旋转调整
- 大量搜索时使用AVL树,搜索、添加、删除次数差不多时使用红黑树
- 红黑树牺牲部分平衡性,平均统计性能优于AVL树
- 实际应用中更多选择使用 红黑树
(6) 树的比较
10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 63, 41, 37, 24, 96
二叉搜索树BST
AVL树
红黑树RBTree