当前位置:首页 > 天道酬勤 > 正文内容

红黑树算法(二叉树和树的区别)

张世龙2021年12月21日 19:37天道酬勤190

因为红黑树的本质是2-3-4树,所以我们先掌握2-3-4树,红黑树很简单。 本文重点介绍2-3-4树。

2-3-4树

1概念介绍

2-3-4树是4层b树(Balance Tree ),他属于多重搜索树,其结构有以下限制。

所有叶子的节点都有同样的深度。 节点只能是2-节点、3-节点或4-节点。 2-节点:包含一个元素的节点,有两个子节点; 3-节点:包含两个元素的节点,有三个子节点; 4-节点:包含三个元素的节点,有四个子节点; 所有节点必须至少包含一个元素

元素总是保持排序顺序,整体上保持二叉树的性质。 即,父节点比左子节点大,比右子节点小;

另外,节点有多个要素时,各要素必须比其左侧的要素及其左侧的子树的要素大。

下图是典型的2-3-4树

2 生成的过程

接下来,我们来看一下2-3-4树的生成过程

首次插入-2个节点

第二个节点插入三个节点合并

第三个节点-插入4个节点的合并

插入第四个节点-需要分裂

插入6

插入7

插入8

插入9

插入10

插入11

插入12

最后插入1看看效果吧

到这里,大家应该对2-3-4的树有了直观的认识。

3 和红黑树的等价关系

红黑色的树从2-3-4的树开始,其本质是2-3-4的树。

3.1两个节点

与1个2个节点对应的红黑树的节点是黑节点

3.2 3节点

一个三节点可以有两种情况的红黑树节点,一个是右倾,一个是左倾,所以一个2-3-4树可以有多棵红黑树

原则:上黑下红

3.3 4个节点

一个四节点切换时只有一个,中间节点为黑色,左右节点为红色

3.4裂变状态

然后是存在于2-3-4树上的裂变状态。 转换为红色的树后,会先变色。 不能有两个相邻的红色节点。

4 转换为红黑树

接下来我们来具体看看2-3-4的树是如何转换成对应的红黑树的。

原始的2-3-4树:

根据右倾规则,转换如下。

转换后,满足黑节点平衡的要求

按照左倾的规则,进行如下变换。

通过2-3-4树和红黑树的等价关系,非常有助于我们以后分析红黑树的内容!

扫描二维码推送至手机访问。

版权声明:本文由花开半夏のブログ发布,如需转载请注明出处。

本文链接:https://www.zhangshilong.cn/work/26533.html

标签: 红黑树pgc
分享给朋友:

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。