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

阳光穿透心脏的1/2处 2022-12-11 15:27 136阅读 0赞

### 文章目录 ###

*   *  概念
     *   *  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树。  
![在这里插入图片描述][20201004103423741.png_pic_center]

图1-1

#### 2-3树的插入实现 ####

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

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

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

图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结点。  
![在这里插入图片描述][20201004110531288.png_pic_center]

图1-4

#### 2-3树的删除实现 ####

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

1.  所删除元素位于一个3结点的叶子节点上，这就最简单的，只要在该结点处删除该元素即可，不会影响到整棵树的其他节点结构，如图1-5所示，删除元素9，只需要将此结点改成只有元素10的2结点即可。  
    ![在这里插入图片描述][20201004124301935.png_pic_center]
    
    图1-5
2.  删除的元素位于一个2结点上，即要删除的是一个只有一个元素的结点。如果按照以前对树的理解，删除即可，可现在的2-3树的定义告诉我们这样做是行不通的，如图1-6所示，如果我们删除了结点1，那么结点4本来是一个2结点，此时他就不满足了，改变了树的结构。

![在这里插入图片描述][2020100412470251.png_pic_center]

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

情况一，此结点的双亲也是2结点，且拥有一个3结点的右孩子，如图1-7所示。删除结点1，那么只需要左旋转，也就是6成为双亲，4成为6的左孩子，7是6的右孩子。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70_pic_center 1]

图1-7

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

图1-8

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

图1-9

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

图1-10

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

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

图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);
    }

[20201004103423741.png_pic_center]: /images/20221123/fd1445f2298d4c65ac1817c6a0466d62.png
[20201004104553434.png_pic_center]: /images/20221123/cb89d91740de4132b0254340a8b0a53c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/5a987bd2c1aa4a33bceecc1bc51122f4.png
[20201004110531288.png_pic_center]: /images/20221123/e890d878481a406d8734fc150f0b2125.png
[20201004124301935.png_pic_center]: /images/20221123/8dea70c45750470b8a20f2cc57963cdb.png
[2020100412470251.png_pic_center]: /images/20221123/7be1bce5445c404282daabe4a687fbfa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/83eedfec71fa4f0eaa8116c95f404d77.png
[20201004125950400.png_pic_center]: /images/20221123/bddfc393bb4b4f13af5bc36107ab74c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/4cf240b48c7744c49ea58343a5da5186.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/e7097e342e054c2891443ef2d34656f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/1c14e97ef8a44dc083c0f27d12afc45c.png