【数据结构】中B树的插入,删除,遍历

桃扇骨 2022-06-16 10:14 128阅读 0赞

## B树的定义： ##

1、根节点至少有两个分支  
2、除了根节点以外，所有节点的关键字个数至少为M/2个，最多为M-1  
3、每个节点的度数均是关键字数加一  
4、所有的叶子节点都在同一层  
插入：  
我们设计节点的结构如下：

#define M 5
    #define  MAX M - 1
    #define MIN M/2
    typedef char KeyType;
    
    typedef struct {}Record;
    
    typedef struct ElemType
    {
        KeyType key;
        Record *recptr;
    }ElemType;
    
    typedef struct BNode
    {
        int num;
        BNode *parent;
        ElemType data[M+1];
        BNode*sub[M+1];
    }BNode,*BTree;
    
    //查找函数的返回值类型
    typedef struct Result
    {
        bool tag;
        BNode*pnode;
        int index;
    }Result;
    
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17 
         18 
         19 
         20 
         21 
         22 
         23 
         24 
         25 
         26 
         27 
         28 
         29 
         30 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17 
         18 
         19 
         20 
         21 
         22 
         23 
         24 
         25 
         26 
         27 
         28 
         29 
         30

插入代码：  
当以个节点的个数大于MAX时就分裂，如果根节点分裂会产生新根，否则就将分裂出来的节点插入到双亲中，如果双亲又大于MAX就继续分裂，这样就能保证B树的定义的正确性，代码如下：

ElemType MoveItem(BNode*ptr, BNode *s, int pos)
    {
        int tmp = ptr->num;
        for (int i = pos + 1, j = 0; i <= tmp; i++, j++)
        {
            s->data[j] = ptr->data[i];
            s->sub[j] = ptr->sub[i];
            if (ptr->sub[i] != NULL)
            {
          
                s->sub[j]->parent = s;
            }
        }
        s->parent = ptr->parent;
        s->num = ptr->num = MIN;
        return s->data[0];
    
    }
    BNode * MakeRoot(ElemType x, BNode *left, BNode *right)
    {
        BNode *s = BuyNode();
        s->num = 1;
        s->data[1] = x;
        s->sub[0] = left;
        if (left != NULL)
            left->parent = s;
        s->sub[1] = right;
        if (right != NULL)
            right->parent = s;
        return s;
    }
    bool InsertItem(BNode*ptr, int pos, ElemType e, BNode*right);
    BNode *Splice(BNode*ptr)
    {
        BNode *s = BuyNode();
        ElemType e = MoveItem(ptr, s, MIN);
    
        if (ptr->parent == NULL)
        {
            return MakeRoot(e,ptr, s);
        }
        else
        {
            ptr = ptr->parent;
            int i = ptr->num;
            ptr->data[0] = e;//这句很关键，如果ptr->data[0]未设置就会和0位置比较还没有结果，插入位置就会出错
            while (ptr->data[i].key > s->data[0].key) --i;
            InsertItem(ptr, i + 1, s->data[0], s);
            if (ptr->num > MAX)
            {
                return Splice(ptr);
            }
            return NULL;
        }
    }
    bool InsertItem(BNode*ptr, int pos, ElemType e, BNode*right)//BNode&node
    {
    
        for (int i = ptr->num; i >= pos; --i)
        {
            ptr->data[i + 1] = ptr->data[i];
            ptr->sub[i + 1] = ptr->sub[i];
        }
        //
        ptr->data[pos] = e;
        ptr->sub[pos] = right;
        if (right != NULL)
        {
            right->parent = ptr;
        }//
        ptr->num += 1;
    
        return true;
    }
    bool Insert(BTree *ptr, ElemType e)
    {
        if (ptr == NULL)
            return false;
        if (*ptr == NULL)
        {
            *ptr = MakeRoot(e, NULL, NULL);
            return true;
        }
        Result res=FindValue(*ptr, e.key);
        if (res.pnode == NULL || res.tag) return false;
        InsertItem(res.pnode, res.index+1, e, NULL);
        if (res.pnode->num > MAX)
        {
            BNode*p = Splice(res.pnode);
            if (p != NULL)
            {
                *ptr = p;
            }
        }
        return true;
    }
    
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17 
         18 
         19 
         20 
         21 
         22 
         23 
         24 
         25 
         26 
         27 
         28 
         29 
         30 
         31 
         32 
         33 
         34 
         35 
         36 
         37 
         38 
         39 
         40 
         41 
         42 
         43 
         44 
         45 
         46 
         47 
         48 
         49 
         50 
         51 
         52 
         53 
         54 
         55 
         56 
         57 
         58 
         59 
         60 
         61 
         62 
         63 
         64 
         65 
         66 
         67 
         68 
         69 
         70 
         71 
         72 
         73 
         74 
         75 
         76 
         77 
         78 
         79 
         80 
         81 
         82 
         83 
         84 
         85 
         86 
         87 
         88 
         89 
         90 
         91 
         92 
         93 
         94 
         95 
         96 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17 
         18 
         19 
         20 
         21 
         22 
         23 
         24 
         25 
         26 
         27 
         28 
         29 
         30 
         31 
         32 
         33 
         34 
         35 
         36 
         37 
         38 
         39 
         40 
         41 
         42 
         43 
         44 
         45 
         46 
         47 
         48 
         49 
         50 
         51 
         52 
         53 
         54 
         55 
         56 
         57 
         58 
         59 
         60 
         61 
         62 
         63 
         64 
         65 
         66 
         67 
         68 
         69 
         70 
         71 
         72 
         73 
         74 
         75 
         76 
         77 
         78 
         79 
         80 
         81 
         82 
         83 
         84 
         85 
         86 
         87 
         88 
         89 
         90 
         91 
         92 
         93 
         94 
         95 
         96

