【数据结构】详解多路查找树之2-3树

文章目录

概念2-3树2-3树的插入实现2-3树的删除实现 测试代码

概念

我们之前学习的树，都是一个结点可以有多个孩子，但是自身只存储一个元素。二叉树的限制会更多，节点最多只能有两个孩子。

一个结点只能存储一个元素，在元素非常多的时候，就使得要么树的度非常大（结点拥有子树的最大值），要么树的度非常大，甚至两者都必须足够大才行，这就使得内存存取外存次数非常多，这显然成了时间效率上的瓶颈，这迫使我们要打破每一个结点只存储一个元素的限制，为此引入了多路查找树的概念。

多路查找树（muitl-way search tree）:其每一个结点的孩子数可以多于两个，且每个结点处可以存储多个元素。 由于它是查找树，所有元素之间存在某种特定的排序关系。

2-3树

2-3树是一颗多路查找树：其中的每一个结点都具有两个孩子（称为2结点）或三个孩子（3结点）。

一个2结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树相似。左子树包含元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同的是，这个2结点要么没有孩子，要有就是两个孩子，不能只有一个孩子。

一个3结点包含一小一大两个元素的和三个孩子（或没有孩子） 一个三结点要么没有孩子，要么具有三个孩子。如果某3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。

并且2-3树中所有的叶子都在同一层次上。如图1-1所示，就是一颗有效的2-3树。

图1-1

2-3树的插入实现

对于2-3树的插入来说，与二叉排序树相同，插入操作一定是发生在叶子结点上，与二叉排序树不同的是，2-3树插入一个元素的过程有可能会对该树的其余结构产生连锁反应。

2-3树插入可以分为三种情况。

对于空树，插入一个2结点即可。

插入到一个2结点的叶子上，应该说，由于其本身就只有一个元素，所以只需要将其升级为3结点即可。如图1-2所示。我们希望从左图的2-3树中插入元素3，根据遍历可知，3比8小，比4小，于是就只能考虑叶子节点1所在的位置，因此很自然的想法就是将此结点变成一个3结点，即右图这样完成插入操作。当然要视插入的元素与当前叶子节点的元素比较大小后，决定谁在左，谁在右。

图1-2

要往3结点中插入一个新元素。因为3结点本身已经是2-3树的结点最大容量（已经有两个元素），因此就需要将其拆分，且将树中两元素或插入元素三者中选择其一向上移动一层。

第一种情况，如图1-3所示，现在需要向左图中插入元素5。经遍历得到元素5比8小比4大，因此它应该是需要插入在拥有6,7元素的3结点位置。问题就，在于6和7结点已经是3结点，不能在加，此时发现他的双亲结点4是一个2结点。因此考虑将它升级为3结点，这样他就得有三个孩子，于是想到，将6,7结点拆分，让6与4成为3的结点，将5成为他的中间孩子，将7成为他的右孩子。

图1-3

另外一种情况，如图1-4所示，需要向图中插入元素11,。经过遍历得到元素11比12,14小，比9，10大，因此他应该说是需要插入拥有9,10元素的3结点位置。同样的道理，9,10结点不能在增加节点，此时发现他的双亲结点12,14也是一个3结点，也不能在插入元素了，再往上看12,14结点的双亲，节点8是个2节点，于是就想到了，将9,10拆分，12,14也拆分，让根结点8升级为3结点。

图1-4

2-3树的删除实现

2-3树的删除也分为3种情况，与插入相反，我们从3结点开始说。

所删除元素位于一个3结点的叶子节点上，这就最简单的，只要在该结点处删除该元素即可，不会影响到整棵树的其他节点结构，如图1-5所示，删除元素9，只需要将此结点改成只有元素10的2结点即可。

图1-5

删除的元素位于一个2结点上，即要删除的是一个只有一个元素的结点。如果按照以前对树的理解，删除即可，可现在的2-3树的定义告诉我们这样做是行不通的，如图1-6所示，如果我们删除了结点1，那么结点4本来是一个2结点，此时他就不满足了，改变了树的结构。

图1-6 因此，对于删除叶子是2结点的情况，我们需要分四种情形来处理。

情况一，此结点的双亲也是2结点，且拥有一个3结点的右孩子，如图1-7所示。删除结点1，那么只需要左旋转，也就是6成为双亲，4成为6的左孩子，7是6的右孩子。

图1-7

情况二，此结点的双亲是2结点，他的右孩子也是2结点，如图1-8所示，此时删除结点1，如果直接左旋转会造成没有右孩子，因此需要对整棵树进行变形，办法就是，我们目标是让结点7变成3结点，那就要让比7稍大的元素8下来，随即就得让比元素8稍大的元素9补充结点8的位置，于是就出现了中间的那幅图，再利用左旋转的方式，变成了右图的结果。

图1-8

情况三，此结点的双亲是一个3结点，如图1-9所示，此时删除结点10，意味着双亲12,14这个结点不能成为3结点了，于是将此结点拆分，并将12与13合并成左孩子。

图1-9

情况四，如果当前树是一个满二叉树的情况，此时删除任何一个叶子都会使得整棵树不满足2-3树的定义，如图1-10所示，删除叶子节点8（其实删除任何一个结点都一样）就不得不考虑将2-3的层数减少，办法是将8的双亲和其左子树6合并为一个3结点，再将14与9合并为3结点。

图1-10

要删除的元素位于非叶子节点的分支结点，通常是将树中序遍历后得到此元素的前驱或者后继。

如果我们要删除的分支结点是2结点，如图1-11所示，我们要删除界定4，分析后得到他的前驱是1后继是6，显然，由于6,7,是3结点，只需要用6来补位即可。

图1-11

测试代码

