每个儿子都是(可能为空)一个子2-3-4树。根节点是其中没有父亲的那个节点;它在遍历树的时候充当起点,因为从它可以到达所有的其他节点。叶子节点是有至少一个空儿子的节点。同B树一样,2-3-4树是有序的:每个元素必须大于或等于它左边的和它的左子树中的任何其他元素。每个儿子因此成为了由它的左和右元素界定的一个区间。如下图所示(你可以看到,图中这棵2-3-4树是由2-结点,3-结点,4-结点元素组成的):
2-3-4树是紅黑树结构的一种等同,这意味着它们是等价的数据结构。换句话说,对于每个2-3-4树,都存在着至少一个数据元素是相同次序的红黑树。在2-3-4树上的插入和删除操作也等价于在红黑树中的颜色翻转和旋转。这使得它成为理解红黑树背后的逻辑的重要工具(还是如此,红黑树稍后介绍,路得一步一步来)。
1.1、2-3-4树的查找
2-3-4树中查找结点,怎么查找呢?分为以下几个步骤:
1、把要查找的结点与根结点相比较
2、根据左小右大的原则,寻找含有要查找结点的区间
3、若找到了,则直接返回该结点,否则,在其子女中继续递归寻找。
如下图所示,在下面这棵2-3-4树中寻找L结点:
1.2、2-3-4树的插入
插入某个结点之前,一般我们先在2-3-4树中寻找是否存在该插入结点(若存在,当然也就没有必要再插入了),如果树中不存在该结点,则执行插入操作。
1.2.1、插入形式一:3-结点元素中插入结点
如下图所示,插入X结点,首先在树中查找是否存在X结点,
没有找到,则在含有YZ的结点元素插入X:
1.2.2、插入形式二:
以下插入H结点,在FGJ区间上发现H没有找到后,
且FGJ区间上已经没有空间来插入H结点了,这个时候怎么办呢?:
当没有空间执行插入操作的时候,咱们当然得寻找空间来执行插入。怎么寻找呢?看下图:
由上图,我们发现,H在区间FGJ上没有空间执行插入的时候,我们首先参试着让G元素上移至CE区间,组成CEG根结点,然后分裂FG区间,F和G各自成为独立的元素。当我们发现,H依然不能作为J的子女进行插入时,我们想到了一种折中的办法,这种办法就是,如下图所示,H插入到J元素旁,成为HJ区间,F元素不作变动:
所以,当发现没有空间可执行插入结点的情况时,我们作如下对策:
1、分裂父母结点
2、然后再插入结点
上述的第1点具体怎么分裂呢?分裂的两种情况如下图所示:
下面再具体分析下上述两种分裂情况:
分裂情况1、如下图所示D-KQW,区间KQW分裂,Q上移与原根结点D组成新的根结点区间DQ,K和W各自分裂成独自区间,D-KQW最终分裂成DQ-K-W:
分裂情况2、如下图所示DH-KQW分裂,KQW区间中的Q元素上移与DH组成根元素区间DHQ,K和W分裂,最终DH-KQW分裂成DHQ-K-W:
下图是逐步在2-3-4树中依次插入元素A、S、E、R、C、D、I。从中你可以看到
1、当插入元素R时,A E S区间分裂,E成为新的根元素,而要插入的R与S移至一起成为E的右儿子。
2、当插入C、D、I时,都是直接找到相对应的区间,各自插入。不必啰嗦,下图已经很形象了。
但下面,继续在上述的A、S、E、R、C、D、I插入操作的基础上之后,再依次插入N、B、X各元素时,情况,就比较复杂了,但下图还是很清晰的表明了各种插入操作及相关元素的调整情况,在此不赘述:
下图所示的是在2-3-4树中插入结点的insert代码:
到此,插入情况已经阐述完,删除情况略过。接下来,咱们来分析下2-3-4树的平衡情况。
1.3、2-3-4树的平衡
2-3-4树的高度为:
1、最坏情况,logn,树中全部都是2结点元素(即如第一节所述的全都是包含一个元素和2个儿子的结点。如此图所示,树中全部都是这样的结点:
2、最好情况,log4N=1/2logN,树中全部都是4结点元素(即如第一节所述的全都是包含3个元素和4个儿子的结点,如此图所示,树中全部都是这样的结点:
3、3结点情况是中间情况,即包含2个元素和3个儿子,
。
第二节、Red-Blacktrees(红黑树)
2.1、红黑树与2-3-4树的等价性
上述第一节中,总是说红黑树是与2-3-4树等价的数据结构,下面,我来挖掘出他们的之间的等价性给你看,看看在红黑树上是否能看到2-3-4树的影子?ok,请看下图:
恩,yeah,不知你是否也看明白了:红黑树真的就是一种2-3-4树,为什么这么说呢?因为从上图中,你能轻易的看到,2-3-4树中的3-结点,和4-结点分裂后,的确就是红黑树中的结点元素形式了。
Ok,可能你还不相信,再送给你一幅图,从中,你是否已看出了丝毫端倪?:
在上面的图中,你可以清楚的看到图中左部分的2-3-4树最终能转换成一棵红黑树。不过,在上述情况下,红黑树最终将调整如下:
2.2、红黑树的插入操作
下图所示的代码是红黑树的插入操作代码:
在红黑树中,有一个非常重要的基础操作,那就是左旋与右旋,在本blog之前的红黑树系列已经对这两种情况进行过详尽的阐述,下图是左旋和右旋各自的操作及对应的代码:
而红黑树的左旋、右旋操作情况中与2-3-4树对应起来的情况如下图所示:
2.2.1、红黑树的插入情况一:父母是2-结点
2.2.2、红黑树的插入情况二:父母是3-结点
其余一切类似插入操作不再阐述。关于红黑树的删除操作在本blog内已经有所具体的阐述,本文不再叙述。全文完。
备注:本blog内的6篇红黑树文章如下:
初步了解红黑树,请看此文:教你透彻了解红黑树
关于红黑树的算法实现,请看此文(对红黑树的删除情况有比较清晰的阐述):红黑树算法的实现与剖析
红黑树的c源码实现,请看此文:红黑树的c源码实现与剖析
C++源码实现,请看此文:红黑树的c++完整实现源码
本红黑树系列中一篇重要的文章:红黑树插入和删除结点的全程演示
其余文章还有:一步一图一代码,R-B Tree
参考文献:
1、:Left-LeaningRed-BlackTrees,DagstuhlWorkshoponDataStructures,Wadern,Germany,February,2008.。可以在这里下载到:http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf。
2、本blog内6篇红黑树文章:红黑树(Red-Black Tree )。
版权所有,侵权必究。本blog内任何内容严禁用于任何商业用途,违者永久追究法律责任。
相关推荐
红黑树的发明者关于红黑树的演化过程的介绍,是最好的理解红黑树的资料。
红黑树C语言代码: #include "redblack.h" #include #include "fatal.h" 头文件: #include #include "fatal.h" typedef int ElementType; #define NegInfinity (-10000) #ifndef _RedBlack_H #define _Red...
红黑树(Red-Black Tree)是二叉搜索树(Binary Search Tree)的一种改进。我们知道二叉搜索树在最坏的情况下可能会变成一个链表(当所有节点按从小到大的顺序依次插入后)。而红黑树在每一次插入或删除节点 之后...
关于红黑树(Red-Black Tree)英文论文,全英文写作,分析全面,到位,结合当前新技术进展总结而成。
这一版代码个人认为99.99%正确,本人使用些结构及算法用于实现嵌入式迅雷Server的任务管理。此代码经本人学习研究之后从C语言版BT源代码中的宏定义式代码中分离出来,并做成一...希望对需要学习红黑树的人有帮助。
C#,红黑树(Red-Black Tree)的构造,插入、删除及修复、查找的算法与源代码 1 红黑树(Red-Black Tree) 如果二叉搜索树满足以下红黑属性,则它是红黑树: 每个节点不是红色就是黑色。 根是黑色的。 每片叶子(无...
红黑树 java代码
通用红黑树 说明: 用Linux内核红黑树封装的一个通用型的红黑树 如何使用该红黑树: 见rbtest1.c和rbtest2.c 直接make生成rbtest1和rbtest2 作者:rcyh 日期:2011年7月21日 ---------------------------------...
红黑树 这是Ada 2012对(一种自平衡二进制搜索树)的实现。 该树使用标准的Ada.Iterator_Interfaces进行迭代。 with Ada.Integer_Text_IO ; use Ada.Integer_Text_IO; with Ada.Text_IO ; use Ada.Text_IO; with ...
red-black-tree(delete).,关于红黑树删除方法的仔细讲解
红黑树的源代码,c语言版本。非常的详细。
:Christmas_tree: let tree = RedBlackTree . from ( increasing , range ( 100000 ) ) ; JavaScript的红黑树库。 请参阅。 父母是 。
红黑树(Red Black Tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 红黑树是一种特化的AVL树(平衡二叉树),都是在进行插入和删除操作时通过特定操作保持二叉树的...
红黑树的详细描述,从数据结构到创建,最小值,最大值,后继,遍历,插入以及删除。 该代码是clion IDE中实现的,代码全部在main.c中。
红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。
红黑树,详细的代码过程,完整的代码实现,希望对大家有帮助,第一次上传,为了赚积分,
红黑树的C语言实现
此工程主要包含红黑树的插入和删除,采用C++编写,有单独的.h和.cpp文件,方便移植
GNU的自平衡叉查找树的源代码库,包括AVL teee和红黑树 redblack tree、二叉查找树。还有PDF的原理说明及HTML的源代码函数解释。
用法实现BinaryTreeNode 要将值插入RedBlackTree ,其类型必须具有BinaryTreeNode的实例。 此类型类的成员必须实现Ord ,因此必须实现Eq ,以便可以在树中比较和排序值。 由于插入重复值可能会破坏树,因此此类型类...