3.1 C語言_實(shí)現(xiàn)AVL平衡二叉樹

3.1 C語言_實(shí)現(xiàn)AVL平衡二叉樹

【序】

上節(jié)我們實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)中最簡單的Vector，那么來到第三章，我們需要實(shí)現(xiàn)一個(gè)Set

set的特點(diǎn)是 內(nèi)部有序且有唯一元素值；同時(shí)各種操作的期望操作時(shí)間復(fù)雜度在O（n·logn）；

那么標(biāo)準(zhǔn)的C++ STL（Standard Template Library） 容器內(nèi)部使用的是什么呢？

STL使用的是紅黑樹或者h(yuǎn)ash Tree ，由于筆者現(xiàn)在的水平和精力，沒時(shí)間搞這個(gè)啦，于是我就

挑了一個(gè)稍微熟悉一點(diǎn)的數(shù)據(jù)結(jié)構(gòu)：AVL 樹；

github：https://github.com/KimAlittleStar/cstd

【1.介紹】

AVL 樹是根據(jù)二叉查找樹改進(jìn)延伸過來的，我們都知道二叉查找樹中只有一個(gè)規(guī)則，

那就是根節(jié)點(diǎn)的元素一定會(huì)大于左孩子，小于右孩子；如果是隨機(jī)數(shù)，那么我們二叉查找樹的高度無限

接近于 logN（完全二叉樹）。但是由于其策略，在反復(fù)的插入和刪除后，普通的二叉查找樹將會(huì)非常

偏科（偏向右子樹）如果樹的高度非常大（height == N） 那么他和鏈表的操作時(shí)間沒有什么區(qū)別，

為了避免普通二叉查找樹的缺陷，因此引申出 AVL Tree -> 平衡二叉查找樹；

AVL 和普通的二叉查找樹只有一個(gè)規(guī)則限制：相同節(jié)點(diǎn)的兩個(gè)孩子的高度最大相差為1，本身節(jié)點(diǎn)的高度

為兩個(gè)孩子節(jié)點(diǎn)中大的那個(gè)高度加1；

【2.基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)】

使用一個(gè)node 和 正常的tree 用于管理他的根和size；node 中有左孩子 右孩子和數(shù)據(jù)還有一個(gè)記錄樹的

高度字節(jié)u8（unsigned char），為什么我們使用u8，因?yàn)榧僭O(shè)在滿足AVL的規(guī)則要求下，壞的情況樹的深度為

deep = logn *2 +1 ； 去除一個(gè)起始位0 ,后期可能會(huì)用到的錯(cuò)誤位 -1，那么在最差的情況下 u8 類型的高度可以存儲(chǔ)

大概多少個(gè)節(jié)點(diǎn)呢：

N = 2^254 （個(gè)）而我們在tree 中 size 的類型是 u32 （unsigned int）完全夠用了；

參考下圖：（數(shù)據(jù)結(jié)構(gòu)與算法C++.pdf）

平衡二叉樹
typedef unsigned int typeClass;

typedef struct __SET_typeClass_node
{
    typeClass data;
    struct __SET_typeClass_node *left;
    struct __SET_typeClass_node *right;
    u8 heigh;
}
 SET_typeClass_node_t;

typedef struct __SET_typeClass_t
{
    SET_typeClass_node_t *root;
    u32 size;
}
 SET_typeClass_t;

【3 插入】

數(shù)據(jù)的插入還是依照我們普通的二叉樹進(jìn)行插入，遞歸判斷我們的數(shù)據(jù)是否小于當(dāng)前節(jié)點(diǎn)，

小于，遞歸往左走，大于，大于遞歸往右走，等于，不操作，真正的基礎(chǔ)情況是判斷是發(fā)現(xiàn)當(dāng)前

節(jié)點(diǎn)為NULL 此時(shí)申請內(nèi)存存儲(chǔ)該元素；

