好玩的网站列表

红黑树的实现

首先对于我们前面看到的二叉查找树，在相对理想的情况下，它的时间负责度为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