最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • :二叉搜索树的应用

    一、基本概念

    二叉搜索树(又称二叉搜索树、二叉排序树),具有以下特点:

    节点左孩子的值小于节点本身的值;节点右孩子的值大于节点本身的值;左右子树也是二叉搜索树;

    所以最终的结果是:

    二叉平衡树(AVL):二叉平衡树是基于二叉搜索树,有限制:对于任何节点,左右子树的高度差不能超过1。这个约束通常用左手来实现和右手操作。

    左旋转:逆时针旋转两个节点,使一个节点被其右子节点替换,该节点成为右子节点的左子节点

    左旋操作步骤如下:

    首先断开节点PL与右子节点G的关系,同时将其右子节点的引用指向节点C2;​​然后断开节点G与左子节点C2的关系,同时将G的左子节点的应用改为节点C2。指向节点PL

    右旋转:顺时针旋转两个节点,使得一个节点被其左子节点替换,该节点成为左子节点的右子节点

    向右旋转的步骤如下:

    首先断开节点G与左子节点PL的关系,同时将其左子节点的引用指向节点C2;​​然后断开节点PL与右子节点C2的关系,同时将PL的右子节点的应用改为节点C2。指向节点G

    二、红黑树(具有自平衡功能的AVL树)

    1. 红黑树规则:

    节点分为红色或黑色;根节点必须是黑色的;叶节点全部为黑色且为空;连接红色节点的两个子节点是黑色的(红黑树不会出现相邻的红色节点);从任意节点开始,到每个叶子节点的路径都包含相同数量的黑色节点;新加入红黑树的节点为红色节点; (其实这是推断出来的,后面会讲)

    以上6条规则是红黑树给出的自动保持平衡的规则

    我们需要注意的是第3条:叶子节点都是黑色的并且都是null,我们在java中是空的就是null,所以我们看到的都是红色的非叶子节点,但是我们必须知道它不是叶节点。

    我们来看看典型的红黑树长什么样子?

    2、从红黑树的规则特征可以推断出什么?

    从根节点到叶子节点的最长路径不超过最短路径的两倍

    什么样的路径是最短路径?

    从规则5可知,从根节点到每个叶子节点的黑色节点个数相同,则纯黑色节点组成的路径为最短路径;

    最长的路径是什么?

    根据规则 4 和规则 3,红黑树不可能有连续的红色节点。如果有红色节点,则必须有一个连接的黑色节点。当红色节点和黑色节点的数量相同时,它是最长的路径。即黑色节点(或红色节点)* 2

    3、第6项:新增节点是红色节点,为什么?

    从规则4可知,当前红黑树中从根节点到每个叶子节点的黑色节点个数是相同的。这时候如果插入一个新的黑色节点,就会违反规则(它所在的路径)。会多出一个黑色节点),但添加红色节点不一定,除非它的父节点是红色节点,否则规则会被破坏,所以添加红色节点,破坏规则的可能性更小,我们将下面也举个例子。

    三、红黑树的插入操作

    我们以这棵红黑树为例:

    插入步骤:

    根据二叉搜索树的特性,找到新节点的合适插入位置,即找到它的父亲决定将其标记为它父亲的左孩子或右孩子(或特性二叉搜索树的)是一个红色节点,因为可能会破坏原来红黑树的规则,所以需要换颜色+旋转来调整

    案例一:插入后不破坏规则,不需旋转,不需变色:

    我们来看看下面的情况

    当我们插入值为[66]的节点时,红黑树变成这样

    可以看出,插入后的红黑树的特性并没有被原树的特性破坏。

    然后想想为什么? ? ? ?

    原因很简单,因为[66]的父亲[64]是一个黑色节点,我们说过,新节点会作为红色节点插入,那么就不会破坏路径上的黑色节点个数.

    真的是这样吗?我们用TreeMap的源码来验证,不仔细看,只看流程:fixAfterInsertion()是插入节点后必须执行的调整流程

    它一出现就是一个while循环。我们可以看到它的条件状态除非它的父节点是红色节点,所以当它的父节点是黑色节点时,它会直接跳过,也就是说,我们的结论是正确的。

    情况二、插入后只需要改变颜色,不需要旋转

    我们将值为 [51] 的节点插入到上面的哪个树中。这时候红黑树就变成了这个样子

    显然当前结构不遵循规则4(连续出现红色节点),此时需要启动自动平衡机制调整节点平衡状态

    我们可以改变颜色使结构满足红黑树的规则

    首先解决结构不遵循规则4的点(红色节点已连接,节点49-51),节点[49]需要改为黑色(我们说新节点必须是一个红色节点,所以我们Change color 49); 这时候我们发现违反了规则5(56-49-51-XX路径中的黑色节点超过了其他路径),于是我们改变了节点[45] 到红色节点;发现再次违反规则 4(红色节点已连接,节点 56-45-43),然后我们将节点 [56] 和节点 [43] 更改为黑色节点(我们必须往前走,我们不能把 49 再改回去);但是我们发现此时违反了规则 5(60-56-XX 路径的黑色节点比 60-68-XX 的黑色节点多),所以我们需要将节点[68]调整为黑色;完成!

    整个过程结束后的树是这样的

    我们发现它已经满足所有常规属性,不需要旋转。

    那么问题来了,第一种情况是当新插入的节点的父节点为黑色时红黑树 c语言实现,不会破坏树的特性,不需要调整。那么你有没有弄清楚现在的情况是否有任何规则?什么情况下只能改变颜色才能达到目的?

    其实并不难。第一个案例的结论是什么? 因为插入的节点是红色的,而它的父亲是黑色的,所以不会有连续的红色节点,路径上原有的黑色节点数也不会被破坏,所以不需要改变。

    也就是说我们需要考虑两个方面?首先,它会破坏路径上原有数量的黑色节点吗?二、是否会有连续的红色节点。

    我们来看看未调整的树和调整后的树

    结合变色的全过程,总结一下?

    新插入的[51]的父[49]和叔[43]都变成了黑色,导致从根到左叶节点的路径上多了一个黑色节点,所以我们需要[49]和[53] [51] 的父亲,[51]、[45] 的祖父为了消除这种影响而变红。 [45]变红后,因为[56]也是红色的,所以它违反了规则,所以继续变色。让我们先不要继续! ! ! !我们开始的情况是什么?因为[51]和[49]都是红色的,我们开始变色,然后我们继续,你现在发现[45]和[56]都是红色的,继续变色,

    你看到什么了吗? ? 是的,这是一个重复的过程,但是要改变的节点是不同的,所以我们可以肯定调整的过程一定是一个while循环! ! ,对,就是我们刚刚看到fixAfterInsertion()进来的时候

    另外我们再想一想,当[51]和[49]都是红色的时候,两个红色的[43]和[49]会不会一起变黑,当[45]和[49] 56]当两个都是红色的时候,两个红色的[56]和[68]会一起变黑吗?

    [43]是[49]的弟弟,[68]是[56]的弟弟,都是红色的

    那么我们总结一下刚才的小循环过程:

    首先插入[51],发现它的父亲[49]是红色的,发现它的父亲的兄弟[43]也是红色的,然后把他都变成黑色,把他的祖父[45]变成黑色; (因为有连续的红色)接下来,[45]和[56]都是红色的,[56]的兄弟[68]也是红色的,所以把它们变成黑色,然后把[45]的爷爷【 60】变红了

    你可能会说,[60]并没有变,是的,但是他是根节点,根节点一定是黑色的,我们看一下源码来证明这个过程:

    你明白吗? ? 明白我们会看最难的,嘻嘻。

    情况3:变色和旋转都需要

    您能想一想在什么情况下需要进行如此复杂的操作吗? ? ?

    其实并不难。第一种情况是插入红色,它的父亲是黑色,不破坏黑色节点树,没有连续的红色,所以不需要操作;第二个是插入红色,它的父亲是红色的,它的叔叔也是红色的,所以它的父亲和它的叔叔会一起变色,它的爷爷也会相应地变色红黑树 c语言实现,所以同一层红色可以统一变为黑色,下一层的黑色会变成红色,这也是在不改变黑色节点数量的情况下实现的。没有连续的红色,所以只需要改变颜色;

    第二种情况的核心点是它的父亲和它的叔叔在一个层次上,而且都是红色的,而且可以一起变色。

    先看代码,就是刚才的代码:

    没有找到,只有它的父亲是红色的,它的叔叔不是红色的,才会进行旋转操作。

    好的,我会在下一篇博客中介绍put()和fixAfterPut()的具体流程和代码解释。让我们总结一下今天的内容:

    四、红黑树调整总结:

    1. 新插入红黑树的节点必须是红色的2. 如果新插入节点的父亲是黑色节点,则红黑树不需要调整3. 如果新插入节点的父亲是 并且它的叔叔都是红色节点,红黑树只需要改变颜色,不需要旋转 4. 如果新插入节点的父亲是红色的,但是它的叔是黑色的(可以是null,但是null是叶子节点,真子八经的黑色),这个时候肯定是换色+旋转。

    参考文章谢谢!

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » :二叉搜索树的应用

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论