平衡搜索树

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

相关文章

来自专栏机器学习和数学

[编程经验] Tensorflow中的共享变量机制小结

今天说一下tensorflow的变量共享机制,首先为什么会有变量共享机制? 这个还是要扯一下生成对抗网络GAN,我们知道GAN由两个网络组成,一个是生成器网络G...

85130
来自专栏CreateAMind

keras doc 7 Pooling Connceted Recurrent Embedding Activation

‘th’模式下,为形如(samples,channels, rows,cols)的4D张量

15130
来自专栏社区的朋友们

Kaggle 实战:Ghouls, Goblins, and Ghosts

本例使用R语言中的决策树以及随机森林package对kaggle的一个分类问题解题的全部过程。本文需要读者对机器学习中的决策树、随机森林的原理有所了解,并且知道...

1.1K00
来自专栏崔庆才的专栏

Attention原理及TensorFlow AttentionWrapper源码解析

3.5K40
来自专栏desperate633

LintCode 寻找缺失的数题目分析方法二 交换法

给出一个包含 0 .. N 中 N 个数的序列,找出0 .. N 中没有出现在序列中的那个数。

8630
来自专栏个人分享

旋转数组的最小数字

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

10340
来自专栏菜鸟程序员

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

12720
来自专栏专知

【干货】计算机视觉实战系列03——用Python做图像处理

【导读】专知成员Hui上一次为大家介绍Matplotlib的使用,包括绘图,绘制点和线,以及图像的轮廓和直方图,这一次为大家详细讲解Numpy工具包中的各种工具...

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

Bloom Filter 的数学背景

18730
来自专栏AI派

Numpy 修炼之道 (7)—— 形状操作

无论是ravel、reshape、T,它们都不会更改原有的数组形状,都是返回一个新的数组。

30430

扫码关注云+社区

领取腾讯云代金券