平衡查找树之23查找树

2-3树

我们在二叉查找树中曾介绍过二叉查找树有可能会出现最坏的情况&＃xff0c;所有的结点变成了一条链。如图

我们当然希望我们能保存二叉查找树的平衡性&＃xff0c;但是在动态插入过程中保证树的完美平衡代价太大了。我们退而求其次&＃xff0c;学习一种新的数据结构。

 

相关定义&＃xff1a;

2-结点&＃xff1a;含有一个键&＃xff08;及对应值&＃xff09;和两条链接&＃xff0c;左链接指向2-3树中的键都小于该结点&＃xff0c;右链接指向2-3树中的键都大于该结点。

3-结点&＃xff1a;含有两个键&＃xff08;及对应的值&＃xff09;和三条链接&＃xff0c;左链接指向2-3树中的键都小于该结点&＃xff0c;中链接指向的2-3树中的键都位于该结点的两个键之间&＃xff0c;右链接指向2-3树中的键都大于该结点。

如图

一颗完美的2-3查找树中所有的空链接到根结点的距离都是相等的

 

 

查找

首先我们将一个键与根结点中的键比较&＃xff0c;如果他和其中任意一个相等&＃xff0c;则命中&＃xff1b;否则就根据比较的结果找到指向相应区域的链接&＃xff0c;并在其指向的子树中继续查找。如果是空链接&＃xff0c;则查找未命中。

对于左边的查找情况&＃xff0c;我们查找H&＃xff0c;发现他h

对于右边的情况&＃xff0c;我们查找B&＃xff0c;发现B

 

 

插入

我们分为4中情况讨论

 

向2-结点中插入新键

我们只需要把这个2-结点替换为一个3-结点即可。如图&＃xff0c;插入K

向一颗只含有一个3-结点的树中插入新键。

在考虑一般情况之前&＃xff0c;我们先考虑这样一种情况&＃xff0c;一棵树只有一个3-结点&＃xff0c;现在我们往里插入新键&＃xff0c;使它暂时变为一个4-结点&＃xff0c;而一个4结点可以很方便的转化为含有3个2-结点的2-3树&＃xff0c;只不过树高增加了1而已。这三个结点其中一个&＃xff08;跟&＃xff09;含有中键&＃xff0c;一个结点含有3个键中的最小者&＃xff08;左链接&＃xff09;&＃xff0c;一个含有最大者&＃xff08;右链接&＃xff09;

 

向一个父节点为2-结点的3-结点插入新键

我们先构建出一个临时的4-结点并将其分解&＃xff0c;但是我们不会为中键创建一个新结点&＃xff0c;而是将他移动到原来的父结点中。即将原来指向3-结点的链接替换为新父结点中的原中键左右两边的两条链接。&＃xff0c;这种转化不影响2-32树的主要性质

向一个父结点为3-结点的3-结点插入新键

我们和刚才一样构造一颗临时的4-结点然后分解他&＃xff0c;将他的中间插入到父结点中&＃xff0c;但是父结点也是一个3-结点&＃xff0c;因此我们继续构造一个临时的4-结点&＃xff0c;继续进行相同的变换。以此类推&＃xff0c;直到遇到一个2-结点或者到达3-结点的根

分解根结点

如果从插入结点到根结点的路径上全是3-结点&＃xff0c;我们的根结点就变成了一个临时的4-结点&＃xff0c;此时我们可以按照向一颗只含有一个3-结点的树中插入新键的方法处理&＃xff0c;将树高加1.这次变换仍然保持了树的性质

 

 

全局性质

上面介绍的变换不会影响树的全局有序性和平衡性&＃xff0c;任意空链接到根结点的距离都是相等的