汇总：二叉查找树=>平衡二叉树(AVL)=>红黑树 偶然机会需要实验一下红黑树算法。（第一感觉就是扑克里面的红桃黑桃）（o–o) 本文旨在溯源红黑树。二叉查找树=>平衡二叉树(AVL)=>红黑树 （参考了一些网络博客）已挂链接 二叉查找树 ==>文章参考 前两部分图片大部分源自这里 大家应该熟悉二叉树。（一个节点最多只有两个孩子的树） 还有熟悉的二分查找，能够提升查找的时间复杂度 O(n) 变为 O(logn)。那么二叉查找树就结合两者并使得二分查找更加结构化。如图：
图片很直观多的话不说，自己悟。（左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大） 但是终究还是缺点很多如：（某些极端条件下）
如果是这样一组数字组成的二叉查找树，那么问题很大。(变成了一条线->链表） 这样查与：查找一个数字在一个数组中。有任何区别吗？ 当然没区别。。。所以问题就来了。尤其是时间复杂度又回到原来的 O(n) 。（就很惨） 平衡二叉树(AVL) 于是就有了平衡二叉树(AVL)。目的当然是为了解决上述问题 (不要以为偶然情况下才会发生上述问题，不管也罢。但是在一个巨大数据量中，O(logn)与O(n)时间相差很恐怖的) 平衡二叉树的特点： 1、具有二叉查找树的全部特性。 2、每个节点的左子树和右子树的高度差至多等于1。
图一是，图二不是 性质一，可以顾名思义，有些水。 性质二，很重要。这是为什么要在前面加一个平衡的原因。防止了左右子树有一方太长了的问题。看一下图自己悟。（图一根节点左右子树长度为1和0，满足相差小于等于一的条件。图二为2和0则不满足 || 理解为2，0和3，1同理）。 正因为这样的性质，所以直接解决了上述二叉查找树的问题。 但是，又产生了新的问题。我们如何：在每次新添加一个节点的时候都能保证形成这样的树。 那就是它的核心算法，左旋，右旋啥的。而且这个我不保证能给你讲明白。于是我就挂个链接（附代码）: 【漫画】以后在有面试官问你AVL树，你就把这篇文章扔给他。 (sigusoft.com)<==反正我是悟到了。 ok,如你懂了也罢，没看懂也罢。我们不得不承认它的开创性与复杂性。 红黑树 千呼万唤，红黑树来了。就是因为上述算法太复杂，而且耗时（主要是耗时，因为红黑树可能更复杂） 首先还是先把定义摘出来 性质1. 结点是红色或黑色。 性质2. 根结点是黑色。 性质3. 所有叶子都是黑色。（叶子是NIL结点） 性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点） 性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。 图片如图（来自网络）
在我看来，前几条性质也是水的。 最重要是最后一条，从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。 也就是说。从任意节点往下走无论走哪一条路，到达叶子节点，所经过黑色节点的个数相等（又复述了一遍，还是要自己悟道）。可以看图证实。 这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。 是性质4导致路径上不能有两个连续的红色结点确保了这个结果。最短的可能路径都是黑色结点，最长的可能路径有交替的红色和黑色结点。因为根据性质5所有最长的路径都有相同数目的黑色结点，这就表明了没有路径能多于任何其他路径的两倍长。 摘自=>百度百科 我说人话就是，这样做导致没有路径能多于任何其他路径的两倍长。 从而使得这棵树大体上能保持平衡（即高度不会差距太大） 也就是说：红黑树没有完全更改上述算法，但也没追求太完美。 红黑树的逻辑（正题） 前面都是一些汤汤水水，后面才是逻辑+代码。（简单实现） 目前没有时间进行论述，但挂出来了一个看到的还算是通俗易懂的解析，挂了出来 彻底搞懂红黑树 – 知乎 (zhihu.com) PS:后续会详解这个红黑树，本文旨在溯源红黑树。二叉查找树=>平衡二叉树(AVL)=>红黑树。 参考文章已经算是很好理解了。 已经有了==>红黑树详解 – 知乎 (zhihu.com)
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/20636.html