#include <stdio.h> #include <malloc.h> #include <memory.h> #define NUM(p) ((p==NULL)?0:p->num) typedef struct node { int a[3]; int num; //1,2,3 struct node *left_child; struct node *mid_child; struct node *right_child; struct node *tmp_child; struct node *parent; } Btree, *BtreePtr; void exchange(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } BtreePtr _node(const int key) { BtreePtr p = (BtreePtr)malloc(sizeof(Btree)); if (p != NULL) { memset(p, 0, sizeof(p)); p->a[0] = key; p->num = 1; p->left_child = NULL; p->right_child = NULL; p->mid_child = NULL; p->tmp_child = NULL; p->parent = NULL; } else { puts("内存不足"); } return p; } void _sort(BtreePtr b) { int length = b->num; for (int i = 0; i < length; i++) { for (int j = i; j < length; j++) { if ((b->a[j]) < (b->a[i])) { exchange(&(b->a[j]), &(b->a[i])); } } } } BtreePtr _checkNum(BtreePtr p) { if (NUM(p) == 1) { //2-结点 if (NUM(p->left_child) == 3) { //case 2 p->a[1] = p->left_child->a[1]; p->num++; _sort(p); BtreePtr l = _node(p->left_child->a[0]); l->left_child = p->left_child->left_child; l->parent = p; BtreePtr r = _node(p->left_child->a[2]); r->left_child = p->left_child->mid_child; r->right_child = p->left_child->right_child; r->parent = p; p->left_child = l; p->mid_child = r; } else if (NUM(p->right_child) == 3) { //case 3 p->a[1] = p->right_child->a[1]; p->num++; _sort(p); BtreePtr l = _node(p->right_child->a[0]); l->left_child = p->right_child->left_child; l->parent = p; BtreePtr r = _node(p->right_child->a[2]); r->left_child = p->right_child->mid_child; r->right_child = p->right_child->right_child; r->parent = p; p->mid_child = l; p->right_child = r; } } else if (NUM(p) == 2) { //3-结点 if (NUM(p->left_child) == 3) { //case 4 p->a[2] = p->left_child->a[1]; p->num++; _sort(p); p->tmp_child = p->mid_child; p->mid_child = _node(p->left_child->a[2]); BtreePtr l = _node(p->left_child->a[0]); l->left_child = p->left_child->left_child; l->right_child = p->left_child->mid_child; l->parent = p; BtreePtr r = _node(p->left_child->a[2]); r->left_child = p->left_child->tmp_child; r->right_child = p->left_child->right_child; r->parent = p; p->left_child = l; } else if (NUM(p->right_child) == 3) { //case 5 p->a[2] = p->right_child->a[1]; p->num++; _sort(p); p->tmp_child = _node(p->right_child->a[2]); // BtreePtr l = _node(p->right_child->a[0]); l->right_child = p->right_child->left_child; l->right_child = p->right_child->mid_child; l->parent = p; BtreePtr r = _node(p->right_child->a[2]); r->right_child = p->right_child->tmp_child; r->right_child = p->right_child->right_child; r->parent = p; p->right_child = l; } else if (NUM(p->mid_child) == 3) { p->a[2] = p->mid_child->a[1]; p->num++; _sort(p); //p->tmp_child = p->mid_child; //p->mid_child = _node(p->left_child->a[2]); BtreePtr l = _node(p->mid_child->a[0]); l->left_child = p->mid_child->left_child; l->right_child = p->mid_child->mid_child; l->parent = p; BtreePtr r = _node(p->mid_child->a[2]); r->left_child = p->mid_child->tmp_child; r->right_child = p->mid_child->right_child; r->parent = p; p->mid_child = l; p->tmp_child = r; } } if (p->num == 3) { if (p->parent == NULL) { // case 1; BtreePtr t = p->left_child; p->left_child = _node(p->a[0]); p->left_child->left_child = t; p->left_child->right_child = p->mid_child; p->left_child->parent = p; t = p->right_child; p->right_child = _node(p->a[2]); p->right_child->left_child = p->tmp_child; p->right_child->right_child = t; p->right_child->parent = p; p->mid_child = NULL; p->tmp_child = NULL; p->a[0] = p->a[1]; p->num = p->num - 2; } } return p; } BtreePtr _insertBTree(BtreePtr b, const int key, const int pos) { if (b->left_child == NULL && b->right_child == NULL) { //底节点 b->a[b->num] = key; b->num++; _sort(b); } else { if (b->num == 1) { if (key < b->a[0]) { //num =1, 2 b->left_child = _insertBTree(b->left_child, key, pos); } else if (key > b->a[0]) { //num = 2 b->right_child = _insertBTree(b->right_child, key, pos); } } else if (b->num == 2) { if (key < b->a[0]) { //num =1, 2 b->left_child = _insertBTree(b->left_child, key, pos); } else if (key > b->a[1]) { //num = 2 b->right_child = _insertBTree(b->right_child, key, pos); } else { b->mid_child = _insertBTree(b->mid_child, key, pos); } } } b = _checkNum(b); return b; } BtreePtr insertBTree(BtreePtr root, const int key, const int pos) { if (root == NULL) { root = _node(key); } else { root = _insertBTree(root, key, pos); } return root; } void freeTree(BtreePtr p) { if (p->left_child != NULL) { freeTree(p->left_child); } if (p->right_child != NULL) { freeTree(p->right_child); } if (p->mid_child != NULL) { freeTree(p->mid_child); } free(p); p = NULL; } int BTreeSearch(const int *a, const int length, const int key) { BtreePtr root = NULL; for (int i = 0; i < length; i++) { root = insertBTree(root, a[i], i); } freeTree(root); return -1; } void main() { const int length = 8; int my_array[8] = { 7, 5, 9 ,11,10,6, 12, 13}; BTreeSearch(my_array, length, 7); }