红黑树详解 接上文，红黑树的历史进程（红黑树是用来干什么的） 汇总：二叉查找树=>平衡二叉树(AVL)=>红黑树 – 知乎 (zhihu.com) 上文，我们提到了性质： 性质1. 结点是红色或黑色。 性质2. 根结点是黑色。 性质3. 所有叶子都是黑色。（叶子是NIL结点） 性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点） 性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。 接一张来源于网络的图片
首先，我们剖析一下5条性质： 1.结点是红色或黑色。 这个顾名思义，红黑树，但是为什么叫红黑树只是是因为红黑树的取名者喜欢红色和黑色这两种颜色。。。 2.根结点是黑色。 这个是有说法的。如图
如果根节点是红那么我们只能在下面添加黑节点（性质4）。但是我们一般只会添加红色节点。（留个悬念） 3.所有叶子都是黑色。（叶子是NIL结点） 这玩意记住就行，为的是把树都搞成满二叉树。（为了方便，至于为什么方便，自己悟） 4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点） 这个其实蛮重要的。如果从头到尾全是红色节点，虽然满足其他性质。但是岂不是乱套了。。。 5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。 最重要的性质。这是保证比较平衡的根本 这样做导致没有路径能多于任何其他路径的两倍长。 从而使得这棵树大体上能保持平衡（即高度不会差距太大） 好，现在出发，看看红黑树的旋转跳跃（如果一步步插入节点） 我们性质看完了，这样两棵树大家是能接受的。
大家盯着第二张图，不要移开目光，如果我们将一个节点插入进去。那么大家一定能够接受–为什么只添加红色节点。（忽略了最后的NULL节点）
因为我们添加黑色，就使得红黑树不再满足第五条性质，这是一定的。这是非常严重的，需要很多算法调整才可以重新恢复。而插入红色的话只有可能不满足第4条性质，而且有可能直接就满足条件了。。。 （那就不必多说）我们在这里直接解决第二种情况。
就这样不就解决了么。将颜色调换一下，向上迭代，直到满足性质。就ok了 （或许，大家要问不是说性质二说了根节点是黑色吗，这是有可能让根节点变为红色的阿。我在上文说到了为什么要有这个性质，那么在不产生影响的情况下，根节点变色就变色了吧。直接变为黑色就好了阿）
根节点变色情况 既然这样，那就讨论一下，如果插入节点时出现另一种情况时
图一
在红黑树左边新增节点 我们发现在这种情况下，直接变色肯定不实际。于是： 右旋： 因为我们是在原本平衡的红黑树左边新增红色节点。于是左边红色产生了连续（性质四） 我们必须做点什么来保证红黑树的平衡（右旋） 看起来花里胡哨的，但事实上是否有某些规律？ 在图一中 我们新加的节点是1（它使得树不再平衡） 此时右旋，由于二叉搜索树原本的性质，一定要使得右边大于左边。于是我们右旋，要将左边的向右边移动，那么就要选择一个左边最大的节点重新作为祖父节点，并且交换两者颜色（前两代的节点）（在这个例子中，2是左边最大） 在图二中 我们新加的节点是2（它使得树不再平衡） 此时右旋，依旧是选择左边最大的节点重新作为祖父节点，并且交换两者颜色（在这个例子中，依旧是2是左边最大） ok:规律就出来了，这种情况下直接找到左边最大节点（可以根据二叉搜索树的性质直接定位到）然后全部节点向右边扯一下，按照二叉搜索树的性质重新排列就ok <=很重要，决定了子孙节点的重新链接。 那么节点插入到此为止 还有其他情况嘛，当然有，那就是以上三种情况的对称情况。大家自行体会（左旋就是找右边最小的作为祖父节点）
直接变色，向上迭代
左旋处理
左旋处理 插入结束 二叉搜索树，自然无非是搜索，插入，删除。既然搜索不影响树本身，那就要讨论一下删除。 二分搜索树节点删除 | 菜鸟教程 (runoob.com) <==不了解二叉搜索树的删除可以看看 我们根据删除的部分，来分为四种情况 本来我想详细论述一下 后来发现文字描述很干。。。只好挂个B站的视频 红黑树快速入门 – 04删除_哔哩哔哩_bilibili 到此结束
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/26583.html
