欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

B树的插入操作

程序员文章站 2022-05-18 16:55:09
...

B树又称B-树

1.一棵M阶的B-树,每个节点最多有M个子树,(M-1)个Key。

2.若某个节点有N个Key,那这个节点就有N+1个子树P。 P0<Key(0)<P1, P0 < P1 < P3

3.当某个节点的Key个数大于等于(M-1)时,该节点需要被分裂;分裂时从中间的那个key为中点,分裂成左右两半;中间的key加入到它的父节点元素中,分裂出来的子树加入到父节点的孩子中;循环往复,直到所有节点都满足1,2两个条件。

#ifndef _BTREE_H_
#define _BTREE_H_

#define MAX_N (4)      // 4叉树

typedef int __INT64;
typedef unsigned int __UINT64;
typedef short __INT32;
typedef unsigned short __UINT32;
typedef char __INT8;
typedef unsigned char __UINT8;

typedef int ElementType;

typedef struct BTNode
{
    BTNode* parent;                   // 父节点
    __INT64 arr[MAX_N + 1];         // 数据
    __INT64 data_cnt;               // 数据个数
    BTNode* child[MAX_N + 2];         // 子树
}BTNode, *BTree;

class CBTree
{
// private variables
private:
    BTree m_pRoot;

// private functions
private:
    void AppendData(BTree &pRoot, ElementType data);
    void AppendTree(BTree &pRoot, BTree &pSubTree);
    __INT64 GetChildCount(const BTree& pRoot);
    // for debug
    void DispNode(const BTree &pRoot);
    BTree NewNode(const BTree &parent);
    void FreeNode(BTree &pRoot);
    __INT64 FindInsertPos(const BTree &pRoot, ElementType data);
    void SplitNode(BTree &pRoot);
    int FindChildTreePos(const BTree &pRoot);
    BTree MergeToParent(BTree &pRoot);
   
public:
    CBTree();
    ~CBTree();
    void InsertNode(ElementType data);
    void WidthFirstSearch();
    void DestroyTree();
};



#endif

#include "btree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <stdarg.h>
#include <time.h>
    
#include "stack.h"
#include "linklist.h"
#include "btree.h"

