红黑树 Hello 大家好，我是小兴兴，最近在看数据结构与算法。相信大家肯定知道，数据结构中比要重要的就是树结构，什么二叉树、平衡二叉树、B 树、B+ 树，傻傻分不清楚。今天呢主要是给大家分享一篇树结构的文章，写的非常好，希望可以给大家带来帮助。 作者：程序员之木铎 链接：红黑树 来源：《泥地里乌龟》 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 看完了 2-3 查找树，我们应该知道它是为了应对二叉搜索树的不均衡的情况。不均衡的情况会严重影响搜索效率。将2-3树的思想铺开，能够得到2-3-4树。这次要说的是红黑树，红黑树是根据2-3-4树的思想，对2-3-4树进行实现。先来看看红黑树的样子。
红黑树和2-3-4树的关系： 红色节点可以看作是与其父节点组成的多节点，比如 3 右子树是 4，4是红色，所以可以看作是 3，4多节点。
按照上面的红黑树与2-3-4树的关系，我们可以这样来看红黑树：
定义： 1. 红黑树是二叉搜索树 2. 每一个节点或者是红的，或者是黑的 3. 跟节点必须是黑的 4. 每一个叶节点都是空，并且是黑的 5. 红节点的孩子必须是黑的 6. 所有的从跟节点到叶节点的黑色节点个数都必须一样。 经过上面的定义，我们可以发现下面几个事实： 1. 两个红节点不能相连 2. 从 x 到 x 的后代叶节点的路径上，黑色节点的数量是相同的。我们可以把这个数量定义称为 bh(x). 其中不包含x。 3. 从跟节点到叶节点的长度差不会超过一倍。 4. 包含n个内部节点的红黑树，height <= 2log(n+1) 查找： 就是按照二叉搜索树的查找，不必赘述。 插入： 将需要插入的素z按照常规的二叉搜索树进行插入，颜色是红色。 然后需要处理对于红黑树的定义违反之处。 a) 跟节点是红色的，那么就让跟节点变成黑色。 b) z 和 z 的父节点都是红色的。处理这种情况，总共有三种 六种冲突情况的处理，假设新加入的节点是z： 1. 父节点和父节点的兄弟节点都是红色的处理方法 a) 将z的父节点和父的兄弟节点都变成黑色 b) 将z的祖父节点变成红色 c) z的祖父节点变成红色后，循环处理冲突
2. z的父节点是红色，叔叔节点是黑色, z 的父节点是左孩子，z是右孩子。 a) 在z的父节点执行左移操作 b) 让 z 的左孩子成为新的新插入的z节点，继续处理冲突。
z的父节点是红色，叔叔节点是黑色, z 的父节点是右孩子，z是左孩子。 a) 在z的父节点执行右移操作 b) 让 z 的右孩子成为新的新插入的z节点，继续处理冲突。 3. z的父节点是红色，叔叔节点是黑色, z 的父节点是左孩子，z是左孩子。 a) 在z的祖父节点右移一次 b) 将z的parent和z的兄弟节点交换颜色
z的父节点是红色，叔叔节点是黑色, z 的父节点是右孩子，z是右孩子。 a) 在z的祖父节点左移一次 b) 将z的parent和z的兄弟节点交换颜色 删除： 先回顾二叉搜索树的删除操作： 1. 如果删除的节点是z，z没有孩子节点，直接删除 2. 如果z包含有一个孩子, 那么就将z去除掉，让z的这个孩子替代之前z的位置。 3. 如果z包含两个孩子，我们就去寻找一个successor y 来替代z，然后将y删除。又是一个递归的过程。 successor y 的寻找顺序： z右孩子的最左节点 z左孩子的最右节点 举个例子（删除节点中的32）：
下面的过程是删除节点65:
红黑树的删除操作： 1. 就像是普通的搜索二叉树一样删除一个节点z 2. 如果z包含有两个孩子，那么拷贝y的值给z的时候，不要复制颜色 3. 让y成为需要被删除的那个节点 4. 如果 y 是红色的，那么不影响红黑树的属性 5. 如果 y 是黑色的，那么就一定产生了红黑树的冲突。 6. 假设 x 是 y 的那个唯一的孩子节点，x也有可能为空。 a) 假设 x 是 红色的, 直接将x改成黑色即可 b) 假设 x 是黑色的 I x的兄弟节点 w 是红色的。 左移一位，然后修改B和D的颜色，就变成了 II，III，IX
II x的兄弟节点 w 是黑色的，w的两个孩子也是黑色的。w变为红色 将 x 变成它的父节点，继续循环第六步
III x的兄弟节点 w 是黑的，w的左孩子是红色的，右孩子是黑色的 右旋转w，交换w和它的孩子的颜色。转变成了 IX
IX x的兄弟节点 w 是黑色的，w的右孩子是红色的。 以x的父节点为基准左旋转，然后改变w的的右孩子的颜色。
以上就是红黑树的删除操作。 红黑树（Red Black Tree） 是一种自平衡二叉查找树 好了这篇文章到这里就结束了。 下面简单说下时间复杂度、空间复杂度的知识，帮助我们更好的掌握以上知识内容。 一、什么是(渐近)复杂度分析？ 数据结构和算法解决是 “如何让计算机更快时间、更省空间的解决问题”。因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。 二、为什么要进行复杂度分析？ 和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。 三、如何进行复杂度分析？ 大 O 表示法 1）来源 算法的执行时间与每行代码的执行次数成正比，用 T (n) = O (f (n)) 表示，其中 T (n) 表示算法执行总时间，f (n) 表示每行代码执行总次数，而 n 往往表示数据的规模。 2）特点 以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽略这些项。复杂度分析法则 1）单段代码看高频：比如循环。 2）多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。 3）嵌套代码求乘积：比如递归、多重循环等 4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。 四、常用的复杂度级别？ 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括， O (1)（常数阶）、O (logn)（对数阶）、O (n)（线性阶）、O (nlogn)（线性对数阶）、O (n^2)（平方阶）、O (n^3)（立方阶） 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括， O (2^n)（指数阶）、O (n!)（阶乘阶） 五、如何掌握好复杂度分析方法？ 复杂度分析关键在于多练，所谓孰能生巧。 总结 一、复杂度分析的 4 个概念最坏情况时间复杂度：代码在最理想情况下执行的时间复杂度。最好情况时间复杂度：代码在最坏情况下执行的时间复杂度。平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。 二、为什么要引入这 4 个概念？同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这 4 个概念。代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。 三、如何分析平均、均摊时间复杂度？平均时间复杂度 代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。均摊时间复杂度 两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/30084.html
