域名转出过程网站能打开吗,wordpress functions.php 修改,做网站要用到什么软件,怎样做网络推广效果好红黑树#xff1a;一棵自平衡#xff08;AVL#xff09;二叉查找树(BST) 什么是红黑树 红黑树#xff0c;Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)。 红黑树是在1972年由Rudolf Bayer发明的#xff0c;当时被称为平衡二叉B树#xff08;sym… 红黑树一棵自平衡AVL二叉查找树(BST) 什么是红黑树 红黑树Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)。 红黑树是在1972年由Rudolf Bayer发明的当时被称为平衡二叉B树symmetric binary B-trees。后来在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。 红黑树是一种特化的AVL树平衡二叉树都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡从而获得较高的查找性能。 它虽然是复杂的但它的最坏情况运行时间也是非常良好的并且在实践中是高效的 它可以在O(log n)时间内做查找插入和删除这里的n 是树中元素的数目。 红黑树的性质规则 红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质 性质1每个节点要么是黑色要么是红色。 性质2根节点是黑色。 性质3每个叶子节点NIL是黑色。 性质4每个红色结点的两个子结点一定都是黑色。 性质5任意一结点到每个叶子结点的路径都包含数量相同的黑结点。保证这棵树尽量是平衡的。 性质1每个节点要么是黑色要么是红色。 性质2根节点是黑色。 性质3每个叶子节点NIL是黑色。 性质4每个红色结点的两个子结点一定都是黑色。(不能有两个连续的红色节点) 2000的子节点不是黑色不满足性质4需要进行“自平衡”操作。 根节点是红色根据性质1需要进行“变色”操作。 性质5任意一结点到每个叶子结点的路径都包含数量相同的黑结点。 从性质5又可以推出性质5.1如果一个结点存在黑子结点那么该结点肯定有两个子结点。 QA Q1.红黑树可不可以全为黑结点 A不可以。 反证法假设有一颗红黑满二叉树结点都为黑色结点时此时添加一个黑色结点不满足5特性但是就算经过旋转也无法满足5特性大家都是黑色变不了红黑树。 红黑树的自平衡操作 前面讲到红黑树能自平衡它靠的是什么 三种操作左旋、右旋和变色。 红黑树结点的叫法 红黑树结点的叫法如图所示。 我们把正在处理(遍历)的结点叫做当前结点如图中的D它的父亲叫做父结点它的父亲的另外一个子结点叫做兄弟结点父亲的父亲叫做祖父结点。 红黑树的自平衡的处理可以总结为 自己能搞定的自消化 自己不能搞定的叫兄弟帮忙 兄弟都帮忙不了的通过父母找远方亲戚。 红黑树实现的源代码Kotlin 红黑树RBT的数据结构 public class RBNodeT { bool color;//颜色 T element;//键值 public RBNodeT left;//左节点 public RBNodeT right;//右节点 public RBNodeT parent;//父节点 } 插入 Before Insert 6000 删除 查询 RB变色 3000 和 4000颜色互换。 不满足性质4每个红色结点的两个子结点一定都是黑色。需要进行RB变色。 旋转 当破坏了平衡时在调整的时候需要用到左旋和右旋 4000节点不满足性质4每个红色结点的两个子结点一定都是黑色。5000和4000都是红色 Single Rotate Left : 以4000节点为中心左旋。 RB 变色 3000 ←→ 4000 RB color 交换 性能 (1) 查找代价 由于红黑树的性质(最长路径长度不超过最短路径长度的2倍)可以说明红黑树虽然不像AVL一样是严格平衡的但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右但在最差情况下(最长路径是最短路径的2倍少1)比AVL要略逊色一点。 (2) 插入代价 RBT插入结点时需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转这一点和AVL的插入操作一样。虽然变色操作需要O(logN)但是变色操作十分简单代价很小。 (3) 删除代价 RBT的删除操作代价要比AVL要好的多删除一个结点最多只需要3次旋转操作。 从根到叶子节点的最大路径不能大于最短路径的两倍长,大致上是平衡的插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例。 如果查找、插入、删除频率差不多那么选择红黑树。 参考资料 RBT 操作动画https://www.cs.usfca.edu/~galles/visualization/RedBlack.html https://www.cs.usfca.edu/~galles/visualization/Algorithms.html https://www.jianshu.com/p/e136ec79235c 专注分享 Java、 Kotlin、Spring/Spring Boot、MySQL、redis、neo4j、NoSQL、Android、JavaScript、React、Node、函数式编程、编程思想、高可用高性能高实时大型分布式系统架构设计主题。