#define dbg(fmt, param...)                                      \
        do                                                      \
        {                                                       \
            printf("[%s:%d] "fmt, __FILE__, __LINE__, ##param); \
        }while(0)
    
// 计算数组总长度
#define ARRAY_SIZE(arr) sizeof((arr))/sizeof((arr[0]))

// 输出错误,结束进程
void err_print(const char *fmt, ...)
{
    char buff[256] = { 0 };
    va_list vlist;
    va_start(vlist, fmt);
    vsnprintf(buff, sizeof(buff) - 1, fmt, vlist);
    va_end(vlist);
    printf(buff);
    exit(0);
}

CBTree::CBTree()
{
    m_pRoot = NULL;
}

CBTree::~CBTree()
{
    DestroyTree();
}

// 添加数据,插入排序
void CBTree::AppendData(BTree &pRoot, ElementType data)
{
    if(pRoot->data_cnt >= ARRAY_SIZE(pRoot->arr))
    {
        err_print("data count:%d reached maximun count:%d, can't append data now\n", pRoot->data_cnt, ARRAY_SIZE(pRoot->arr));
    }
    if(pRoot->data_cnt == 0)
    {
        pRoot->arr[0] = data;
        pRoot->data_cnt = 1;
        return;
    }

    int i = 0;
    for(;i < pRoot->data_cnt; i++)
    {
        if(data < pRoot->arr[i])
        {
            for(int j = pRoot->data_cnt; j > i; j--)
            {
                pRoot->arr[j] = pRoot->arr[j - 1];
            }
            
            break;
        }
    }
    pRoot->arr[i] = data;
    pRoot->data_cnt++;
}

// 获取子树个数
__INT64 CBTree::GetChildCount(const BTree& pRoot)
{
    int count = 0;
    for(int i=0;i<ARRAY_SIZE(pRoot->child);i++)
    {
        if(pRoot->child[i])
        {
            count++;
        }
    }

    return count;
}

// for debug
void CBTree::DispNode(const BTree &pRoot)
{
    printf("head(%d):", pRoot->data_cnt);
    for(int i=0;i<pRoot->data_cnt;i++)
    {
        printf("%d ", pRoot->arr[i]);
    }
    printf("\n");
    for(int i=0;i<GetChildCount(pRoot);i++)
    {
        if(pRoot->child[i] != NULL)
        {
            printf(" child[%d]:", i);
            for(int j=0;j<pRoot->child[i]->data_cnt;j++)
            {
                printf("%d ", pRoot->child[i]->arr[j]);
            }
            printf("\n");
        }
    }
    printf("\n");
}

// 填加树,插入排序
void CBTree::AppendTree(BTree &pRoot, BTree &pSubTree)
{
    if(pRoot == NULL || pSubTree == NULL)
    {
        return;
    }
    if(pRoot->data_cnt == 0)
    {
        err_print("error! tree data count is 0\n");
    }
    
    int nChildCnt = GetChildCount(pRoot);
    if(nChildCnt == 0)
    {
        pRoot->child[0] = pSubTree;
        pSubTree->parent = pRoot;
        return;
    }

    int iSubTreeMax = 0;
    if(pSubTree->data_cnt > 0)
    {
        iSubTreeMax = pSubTree->arr[pSubTree->data_cnt - 1];
    }

    int i = 0;
    for(i = 0; i < nChildCnt; i++)
    {
        if(pRoot->child[i] != NULL)
        {
            BTree pItreeChild = pRoot->child[i];
            if(pItreeChild->data_cnt == 0)
            {
                err_print("error! tree data count shouldn't be 0\n");
            }


            int iMax = pItreeChild->arr[pItreeChild->data_cnt - 1];
            // 2=>升序1   _ 3 5
            if(iSubTreeMax < iMax)
            {
                for(int j = nChildCnt; j > i; j--)
                {
                    pRoot->child[j] = pRoot->child[j - 1];
                }

                break;
            }
        }
    }
    pRoot->child[i] = pSubTree;
    pSubTree->parent = pRoot;
}

// 申请新空节点
BTree CBTree::NewNode(const BTree &parent)
{
    BTree pNode = new BTNode;
    if(pNode == NULL)
    {
        return NULL;
    }

    for(int i=0;i<ARRAY_SIZE(pNode->arr);i++)
    {
        pNode->arr[i] = 0;
    }

    for(int i=0;i<ARRAY_SIZE(pNode->child);i++)
    {
        pNode->child[i] = NULL;
    }

    pNode->data_cnt = 0;
    pNode->parent = parent;

    return pNode;
}

// 释放当前节点
void CBTree::FreeNode(BTree &pRoot)
{
    if(pRoot)
    {
        for(int i=0;i<ARRAY_SIZE(pRoot->child); i++)
        {
            pRoot->child[i] = NULL;
        }
        pRoot->data_cnt = 0;
        pRoot->parent = NULL;
    
        delete pRoot;
        pRoot = NULL;
    }
}

// 查找插入位置
__INT64 CBTree::FindInsertPos(const BTree &pRoot, ElementType data)
{
    __INT64 idx = 0;
    for(idx = 0; idx < pRoot->data_cnt && idx < (MAX_N + 1); idx++)
    {
        if(data < pRoot->arr[idx])
        {
            return idx;
        }
    }
    return idx;
}

// 分裂树
void CBTree::SplitNode(BTree &pRoot)
{
    if(pRoot->data_cnt <= MAX_N)
    {
        printf("data_cnt not reach maximun, don't need to split node.\n");
        return;
    }

    __INT64 nMidDatIdx  = pRoot->data_cnt / 2;

    // 当前节点下生成2个新树
    BTree lpLeft  = NewNode(pRoot);   
    BTree lpRight = NewNode(pRoot);

    assert(lpLeft != NULL);
    assert(lpRight != NULL);


    // 重新分配数据
    for(__INT64 i = 0; i < nMidDatIdx; i++)
    {
        AppendData(lpLeft, pRoot->arr[i]);
    }

    for(__INT64 i = nMidDatIdx + 1; i < pRoot->data_cnt; i++)
    {
        AppendData(lpRight, pRoot->arr[i]);
    }

    pRoot->arr[0] = pRoot->arr[nMidDatIdx];
    pRoot->data_cnt = 1;

    // 重新分配子树
    __INT64 nChildCnt    = GetChildCount(pRoot);
    __INT64 nMidChildIdx = (lpLeft->data_cnt > lpRight->data_cnt) ? ((nChildCnt+1)/2) : nChildCnt/2;

    for(__INT64 i = 0;i < nMidChildIdx; i++)
    {
        AppendTree(lpLeft, pRoot->child[i]);
    }

    for(__INT64 i=nMidChildIdx; i<nChildCnt; i++)
    {
        AppendTree(lpRight, pRoot->child[i]);
    }

    // 清空子树
    for(__INT64 i = 0; i < ARRAY_SIZE(pRoot->child); i++)
    {
        pRoot->child[i] = NULL;
    }


    // 当前节点增加新生成的2棵子树
    AppendTree(pRoot, lpLeft);
    AppendTree(pRoot, lpRight);
}

// 查找当前节点是父节点的第几个树节点
int CBTree::FindChildTreePos(const BTree &pRoot)
{
    BTree hParent = pRoot->parent;
    for(__INT64 i = 0;i < ARRAY_SIZE(pRoot->child); i++)
    {
        if(hParent->child[i] != NULL &&
           hParent->child[i] == pRoot)
        {
            return i;
        }
    }
    return -1;
}

// 向上合入父节点
BTree CBTree::MergeToParent(BTree &pRoot)
{
    if(pRoot == NULL || pRoot->parent == NULL) // 没有父节点的时候,不用合入
    {
        return pRoot;
    }

    BTree hParent = pRoot->parent;             // 当前节点的父节点

    __INT64 child_pos = FindChildTreePos(pRoot);
    if(child_pos == -1)
    {
        err_print("can't find child pos, root data:%d.\n", pRoot->arr[0]);
    }
    
    // 置空子树在父节点中的位置
    int nParentChildCnt = GetChildCount(hParent);
    if(nParentChildCnt == 1)
    {
        hParent->child[0] = NULL;
    }
    else
    {
        for(int i = child_pos;i < nParentChildCnt - 1; i++)
        {
            hParent->child[i] = hParent->child[i + 1];
        }
        hParent->child[nParentChildCnt - 1] = NULL;
    }

    // 追加所有数据
    for(int i=0;i<pRoot->data_cnt;i++)
    {
        AppendData(hParent, pRoot->arr[i]);
        pRoot->arr[i] = 0;
    }
    pRoot->data_cnt = 0;

    // 追加所有子节点
    for(__INT64 i = 0; i < ARRAY_SIZE(pRoot->child); i++)
    {
        if(pRoot->child[i] != NULL)
        {
            AppendTree(hParent, pRoot->child[i]);
            pRoot->child[i] = NULL;
        }
    }
    
    // 释放节点
    FreeNode(pRoot);

    return hParent;
}

// 广度优先遍历
void CBTree::WidthFirstSearch()
{
    if(m_pRoot == NULL)
    {
        return;
    }

    char szPrtBuf[1024] = { 0 };

    CLinkList<BTree> treelist1;
    CLinkList<BTree> treelist2;

    treelist1.Pushback(m_pRoot);

    printf("======================================\n");
    printf("tree struct:\n");
    do
    {
        while(!treelist1.IsEmpty())
        {
            BTree pTreeNode = NULL;
            treelist1.GetHead(pTreeNode);
            treelist1.RemoveHead();
            if(pTreeNode == NULL)
            {
                continue;
            }
            char tmp[256] = "head:";
            strcat(szPrtBuf, tmp);
            for(int i=0;i<pTreeNode->data_cnt;i++)
            {
                snprintf(tmp, sizeof(tmp) - 1, "%d ", pTreeNode->arr[i]);
                strcat(szPrtBuf, tmp);
            }
            strcat(szPrtBuf, "\n");
            for(int i=0;i<ARRAY_SIZE(pTreeNode->child);i++)
            {
                if(pTreeNode->child[i])
                {
                    snprintf(tmp, sizeof(tmp) - 1, " child[%d]:", i);
                    strcat(szPrtBuf,tmp);
                    for(int j=0;j<pTreeNode->child[i]->data_cnt;j++)
                    {
                        snprintf(tmp, sizeof(tmp) - 1, "%d ",pTreeNode->child[i]->arr[j]);
                        strcat(szPrtBuf, tmp);
                    }
                    strcat(szPrtBuf, "\n");
                }
            }

            for(int i = 0; i < pTreeNode->data_cnt; i++)
            {
                printf("%d ", pTreeNode->arr[i]);
            }
            printf(",");

            for(int i = 0;i < ARRAY_SIZE(pTreeNode->child); i++)
            {
                if(pTreeNode->child[i] != NULL)
                {
                    treelist2.Pushback(pTreeNode->child[i]);
                }
            }
        }
        printf("\n");

        while(!treelist2.IsEmpty())
        {
            BTree pTreeNode = NULL;
            treelist2.GetHead(pTreeNode);
            treelist2.RemoveHead();
            if(pTreeNode == NULL)
            {
                continue;
            }

            char tmp[256] = "head:";
            strcat(szPrtBuf, tmp);
            for(int i=0;i<pTreeNode->data_cnt;i++)
            {
                snprintf(tmp, sizeof(tmp) - 1, "%d ", pTreeNode->arr[i]);
                strcat(szPrtBuf, tmp);
            }
            strcat(szPrtBuf, "\n");
            for(int i=0;i<ARRAY_SIZE(pTreeNode->child);i++)
            {
                if(pTreeNode->child[i])
                {
                    snprintf(tmp, sizeof(tmp) - 1, " child[%d]:", i);
                    strcat(szPrtBuf,tmp);
                    for(int j=0;j<pTreeNode->child[i]->data_cnt;j++)
                    {
                        snprintf(tmp, sizeof(tmp) - 1, "%d ",pTreeNode->child[i]->arr[j]);
                        strcat(szPrtBuf, tmp);
                    }
                    strcat(szPrtBuf, "\n");
                }
            }


            for(int i=0;i<pTreeNode->data_cnt;i++)
            {
                printf("%d ", pTreeNode->arr[i]);
            }
            printf(",");
            for(int i = 0;i < ARRAY_SIZE(pTreeNode->child); i++)
            {
                if(pTreeNode->child[i] != NULL)
                {
                    treelist1.Pushback(pTreeNode->child[i]);
                }
            }
        }
        printf("\n");
    }while(!treelist1.IsEmpty() || !treelist2.IsEmpty());

    printf("tree nodes:\n%s", szPrtBuf);
    printf("======================================\n");
}

// 插入节点
void CBTree::InsertNode(ElementType data)
{
    if(m_pRoot == NULL)
    {
        m_pRoot = NewNode(NULL);
        AppendData(m_pRoot, data);
        return;
    }
    printf("Insert Data:%d\n", data);

    assert(m_pRoot != NULL);

    BTree pHead = m_pRoot;
    while(pHead)
    {
        if(pHead->data_cnt == 0)
        {
            AppendData(pHead, data);
            break;
        }
        else
        {
            __INT64 ins_pos = FindInsertPos(pHead, data);
            if(ins_pos > MAX_N)
            {
                err_print("findinsert pos err, ins_pos out of max range\n");
            }
            //DispNode(pHead);
            //printf("ins pos = %d\n", ins_pos);
            // 对应的子树存在则到跳到子树,否则直接插入
            if(pHead->child[ins_pos])
            {
                pHead = pHead->child[ins_pos];
            }
            else
            {
                AppendData(pHead, data);
                while(pHead && pHead->data_cnt > MAX_N)
                {
                    SplitNode(pHead);                  // 分裂当前节点
                    pHead = MergeToParent(pHead);      // 当前节点合入父节点
                }
                break;
            }
       }
    }
    WidthFirstSearch();
}

void CBTree::DestroyTree()
{
    if(m_pRoot == NULL)
    {
        return;
    }

    printf("destroying tree\n");

    CStack<BTree> nodeStack;
    nodeStack.Push(m_pRoot);

    while(!nodeStack.isEmpty())
    {
        BTree top = NULL;
        nodeStack.Pop(top);
        if(top)
        {
            for(int i=0;i<ARRAY_SIZE(top->child);i++)
            {
                if(top->child[i] != NULL)
                {
                    nodeStack.Push(top->child[i]);
                }
            }
            DispNode(top);
            FreeNode(top);
        }
    }
    m_pRoot = NULL;
}



相关标签: B树