辅助函数：

BNode* BuyNode()
    {
        BNode *node = new BNode();
        if (node == NULL)
            exit(-1);
        memset(node, 0, sizeof(BNode));
        return node;
    }
    
    
    Result FindValue(BNode*ptr, KeyType e)
    {
        Result res = { false, NULL, -1 };
        while (ptr != NULL)
        {
            int i = ptr->num;
            ptr->data[0].key = e;
            while (ptr->data[i].key > e) --i;
            res.pnode = ptr;
            res.index = i;
            if (i != 0 && ptr->data[i].key == e)
            {
                res.tag = true;
                break;
            }
            else
                ptr = ptr->sub[i];
        }
        return res;
    }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17 
         18 
         19 
         20 
         21 
         22 
         23 
         24 
         25 
         26 
         27 
         28 
         29 
         30 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17 
         18 
         19 
         20 
         21 
         22 
         23 
         24 
         25 
         26 
         27 
         28 
         29 
         30

## B树的删除 ##

B树的删除，我们将带有分支的节点中的关键码删除，用他的前驱和后继替换掉这个被删除的关键码，然后删除前驱或者后继，删除前驱或者后继之后，会出现与B树定义不相符的情况，比如关键码个数小于MIN的情况，这个时候就要做相应的旋转，如过旋转不了就只有进行节点的合并，合并有可能会产生新根，代码如下：