SET_typeClass_node_t *SET_inserttypeClass_node_t(SET_typeClass_node_t *root,
                                                 u8 (*compare)(const typeClass *a, const typeClass *b),                                                 const typeClass *value, u32 *size)
{
    if (root == NULL)
    {
        root = (SET_typeClass_node_t *)malloc(sizeof(SET_typeClass_node_t));
        if (root == NULL)
        {
            // Out of space!!!        }
        else
        {
            root->data = (*value);
            root->left = root->right = NULL;
            (*size)++;
        }
        return root;
    }
    else if (compare(value, &root->data))
    {
        root->left = SET_inserttypeClass_node_t(root->left, compare, value, size);
    }
    else if (compare(&root->data, value))
    {
        root->right = SET_inserttypeClass_node_t(root->right, compare, value, size);
    }
    return root;
}

當(dāng)我們在做完這一切之后，還需要做的是維護(hù)AVL的性質(zhì)：左右節(jié)點(diǎn)高度相差最大為1；且需要

遞歸查詢哦。于是乎我們接下來第一步要做的是什么呢？

更新我們自己的節(jié)點(diǎn)的高度；

root->heigh = SET_Max(SET_heighttypeClass(root->left),
                          SET_heighttypeClass(root->right)) +                  1;

更新之后節(jié)點(diǎn)之后我們就會(huì)發(fā)現(xiàn)，哎呀，有些時(shí)候（大多數(shù)時(shí)候）AVL樹的規(guī)則被破壞了，那么該

就需要處理重新符合AVL樹的規(guī)則；插入之后呢可能會(huì)出現(xiàn)四種情況，其中兩兩鏡像，因此我們只討論

兩種；

LL情況

LR情況

以上兩種情況分別為 LL ，LR，具體判斷標(biāo)準(zhǔn)為：觀察高度開始不符合的節(jié)點(diǎn)，8號(hào)節(jié)點(diǎn)和 K2節(jié)點(diǎn)，

這里說的**高度不符的節(jié)點(diǎn)表示：左右孩子的高度相差 >1 **那么他們偏離的子節(jié)點(diǎn)的方向分別是

8號(hào)：Left->Left k2->Left->Right;　　我們在處理LL情況的時(shí)候，只需要將7號(hào)變成5號(hào)的右孩子；

8號(hào)變成7號(hào)的右孩子即可，相當(dāng)于678號(hào)順時(shí)針旋轉(zhuǎn)了一下，我們把這個(gè)定義為左單旋，旋轉(zhuǎn)后

變成如下圖：

旋轉(zhuǎn)后

相對(duì)應(yīng)的也有** ”右單旋“**咯。大家自己推導(dǎo)啦；

接下來看我們的LR情況，如果僅僅對(duì)K2執(zhí)行一次左單旋，那么結(jié)果是：

旋轉(zhuǎn)后

但是這樣依舊沒有滿足 AVL 樹的性質(zhì)；K2的高度會(huì)比 X大超過1；此時(shí)我們需要引進(jìn)一個(gè)k1的右節(jié)點(diǎn)進(jìn)行雙旋轉(zhuǎn)；

旋轉(zhuǎn)后

我們首先把 K1 k2 B 進(jìn)行一次右單旋；得到

右單旋后

然后我們在將Ck2k3進(jìn)行一次左旋：

做單旋后

相對(duì)應(yīng)的我們也會(huì)有 RL的情況，鏡像情況我們就不贅述咯；

下面代碼是單旋、雙旋的實(shí)現(xiàn)：

SET_typeClass_node_t *SET_doubleRotateLefttypeClass(SET_typeClass_node_t *s)
{
    s->left = SET_singleRotateRighttypeClass(s->left);
    return SET_singleRotateLefttypeClass(s);
}
SET_typeClass_node_t *SET_doubleRotateRighttypeClass(SET_typeClass_node_t *s)
{
    s->right = SET_singleRotateLefttypeClass(s->right);
    return SET_singleRotateRighttypeClass(s);
}

SET_typeClass_node_t *SET_singleRotateLefttypeClass(SET_typeClass_node_t *s)
{
    SET_typeClass_node_t *s1;
    s1 = s->left;
    s->left = s1->right;
    s1->right = s;

    s->heigh = SET_Max(
                   SET_heighttypeClass(s->left),
                   SET_heighttypeClass(s->right)) +               1;
    s1->heigh = SET_Max(
                    SET_heighttypeClass(s1->left),
                    s->heigh) +                1;
    return s1;
}

SET_typeClass_node_t *SET_singleRotateRighttypeClass(SET_typeClass_node_t *s)
{
    SET_typeClass_node_t *s1;
    s1 = s->right;
    s->right = s1->left;
    s1->left = s;

    s->heigh = SET_Max(
                   SET_heighttypeClass(s->left),
                   SET_heighttypeClass(s->right)) +               1;
    s1->heigh = SET_Max(
                    SET_heighttypeClass(s1->right),
                    s->heigh) +                1;
    return s1;
}

綜合以上，我們最后insert的代碼就成了：

SET_typeClass_node_t *SET_inserttypeClass_node_t(SET_typeClass_node_t *root,
                                                 u8 (*compare)(const typeClass *a, const typeClass *b),                                                 const typeClass *value, u32 *size)
{
    if (root == NULL)
    {
        root = (SET_typeClass_node_t *)malloc(sizeof(SET_typeClass_node_t));
        if (root == NULL)
        {
            // Out of space!!!        }
        else
        {
            root->data = (*value);
            root->left = root->right = NULL;
            root->heigh = 1;
            (*size)++;
        }
        return root;
    }
    else if (compare(value, &root->data))
    {
        root->left = SET_inserttypeClass_node_t(root->left, compare, value, size);
        if (SET_heighttypeClass(root->left) - SET_heighttypeClass(root->right) == 2)
        {
            if (compare(value, &root->left->data))
                root = SET_singleRotateLefttypeClass(root);
            else
                root = SET_doubleRotateLefttypeClass(root);
        }
    }
    else if (compare(&root->data, value))
    {
        root->right = SET_inserttypeClass_node_t(root->right, compare, value, size);
        if (SET_heighttypeClass(root->right) - SET_heighttypeClass(root->left) == 2)
        {
            if (compare(&root->right->data, value))
                root = SET_singleRotateRighttypeClass(root);
            else
                root = SET_doubleRotateRighttypeClass(root);
        }
    }
    root->heigh = SET_Max(SET_heighttypeClass(root->left),
                          SET_heighttypeClass(root->right)) +                  1;
    return root;
}

然后我們使用 tree 將其包裝，并且返回是否插入成功；插入不成功有兩種情況（內(nèi)存空間不足和元素已存在）

u8 SET_inserttypeClass_t(SET_typeClass_t *set, const typeClass ele)
{
    if (set == NULL || set->compare == NULL)        return 0;
    u32 cursize = set->size;
    set->root = SET_inserttypeClass_node_t(set->root, set->compare, &ele, &set->size);
    return (cursize < set->size);
}

【4 刪除】

刪除的操作呢，比插入要更加復(fù)雜一些；但是我們依舊是從基礎(chǔ)的二叉樹刪除來入手；普通的二叉樹首先

遞歸尋找到數(shù)據(jù)，然后將數(shù)據(jù)分成兩種情況：該元素有兩個(gè)孩子和該元素沒有兩個(gè)孩子；沒有兩個(gè)孩子的邏輯就

很簡單，判斷當(dāng)前左孩子是否為空，是：將元素的指針指向他的右孩子，否則指向左孩子；如果兩個(gè)孩子都為NULL，

指向誰都一樣；

如果是有兩個(gè)孩子的呢？那么我們就將這個(gè)元素下尋找到他最小的一個(gè)子輩（可能是他的孩子、孫子、曾孫、玄孫。。。）

然后把他的子輩賦值給他，然后刪除他的那個(gè)子輩；因?yàn)樗淖虞呉欢ㄊ亲蠛⒆訛镹ULL的；

以下為實(shí)現(xiàn)：

SET_typeClass_node_t *SET_removetypeClass_node_t(SET_typeClass_node_t *root,
                                                 u8 (*compare)(const typeClass *a, const typeClass *b),                                                 void (*deleteSub)(const typeClass *ele),                                                 const typeClass *value, u32 *size)
{
    if (root == NULL)
    {
        
    // no has this value    
    }
    
    else if (compare(value, &root->data))
    {
        root->left = SET_removetypeClass_node_t(root->left, compare, deleteSub, value, size);
    }
    
    else if (compare(&root->data, value))
    {
        root->right = SET_removetypeClass_node_t(root->right, compare, deleteSub, value, size);
    }
    else
    {
        /*real delete option*/
        if (root->right != NULL && root->left != NULL)
        {
            /* has two child */
            SET_typeClass_node_t *temp = root;
            
            while (temp->left != NULL)
            {
                temp = temp->left;
            }
            if (deleteSub != NULL)
                deleteSub(&root->data);
            root->data = temp->data;
            /* deleteSub == NULL because this min not to free ,just become root->data; */
            root->left = SET_removetypeClass_node_t(root->left, compare, NULL, &root->data, size);
        }
        else
        {
            /* has only child or no child */
            SET_typeClass_node_t *t = (root->right == NULL) ? (root->left) : (root->right);
            
            if (deleteSub != NULL)
                deleteSub(&root->data);
            free(root);
            (*size)--;
            root = t;
        }
     }
    
     return root;
}

刪除完節(jié)點(diǎn)之后，我們依舊需要考慮的問題是平衡的問題；刪除會(huì)出現(xiàn)什么問題呢？我們上述的刪除到最后

一定以刪除一個(gè)在末梢的節(jié)點(diǎn)（孩子最多只有一個(gè)），因此我們只需要考慮此情況即可；

我們可以換一個(gè)思路，其實(shí)刪除帶來的影響就是在樹的另一邊插入了一個(gè)值；那么相對(duì)應(yīng)的，那邊高度高了我

就往哪邊旋轉(zhuǎn)就好了；只不過我們判斷的時(shí)候如果是刪除左邊，那么我們就要判斷當(dāng)前是不是右邊高度-左邊高度 > 2 就好了。

嗯~很簡單是不是？

不不不，在insert中我們判斷是否需要使用雙旋轉(zhuǎn)的依據(jù)是：

root->right = SET_inserttypeClass_node_t(root->right, compare, value, size);

if (SET_heighttypeClass(root->right) - SET_heighttypeClass(root->left) == 2)

{

　　if (compare(&root->right->data, value))

　　　　root = SET_singleRotateRighttypeClass(root);

　　else

　　　　root = SET_doubleRotateRighttypeClass(root);

}

因?yàn)樵诓迦霑r(shí)，如果出現(xiàn)的不平衡，那么假設(shè)插入的值比當(dāng)前root的右孩子要大，那么就會(huì)插入在右孩子的左邊；

