红黑树—存在的必要？算法原理？红黑树&&平衡二叉树 对比思考 首先了解一下为啥需要这种红黑树？ 有句话叫存在就是合理。红黑树是非常合理。 我们已经有二叉查找树和平衡二叉树，为啥需要一个红黑树的存在呢？？ 1、先简单说一下二叉查找树和平衡二叉树 思想：二叉查找树和平衡二叉树都是将二分查找的思想引入到树形结构中。 1.1 二叉查找树 二叉查找树（BST）具备什么特性呢？ 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根结点的值。 3.左、右子树也分别为二叉排序树。 从如下图中查找10的路径为9—->13—->11—–>10
缺点：虽然将二分思想引入，但是实际中很少有上图如此完美的插入顺序；如果我们的插入顺序无法稳定，那么极有可能出现如下的场景： 向下面的树中依次插入 7,6，5,4，3,2，1
结果如下：
显然上述场景是一种非常不理想的场景。这只是一种极限情况，实际中可能很难遇到此极限。但是由于二叉查找树没有对各条查找线路长度做限制，导致其不可控因素巨大。 二叉树如果完全平衡的，则近似于折半查找，效率为O(Log2n)。如果二叉排序树完全不平衡，则其深度可达到n，查找效率为O(n)，退化为顺序查找。所以二叉排序树的查找性能在O(Log2n)到O(n)之间。因此，为了获得较好的查找性能，就要构造一棵平衡的二叉排序树。 1.2 平衡二叉树 条件一：它必须是二叉查找树。 条件二：每个节点的左子树和右子树的高度差至多为1。 为了减小查找效率的不确定性，稳定其查找次数。在二叉查找树中对其做了高度限制，这样就可以将查找次数稳定在（O（logn）)内。 但是其插入时就费劲了。没有二叉查找树方便。二叉查找树，就是从根节点开始往下找，找到自己的位置，连接上就好了。二叉平衡树，为了满足条件二，需要在插入加节点之后，可能需要进行平衡操作。如上图，若在平衡二叉树中插入一个点 4
插入后将不满足（每个节点的左子树和右子树的高度差至多为1）条件。于是乎需要调节平衡。详细步骤此处不做详解。自行学习吧。 AVL树的查找、插入、删除操作在平均和最坏的情况下都是O（logn） 2 . 红黑树出现了 红黑树的特性: （1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （3）每个叶子节点（NIL）是黑色。[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！] （4）如果一个节点是红色的，则它的子节点必须是黑色的。 （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
思考： 想一下，若有一颗树，其全都是黑色节点。那么为了同时5个条件。只有一种可能那就是满平衡二叉树。也就是说只有黑色节点的红黑树其实就是平衡二叉树。 我们将红色点想成是填充节点。即每次插入都以红色插入，且将黑色想成主要节点。红色节点做填充。 红色节点的作用就是使得树的高度更加灵活，不至于像平衡二叉树那样每次插入都需要 做平衡操作（减少了需要平衡的概率）。 （红色节点的子节点是黑色节点）条件就使得高度受到限制，极限情况就是一个红色一个黑色串联。最多的查找次数 不会超过2倍的 最少的查找数。 总之：红黑树其实就是 二叉查找树和平衡二叉树 两者优缺点的一种折中。 可以防止出现二叉查找树那种 极差的情况 可以减少插入时平衡的次数。 其综合效率是最优的。但是查找效率，应该是平衡二叉树最快。
参考文章：https://blog.csdn.net/isunbin/article/details/小灰：漫画：什么是红黑树？
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/37931.html
