数据结构与算法(17)-红黑树

  1. 红黑树的实现
  2. 1. 什么是平衡二叉查找树?
  3. 2. 如何定义一棵红黑树 Red Black Tree
  4. 3. 如何实现一个红黑树
  5. Reference

红黑树的实现

首先对于我们前面看到的二叉查找树,在相对理想的情况下,它的时间负责度为O(logn).但是在频繁的动态更新的过程中,可能会出现树的高度远远大于log2(n)的情况,导致各项操作的效率下降.

在极端情况下,二叉查找树会退化为一个链表,时间复杂度会退化到O(n).为了解决这个复杂度退化的问题,我们需要设计一种平衡二叉查找树

1. 什么是平衡二叉查找树?

平衡二叉查找树定义 二叉树中任意一个节点的左右子树的高度相差不能大于1.

平衡二叉查找树的初衷是解决普通二叉查找树在频繁的插入,出现时间复杂度退化的问题

红黑树并没有严格满足平衡二叉查找树的定义,即其左右子树的高度有时相差是会超过1 的。

平衡二叉查找树中平衡的意思就是让整棵树看起来比较对称,不要出现左子树很高,右子树很矮的情况。这样就能让整棵树的高度相对来说低一些。

  • 最开始被发明的是AVL树,严格符合平衡二叉查找树的定义
    • 任何节点的左右子树高度相差不超过1
    • 是一种高度平衡的二叉查找树

2. 如何定义一棵红黑树 Red Black Tree

是一种不严格的平衡二叉查找树。红黑树当中的节点,一类被标记为黑色,一类被标记为红色。

  • 根节点是黑色的
  • 每个叶子节点都是黑色的空节点(NIL),即叶子节点不存储数据
  • 任何相邻的节点都不能同时为红色,即红色节点是被黑色节点分割开的
  • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点

二叉查找树的很多操作的性能都跟树的高度成正比,因此为了证明红黑树近似平衡,我们需要分析的问题可以转化为其高度是否能比较稳定的趋近log2(n)。红黑树的插入,删除,查找等各种操作性能都比较稳定

AVL是高度平衡的二叉树,查找效率非常高,但是每次插入删除都要对应做调整,所以会比较复杂耗时。红黑树只是做到近似平衡,在维护平衡的成本上,要比AVL要低。

3. 如何实现一个红黑树

红黑树的平衡过程就是根据节点排布的特征来,遇到什么样的节点排布,我们就对应的去进行调整

  • 重要操作
    • 左旋 rotate left
      • 将基准点的右子树绕x做逆时针旋转,是的x的右子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的特性仍然能够得到满足
    • 右旋 rotate right
      • 将x的左子树绕x顺时针旋转,使得x的左子树成为x的父亲,同时修改相关节点的引用。旋转之后,二叉查找树的属性仍然能够满足

Reference

https://www.cnblogs.com/carpenterlee/p/5503882.html


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 stone2paul@gmail.com

文章标题:数据结构与算法(17)-红黑树

文章字数:862

本文作者:Leilei Chen

发布时间:2020-02-11, 12:16:00

最后更新:2021-07-12, 00:33:46

原始链接:https://www.llchen60.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-17-%E7%BA%A2%E9%BB%91%E6%A0%91/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