数据结构 - 红黑树

1. 红黑树（Red Black Tree）

(1) 定义

红黑树（Red Black Tree）：是一种自平衡的二叉搜索树，也叫平衡二叉B树。

  • 红黑树必须满足一下5条性质：
  1. 节点是 \color{red}{Red} 或者 \color{black}{Black}
  2. 根节点是 \color{black}{Black}
  3. 叶子节点(外部节点，空节点)都是 \color{black}{Black}
  4. \color{red}{Red}节点的子节点都是 \color{black}{Black}
    \color{red}{Red}节点的parent都是 \color{black}{Black}
    从根节点到 叶子节点 的所有路径上不能有2个连续的\color{red}{Red}节点
  5. 从任一节点到 叶子节点 的所有路径都包含相同数目的\color{black}{Black}节点
红黑树

(2) 红黑树的等价变换

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

  • \color{black}{Black}节点与它的\color{red}{Red}子节点融合在一起，形成1个B树节点
  • 红黑树的\color{black}{Black}节点个数 与 4阶B树的节点总个数 相等
红黑树
等价变换成 4阶B树

(3) 红黑树的添加删除

  • B树中，新元素必定是添加到 叶子节点中
  • B树中，最后真正被删除的元素都在 叶子节点中

(4) 平均时间复杂度

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

(5) AVL树 和 红黑树

AVL树

  • 平衡标准比较严格：每个左右子树的高度差不超过1
  • 最大高度是：1.44 * log_2(n + 2) - 1.328（100万个节点，最大树高28）
  • 搜索、添加、删除都是O(logn)复杂度
    添加仅需O(1)次旋转调整，删除最多需要O(logn)次旋转调整

红黑树

  • 平衡标准比较宽松：没有一条路径会大于其他路径的2倍
  • 最大高度是：2 * log_2(n + 1)（100万个节点，最大树高40）
  • 搜索、添加、删除都是O(logn)复杂度
    添加、删除仅需O(1)次旋转调整
  • 大量搜索时使用AVL树，搜索、添加、删除次数差不多时使用红黑树
  • 红黑树牺牲部分平衡性，平均统计性能优于AVL树
  • 实际应用中更多选择使用 红黑树

(6) 树的比较

10, 35, 47, 11, 5, 57, 39, 14, 27, 26, 84, 75, 63, 41, 37, 24, 96

二叉搜索树BST
AVL树
红黑树RBTree
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容