就會(huì)出現(xiàn)下圖所示 （插入了 14 ）此時(shí)需要雙旋轉(zhuǎn)，是因?yàn)?strong>k1的右孩子高度高且右孩子的左側(cè)比右側(cè)要高；這句話有

點(diǎn)繞口，我們分成兩步，

第一步：k1節(jié)點(diǎn)破壞了AVL樹的規(guī)則且需要旋轉(zhuǎn)的是右邊；

第二步：在k1的右孩子k3上，雖然沒有違法AVL的規(guī)則，但是他的左孩子高度要比右孩子高度高；這就是我們所說

的RL情況，

所以需要雙旋；

image
image

那么在刪除是，也應(yīng)遵循此規(guī)則，也就是說刪除的時(shí)候我們就不要比較 刪除值的大小啦，因?yàn)閯h除完值之后，

相當(dāng)于我們需要知道另一側(cè)的情況是不是需要雙旋，這個(gè)時(shí)候怎么辦呢？我們就依照上述一二步的原理，判斷如果

左邊高度高高于右邊高度 >1 了，那么我就看左邊孩子的兩個(gè)孩子的高度是不是右邊 > 左邊，如果是->雙旋轉(zhuǎn),如果

不是，單旋轉(zhuǎn)；由于有兩個(gè)孩子的節(jié)點(diǎn)到最后也會(huì)是刪除一個(gè)葉子節(jié)點(diǎn)，故不需要考慮；