//找前驱
    BNode *FindPre(BNode*ptr)
    {
        while (ptr!=NULL&&ptr->sub[ptr->num] != NULL)
        {
          
            ptr = ptr->sub[ptr->num];
        }
        return ptr;
    }
    //找后继
    BNode *FindNext(BNode*ptr)
    {
        while (ptr != NULL&&ptr->sub[0] != NULL)
        {
          
            ptr = ptr->sub[0];
        }
        return ptr;
    }
    //删除叶子结点
    void DelLeafItem(BNode *ptr, int pos)
    {
        for (int i = pos; i < ptr->num; i++)
        {
            ptr->data[i] = ptr->data[i + 1];
            ptr->sub[i] = ptr->sub[i + 1];
        }
        ptr->num -= 1;
    }
    //右旋转
    void RightRotateLeaf(BNode *leftbro, BNode*ptr, BNode *parent, int pos)
    {
        ptr->data[0] = parent->data[pos];
        for (int i = ptr->num; i >= 0; i--)
        {
            ptr->data[i + 1] = ptr->data[i];
            ptr->sub[i + 1] = ptr->sub[i];
        }
        ptr->num += 1;
        ptr->sub[0] = leftbro->sub[leftbro->num];
        if (ptr->sub[0] != NULL)//
        {
          
            ptr->sub[0]->parent = ptr;
        }
        parent->data[pos] = leftbro->data[leftbro->num];
        leftbro->num -= 1;
    }
    //左旋转
    void LeftRotateLeaf(BNode *rightbro,BNode *ptr,BNode *parent,int pos)
    {
        ptr ->data[ptr->num+1] = parent->data[pos + 1];
        ptr->sub[ptr->num + 1] = rightbro->sub[0];
        if (ptr->sub[ptr->num+1]!=NULL)
        {
          
            ptr->sub[ptr->num + 1]->parent = ptr;
        }
        ptr->num += 1;
        parent->data[pos + 1] = rightbro->data[1];
    
        for (int i =0; i < rightbro->num; i++)
        {
            rightbro->data[i] = rightbro->data[i + 1];
            rightbro->sub[i] = rightbro->sub[i + 1];
        }
        rightbro->num -= 1;
    
    }
    //向左合并
    void LeftMerge(BNode*leftbro, BNode*ptr, BNode*parent, int pos)
    {
        ptr->data[0] = parent->data[pos];
        for (int i = 0,j=leftbro->num+1; i <= ptr->num; i++,j++)
        {
            leftbro->data[j] = ptr->data[i];
            leftbro->sub[j] = ptr->sub[i];
            if (leftbro->sub[j] != NULL)
            {
          
                leftbro->sub[j]->parent = leftbro;
            }
        }
        leftbro->num = leftbro->num + ptr->num + 1;
        free(ptr);
        DelLeafItem(parent, pos);
    
    }
    //向右合并
    void RightMerge(BNode *ptr, BNode *rightbro, BNode *parent, int pos)
    {
         LeftMerge(ptr, rightbro, parent, pos+1);
    }
    //出现小于MIN的情况的调整函数
    BNode *AdjusLeaf(BNode*ptr)
    {
        BNode*parent = ptr->parent;
        int pos = 0;
        while (parent->sub[pos] != ptr) ++pos;
    
        BNode*leftbro = pos-1<0?NULL:parent->sub[pos-1];
        BNode*rightbro = pos+1>=MAX?NULL:parent->sub[pos+1];
    
        if (leftbro!=NULL&&leftbro->num>MIN)
        {
            RightRotateLeaf(leftbro,ptr,parent,pos);
        }
        else if (rightbro!=NULL&&rightbro->num>MIN)
        {
            LeftRotateLeaf(rightbro, ptr,parent, pos);
        }
        else if(leftbro!=NULL)
        {
            LeftMerge(leftbro, ptr, parent, pos);
            ptr = leftbro;
        }
        else if (rightbro != NULL)
        {
             RightMerge(ptr, rightbro, parent, pos);
            // ptr = rightbro;
        }
        if (parent->parent != NULL&&parent->num < MIN)
        {
            return AdjusLeaf(parent);
        }
        if (parent->parent == NULL&&parent->num <= 0)
        {
            free(parent);
            ptr->parent = NULL;
            return ptr;
        }
        return NULL;
    
    }
    //删除函数
    void ReMove(BNode*&root, KeyType e)
    {
        if (root == NULL)
            return;
        Result res = FindValue(root, e);
        if (res.pnode == NULL || res.tag==false) return;
    
        BNode *ptr = res.pnode;
        int pos = res.index;
        BNode*pre = FindPre(ptr->sub[pos-1]);
        BNode*next = FindNext(ptr->sub[pos]);
        if (pre != NULL&&pre->num > MIN)
        {
            ptr->data[pos] = pre->data[pre->num];
            ptr = pre;
            pos = pre->num;
        }
        else if (next != NULL&&next->num > MIN)
        {
            ptr->data[pos] = next->data[1];
            ptr = next;
            pos = 1;
        }
        else if (pre != NULL)
        {
            ptr->data[pos] = pre->data[pre->num];
            ptr = pre;
            pos = pre->num;
        }
        else if (next != NULL)
        {
            ptr->data[pos] = next->data[1];
            ptr = next;
            pos = 1;
        }
        DelLeafItem(ptr, pos);//
        if (ptr->parent != NULL&&ptr->num < MIN)
        {
            BNode*newroot = AdjusLeaf(ptr);
            if (newroot != NULL)
            {
                root = newroot;
            }
        }
        else if (ptr->parent == NULL&&ptr->num <= 0)
        {
            free(root);
            root = NULL;
        }
    }
    
    
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17 
         18 
         19 
         20 
         21 
         22 
         23 
         24 
         25 
         26 
         27 
         28 
         29 
         30 
         31 
         32 
         33 
         34 
         35 
         36 
         37 
         38 
         39 
         40 
         41 
         42 
         43 
         44 
         45 
         46 
         47 
         48 
         49 
         50 
         51 
         52 
         53 
         54 
         55 
         56 
         57 
         58 
         59 
         60 
         61 
         62 
         63 
         64 
         65 
         66 
         67 
         68 
         69 
         70 
         71 
         72 
         73 
         74 
         75 
         76 
         77 
         78 
         79 
         80 
         81 
         82 
         83 
         84 
         85 
         86 
         87 
         88 
         89 
         90 
         91 
         92 
         93 
         94 
         95 
         96 
         97 
         98 
         99 
         100 
         101 
         102 
         103 
         104 
         105 
         106 
         107 
         108 
         109 
         110 
         111 
         112 
         113 
         114 
         115 
         116 
         117 
         118 
         119 
         120 
         121 
         122 
         123 
         124 
         125 
         126 
         127 
         128 
         129 
         130 
         131 
         132 
         133 
         134 
         135 
         136 
         137 
         138 
         139 
         140 
         141 
         142 
         143 
         144 
         145 
         146 
         147 
         148 
         149 
         150 
         151 
         152 
         153 
         154 
         155 
         156 
         157 
         158 
         159 
         160 
         161 
         162 
         163 
         164 
         165 
         166 
         167 
         168 
         169 
         170 
         171 
         172 
         173 
         174 
         175 
         176 
         177 
         178 
         179 
         180 
         181 
         182 
         183 
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
         14 
         15 
         16 
         17 
         18 
         19 
         20 
         21 
         22 
         23 
         24 
         25 
         26 
         27 
         28 
         29 
         30 
         31 
         32 
         33 
         34 
         35 
         36 
         37 
         38 
         39 
         40 
         41 
         42 
         43 
         44 
         45 
         46 
         47 
         48 
         49 
         50 
         51 
         52 
         53 
         54 
         55 
         56 
         57 
         58 
         59 
         60 
         61 
         62 
         63 
         64 
         65 
         66 
         67 
         68 
         69 
         70 
         71 
         72 
         73 
         74 
         75 
         76 
         77 
         78 
         79 
         80 
         81 
         82 
         83 
         84 
         85 
         86 
         87 
         88 
         89 
         90 
         91 
         92 
         93 
         94 
         95 
         96 
         97 
         98 
         99 
         100 
         101 
         102 
         103 
         104 
         105 
         106 
         107 
         108 
         109 
         110 
         111 
         112 
         113 
         114 
         115 
         116 
         117 
         118 
         119 
         120 
         121 
         122 
         123 
         124 
         125 
         126 
         127 
         128 
         129 
         130 
         131 
         132 
         133 
         134 
         135 
         136 
         137 
         138 
         139 
         140 
         141 
         142 
         143 
         144 
         145 
         146 
         147 
         148 
         149 
         150 
         151 
         152 
         153 
         154 
         155 
         156 
         157 
         158 
         159 
         160 
         161 
         162 
         163 
         164 
         165 
         166 
         167 
         168 
         169 
         170 
         171 
         172 
         173 
         174 
         175 
         176 
         177 
         178 
         179 
         180 
         181 
         182 
         183

## B树的遍历 ##

利用递归的特性 ，代码十分简洁，先递归到最左边，然后打印一个关键码就遍历一个分支，代码如下：

void InOder(BNode*root)
    {
        if (root != NULL)
        {
            InOder(root->sub[0]);
            for (int i = 1; i <= root->num; i++)
            {
                cout << root->data[i].key;
                InOder(root->sub[i]);
            }
        }
    }
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13 
        
       
        
        
         
       
        
       
        
         1 
         2 
         3 
         4 
         5 
         6 
         7 
         8 
         9 
         10 
         11 
         12 
         13