平衡搜索树

2-3树

​ 其实仔细来看2-3树好像是 B 树的一个特例,它规定了一个节点要么有一个 key 要么有两个 key。

  1. 如果有一个 key 那么他就有两个子节点,左边小于这个 key 右边大于这个 key
  2. 如果有两个 key 那么他就有三个子节点,左边小于,中间处于两者之间,右边大于

​ 这样一来就会发现他其实也会处在插入的时候出现分裂的情况,当一个节点需要插入的时候我们先让他插入,这时候可能出现一个节点有三个 key 的情况,我们就打出四个分支,然后我们把中间的那个 key 分裂到父节点,然后左右的 key 分别作为左右子节点。

​ 这时候我们能够发现当且仅当我们的根节点分裂的时候我们的 2-3 树的高度才会真正的加一。这也是和 B 树的性质相似的。

​ 2-3 树最好情况就是当所有的节点都是 3 key 节点的时候,这时候我们的树高度最小,而最坏情况自然也就是一个二叉树的时候。

红黑树

红黑树我们可以把它看做为 2-3 树的变种,也就是说我们可以在 2-3 上进行一些改造生成对应的红黑树。一般来说我们就是将那些具有三个子节点的节点拆分成两个节点,key 大的那个作为根,小的那个作为左子节点,然后他们之间使用红色连接起来(用红色连接的意思就是父节点是黑的,子节点是红的),也就可以看出红黑树更偏向于左边。下面是一个具体的例子:

红黑树的三个基本操作:

左旋转

​ 从第一个图到第二个,这个在什么情况下需要呢?当我们插入一个新节点的时候我们发现插入后就是图一的情况,这时候我们还原到 2-3 树我们发现因为 s 节点更大,所以 s 节点应该是根节点, e 节点应该是 s 节点的子节点才对。所以产生了这样的操作!

​ 所以说,当我们插入一个节点的时候我们发现插入到了右边的节点了我们就需要左旋转进行调整。

右旋转

右旋转刚和和左旋转相反。

颜色翻转

颜色翻转就是

当红黑树是这种情况的时候我们会发现他对应的 2-3 树是有问题的,需要进行分裂,所以说这里的颜色翻转就是把他的子节点都表示为黑色,自己变成红色。

红黑树的插入操作

上面看到了关于红黑树的三个基本操作,这三个操作其实在我们插入的时候都是用的上的,并且重要的是在 AVL 树我们也可以仿照这种思想去完成平衡操作。

上面一般就是我们进行插入的时候会遇到的所有需要处理的情况。

  • 首先看第一个,就是在插入的时候 C 被插入到了左节点,这时候根据 2-3 树的规定我们是需要进行旋转的,把 C 作为根节点,就类似于把 C 提起来,然后 A 节点随着重力到达左节点。也就是左旋转
  • 第二种情况就是左右节点都是红节点的时候我们就需要进行颜色翻转,让左右子节点都变黑,根节点边城红节点
  • 第三种情况一开始属于有两个连续的红节点在左边,这时候我们仅仅需要进行一次右旋转就变成了第二种情况了
  • 第四种情况我们可以看到首先进行一次左旋转,然后右旋转又再次回到了第二种情况,也就是颜色翻转 所以说无论怎么变化我们只需要这三个基本操作我们就可以保证红黑树的性质不被破坏。 所以最终的代码就是

我们的 AVL 树完全可以按照这个套路在接着写。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二叉树

    1.二叉树的性质 1.具有 n 个节点的二叉树第 n 层最多2的 n-1 次方个节点 2.具有 n 个节点的二叉树最多有 2 的 n 次方减 1 个节点 3.度...

    lwen
  • LinkedHashSet 源码分析

    LinkedHashSet 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE ...

    lwen
  • 优先队列

    优先队列基本介绍 ​ 优先队列又叫做堆,他是一种比较特殊的完全二叉树。所谓完全二叉树就是一层层的堆叠,本层不满就不能堆放下一层。并且优先队列还有一个特点就...

    lwen
  • PaperReading-图嵌入之node2vec

    不同于图像、自然语言这种欧式空间的数据,网络结构的数据——图,通常无法通过CNN或者RNN来处理,这就需要我们寻找其他的方法来处理图数据。图数据其实非常常见,例...

    beyondGuo
  • 获取DOM节点的方法汇总

    我们都知道,当获得所有节点(如:getElementsByTagName)或者获得所有子元素(如:element.childNodes)时,实际上返回的是包含一...

    Chor
  • 红黑树的特性

    (1)每个节点或者是黑色,或者是红色。 (2)根节点是黑色。 (3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点...

    IT技术小咖
  • 深度优先搜索

    深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点...

    致Great
  • 『互联网架构』软件架构-zookeeper快速入门(33)

    PS:重点原理和基本命令。Zookeeper 是一个有上下级关系(Leader 、follower 、Observer )的集群。客户端链接 zookeeper...

    IT故事会
  • 二叉查找树(Binary Search Tree)

    在二叉搜索树b中查找x的过程为: 若b是空树,则搜索失败,否则: 若x等于b的根节点的数据域之值,则查找成功;否则: 若x小于b的根节点的数据域之值,则搜...

    None_Ling
  • DOM(文档对象模型)基础加强

    黑泽君

扫码关注云+社区

领取腾讯云代金券