歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

B樹——思路、及C語言代碼的實現

0.序

  本人現讀本科大二,這學期學習數據結構,老師為我們的期末作業布置一道任選題,而我一直以來都有聽說B樹是一棵挺神奇的樹,所以我選擇了它,當然更重要的原因是因為B樹的難度最高,我喜歡做有挑戰性的工作。同時,我聽我基友說他熱衷於將自己所學所想分享到博客園上,故才有了這樣一篇文章。希望我能夠在寫博客的同時學習到更多東西,同時也能幫助到其他遇到或者即將遇到雷同問題的初學者們。

1.關於B樹

  B樹是一種稱之為查找樹的樹,與之類似的有查找二叉樹,平衡二叉樹,除此之外,還有各種B樹的兄弟姐妹B+樹、B-樹、B*樹等,他們共同的特點就是都是按照一定的順序規律存儲的。B樹的應用也是很廣泛的,B樹是幾乎所有數據庫的默認索引結構,也是用的最多的索引結構。B樹是一種多叉樹,根據其最多叉的數目可以直接稱為M階B樹。根據算法導論上敘述,還可按B樹每個節點最少的分支確定一棵B樹的階,但是這樣的話B樹的階便必須為偶數。我個人是使用根據最大分支的數目確定B樹的階的。

  下圖就是某一棵B樹,每一個結點中都包含有數個數據元素,而同時一定會有數據元素的個數加一個的子樹。

  一棵M階B樹或為空樹,或為滿足下列特性的M叉樹:

(1)樹中每個結點最多含有M棵子樹;

(2)若根結點不是葉子結點,則至少有2棵子樹;

(3)除根結點之外的所有非終端結點至少有[m/2]棵子樹;

(4)每個非終端結點中包含的信息keynum,ptr[0],key[1],ptr[1],key[2],ptr[2],……key[keynum],ptr[keynum];

  其中,key為關鍵字,且關鍵字按升序排序,ptr為指向子樹的根結點指針

2.思路及實現

  B樹的接口主要是插入(包括空樹插入一個元素)和刪除操作,而插入和刪除操作不可避免的都會用到查找操作,而查找的主要思路比較簡單,主要是利用B樹是一種排序樹的原理,可以很快找到要插入位置或者要刪除結點。這裡的關鍵是注意返回內容包括查找結果所在結點,以及該元素所在位置,這是為了方便接下來的操作比較簡單。

插入:

  通過對B樹進行遍歷,找出要插入的結點以及結點位置,如果找到的key值在B樹當中已經存在,則說明插入失敗,否則,就可以進行插入操作。這裡可以先不管是否超出M階樹的上限要求,因為我們在定義的時候會故意留下一個位置,可以存放多余的一個元素,插入之後,通過判斷是否達到M階樹上限要求,再進行遞歸的分裂操作。

/***
*  @name          Status insertBTree(BTree &T, Record e)
*  @description    插入實現元素的插入
*  @return        成功返回OK,如果存在則返回FALSE,否則返回ERROR
*  @notice
***/
Status insertBTree(BTree &T, Record e)
{
    BTree p;
    int index, temp;
    Status find_flag;
    if (NULL == T)//考慮B樹為空樹的情況
    {
        T = (BTree)malloc(BTLEN);
        if (NULL == T) return OVERFLOW;
        T->keynum = 1;
        T->parent = NULL;
        for (index = 0;index <= m; ++index)
        {
            T->ptr[index] = NULL;
            T->key[index] = 0;
        }
        T->key[1] = e.key;
        return OK;
    }
    find_flag = findBTree(T, p, temp, e.key);//尋找插入節點
    if (find_flag == TRUE)
    {
        return FALSE;
    }
    if (find_flag == FALSE)
    {                                //不管怎樣先直接插入
        p->keynum++;
        for (index = p->keynum;index > temp;--index)
        {
            p->key[index] = p->key[index - 1];
            p->ptr[index] = p->ptr[index - 1];
        }
        p->ptr[temp] = NULL;
        p->key[temp] = e.key;
        if (p->keynum == m)      //這種情況得分裂
        {
            splitBTree(p);
        }
        renewParent(T);
        return OK;
    }
    return ERROR;

更多詳情見請繼續閱讀下一頁的精彩內容: http://www.linuxidc.com/Linux/2015-07/120035p2.htm

Copyright © Linux教程網 All Rights Reserved