平衡搜索树

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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

27:单词翻转

27:单词翻转 总时间限制: 1000ms 内存限制: 65536kB描述 输入一个句子(一行),将句子中的每一个单词翻转后输出。 输入只有一行,为一个...

3977
来自专栏个人分享

旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个非递减序列的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2...

844
来自专栏菜鸟程序员

Java中在特定区间产生随机数

702
来自专栏数据处理

TensorFlow入门1-minist

1653
来自专栏10km的专栏

faster rcnn:assert (boxes[:, 2] >= boxes[:, 0]).all()分析塈VOC2007 xml坐标定义理解

在进行faster rcnn训练的时候,报了一个断言错误 File “/py-faster-rcnn/tools/../lib/datasets/imdb.p...

3605
来自专栏数据结构与算法

拉格朗日插值

存在性和唯一性的证明以后再补。。。。 拉格朗日插值 拉格朗日插值,emmmm,名字挺高端的:joy: 它有什么应用呢? 我们在FFT中讲到过 设n-1次多项式为...

2867
来自专栏CreateAMind

keras doc 8 BatchNormalization

该层在每个batch上将前一层的激活值重新规范化,即使得其输出数据的均值接近0,其标准差接近1

1705
来自专栏编程

扣丁学堂浅谈Python视频教程之random模块详解

今天扣丁学堂小编给大家详细介绍一下关于Python视频教程之random模块详解,,首先用于生成伪随机数之所以称之为伪随机数,是因为真正意义上的随机数(或者随机...

22610
来自专栏木东居士的专栏

Bloom Filter 的数学背景

1623
来自专栏余林丰

12.高斯消去法(1)——矩阵编程基础

对于一阶线性方程的求解有多种方式,这里将介绍利用高斯消去法解一阶线性方程组。在介绍高斯消去法前需要对《线性代数》做一下温习,同时在代码中对于矩阵的存储做一个简...

2367

扫码关注云+社区