以下是remove判斷是否需要雙旋轉(zhuǎn)的代碼：

if (compare(value, &root->data))
{
    root->left = SET_removetypeClass_node_t(root->left, compare, deleteSub, value, size);
    
    if (SET_heighttypeClass(root->right) - SET_heighttypeClass(root->left) == 2)
    {
        if (SET_heighttypeClass(root->right->right) > SET_heighttypeClass(root->right->left))
            root = SET_singleRotateRighttypeClass(root);
        else
            root = SET_doubleRotateRighttypeClass(root);
    }
    
}

需要我們注意的是在刪除有兩個(gè)孩子的節(jié)點(diǎn)的時(shí)候，雖然我們是刪除，但是我實(shí)際上還是調(diào)用的遞歸，一次我們還

是需要判斷一次平衡規(guī)則；

最后remove的代碼如下：

SET_typeClass_node_t *SET_removetypeClass_node_t(SET_typeClass_node_t *root,
                                                u8 (*compare)(const typeClass *a, const typeClass *b),
                                                void (*deleteSub)(const typeClass *ele),
                                                const typeClass *value, u32 *size)
{
    
    if (root == NULL)
    {
        
    // no has this value    
    }
    
    else if (compare(value, &root->data))
    {
        root->left = SET_removetypeClass_node_t(root->left, compare, deleteSub, value, size);
        
        if (SET_heighttypeClass(root->right) - SET_heighttypeClass(root->left) == 2)
        {
            
                if (SET_heighttypeClass(root->right->right) > SET_heighttypeClass(root->right->left))
                    root = SET_singleRotateRighttypeClass(root);
            
                else
                    root = SET_doubleRotateRighttypeClass(root);
        }
    }
    else if (compare(&root->data, value))
    {
        root->right = SET_removetypeClass_node_t(root->right, compare, deleteSub, value, size);
        
        if (SET_heighttypeClass(root->left) - SET_heighttypeClass(root->right) == 2)
        {
            
            if (SET_heighttypeClass(root->left->left) > SET_heighttypeClass(root->left->right))
                root = SET_singleRotateLefttypeClass(root);
            
            else
                root = SET_doubleRotateLefttypeClass(root);
        }
    }
    else
    {
        /*real delete option*/
        if (root->right != NULL && root->left != NULL)
        {
            /* has two child */
            SET_typeClass_node_t *temp = root;
            
            while (temp->left != NULL)
            {
                temp = temp->left;
            }
            
            if (deleteSub != NULL)
                deleteSub(&root->data);
            root->data = temp->data;
            /* deleteSub == NULL because this min not to free ,just become root->data; */
            root->left = SET_removetypeClass_node_t(root->left, compare, NULL, &root->data, size);
            if (SET_heighttypeClass(root->right) - SET_heighttypeClass(root->left) == 2)
            {
                    if (SET_heighttypeClass(root->right->right) > SET_heighttypeClass(root->right->left))
                        root = SET_singleRotateRighttypeClass(root);
                    else
                        root = SET_doubleRotateRighttypeClass(root);
            }
        }
        else
        {/* has only child or no child */
            SET_typeClass_node_t *t = (root->right == NULL) ? (root->left) : (root->right);
            if (deleteSub != NULL)
                deleteSub(&root->data);
            free(root);
            (*size)--;
            root = t;
        }
    }
    if (root != NULL)
        root->heigh = SET_Max(SET_heighttypeClass(root->left),
                              SET_heighttypeClass(root->right)) +
                      1;
    return root;
}

同理使用一個(gè)tree對(duì)他進(jìn)行封裝，同時(shí)返回是否remove成功，remove不成功只有一種可能，那就是set中不存在此元素；

u8 SET_removetypeClass_t(SET_typeClass_t *set, const typeClass ele)
{
    if (set == NULL || set->compare == NULL)        return 0;
    u32 cursize = set->size;
    set->root = SET_removetypeClass_node_t(set->root, set->compare, set->deleteSub, &ele, &set->size);
    return (cursize > set->size);
}

在AVL樹中最重要的就是插入和刪除啦；

其他的像 delete 遍歷呀，find findMax之類的太簡單我就不說啦。基本上就是使用遍歷或者一直往右找或往左找；

最后我考慮到上文中SET_typeClass_t是一個(gè)類型，所以所有的比較都抽象化了compare函數(shù)，還有有可能在刪除的時(shí)候

需要釋放SET_typeClass_t中指向的空間，所以抽象化成為函數(shù)指針deleteSub；

【結(jié)束語】

下一節(jié)就是將我們今天所實(shí)現(xiàn)的這些函數(shù)變成宏，完成 STL 數(shù)據(jù)容器 SET

目錄

1.引言

2.1 C語言_實(shí)現(xiàn)簡單基礎(chǔ)的vector

2.2 C語言_實(shí)現(xiàn)數(shù)據(jù)容器vector(排序功能)

3.1 C語言_實(shí)現(xiàn)AVL平衡二叉樹

3.2 C語言_實(shí)現(xiàn)數(shù)據(jù)容器set(基礎(chǔ)版)

4 C語言_實(shí)現(xiàn)簡單基礎(chǔ)的map

參考資料 : 數(shù)據(jù)結(jié)構(gòu)與算法C++實(shí)現(xiàn).pdf;

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 今天是四老舅丟失馬的第二天——不，確切的說是第六天，只不過四老舅在前兩天才發(fā)現(xiàn)。 據(jù)目擊者說大馬和小馬是讓一個(gè)類似...
    橘貓暖暖閱讀 403評(píng)論 0贊 3
  • 1. 安裝 gtk+2.0 針對(duì)RedHat系列操作系統(tǒng)，執(zhí)行命令#yum install gtk2-devel針...
    快樂小吧閱讀 1,567評(píng)論 0贊 1
  • 春節(jié)是我國一個(gè)古老的節(jié)日，也是全年最重要的一個(gè)節(jié)日，如何過慶賀這個(gè)節(jié)日，在千百年的歷史發(fā)展中，形成了一些較為固定的...
    GJRRRRR閱讀 199評(píng)論 0贊 0
  • 財(cái)務(wù)自由，很流行的概念，也是蕓蕓眾生中凡俗你我向往的境界。什么男人財(cái)務(wù)自由、女人財(cái)務(wù)自由的15個(gè)階段，娛...
    慧子清心閱讀 206評(píng)論 0贊 1
  • 今天的重點(diǎn)就是那個(gè)心理模型：騎象人與象。象征理性與感性。這個(gè)試驗(yàn)告訴我們行為的改變居然不是靠意志力，而是去平衡理性...
    自律的黃老爺閱讀 188評(píng)論 2贊 4

友情鏈接更多精彩內(nèi)容