程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> STL源碼筆記（18）—平衡二叉樹AVL（C++封裝+模板）

STL源碼筆記（18）—平衡二叉樹AVL（C++封裝+模板）

編輯：關於C++

在幾年前剛學數據結構時，AVL-Tree只是一個僅僅需要掌握其概念的東西，今非昔比，借看STL源碼剖析的契機希望從代碼層面將其拿下。

1.簡介

二叉查找樹給我們帶來了很多方便，但是由於其在有序序列插入時就會退化成單鏈表（時間復雜度退化成 O(n)），AVL-tree就克服了上述困難。AVL-tree是一個“加上了平衡條件的”二叉搜索樹，平衡條件確保整棵樹的深度為O(log n)。

AVL樹是最先發明的自平衡二叉查找樹。在AVL樹中任何節點的兩個子樹的高度最大差別為一，所以它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下都是 O(log n)。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。

節點的平衡因子是它的左子樹的高度減去它的右子樹的高度（有時相反）。帶有平衡因子1、0或-1的節點被認為是平衡的。帶有平衡因子-2或2的節點被認為是不平衡的，並需要重新平衡這個樹。平衡因子可以直接存儲在每個節點中，或從可能存儲在節點中的子樹高度計算出來。

AVL樹的所有操作都與二叉查找樹相同，不同的是，這裡AVL樹需要做“AVL旋轉”。

2.AVL旋轉

AVL樹最重要的核心部分就是AVL旋轉了，這部分我的感觸是，單做旋轉還是挺好理解的，只不過寫起代碼來有點復雜，書中以插入節點為例，刪除節點的部分折騰了好久。

在理解AVL旋轉之前，首先得知道以下幾個概念：
1. AVL 樹節點的插入總是在葉子節點。
2. AVL 樹在插入節點之前總是滿足平衡條件的。
3. 插入新節點後有可能滿足平衡條件也有可能不滿足。
4. 當不滿足平衡條件後，我們就需要對新的樹進行旋轉。

旋轉之前，我們首先要找到一個X節點，這個X節點做如下定義：

假如我們在某一個葉子節點處插入一個新的節點後，此時這棵樹的某些節點的平衡性會發生變化，那麼我們從葉子節點向上到根節點的路徑上第一個平衡性發生變化的節點。

基於這個X節點，考慮一件事情：
這個X節點分為左右子樹，左右子樹又有左右子樹，1分2，2分4，所以以這個X節點為根節點的話，新插入的節點可能出現的位置有：

X的左孩子節點的左子樹上(left-left)
X的右孩子節點的右子樹上(right-right)
X的左孩子節點的右子樹上(left-right)
X的右孩子節點的左子樹上(right-left)

根據上述情況就延生出了4種旋轉：
1.left-left Rotation
2.right-right Rotation
3.left-right Rotation
4.right-left Rotation

前兩種屬於單旋轉，後兩種屬於雙旋轉，雙旋轉的操作可以由兩次單旋轉組成。

PS:AVL樹的旋轉還是得畫圖來理解，這裡直接貼出書中的圖了。

插入新節點

<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxoMyBpZD0="平衡破壞條件">平衡破壞條件

單旋轉（以left-left Rotation為例）

雙旋轉（以left-right Rotation為例）

雙旋轉：兩次單旋轉

3.AVL-Tree實現

AVL-Tree是一個二叉排序樹，其基本操作也跟它類似，唯一需要注意的就是在插入，刪除節點後，需要對樹進行調整，讓樹的每個節點保持平衡。

節點的平衡因子是通過計算其左子樹和右子樹的差得來的，這裡有兩種考慮方式：
1. 每次都計算一次（遞歸求深度）。
2. 將平衡因子作為一個成員變量保存在節點中，平衡性發生變化的時候更新。

我采取了第1種方式，網上也有用第2種方式的，我說不上利弊，但是感覺起碼掌握一種方式就可以“一招鮮”了吧。

另外，這裡我用了C++類封裝，為了學習還順便使用了模板，所以類的聲明和實現都放在了一個文件中，感覺內容太多，還是分開來比較好。

（1）AVL-Tree節點結構定義

//AVLNode.h

#ifndef __AVLNODE_H__
#define __AVLNODE_H__
#include 
#include 
#include 
template 
class AVLNode{
public:
    KeyType key;
    AVLNode * left;
    AVLNode * right;
    AVLNode() :key(0),left(NULL), right(NULL){}
    AVLNode(KeyType k) :key(k), left(NULL), right(NULL){}
};
#endif

（2）AVL-Tree 類聲明

//AVLTree.h

#ifndef __AVLTREE_H__
#define __AVLTREE_H__
#include "AVLNode.h"
//AVL樹的模板實現
template 
class AVLTree
{
    typedef AVLNode AVLNode;//類型定義
private:
    AVLNode * avlroot;//私有數據結構
    int __height(const AVLNode *root);//求樹的高度
    int __diff(const AVLNode*root);//高度差（平衡因子）

    //AVL4種旋轉：左左，左右，右右，右左
    //X定義為插入位置節點到根節點的路徑上平衡條件被改變的節點中最深的那個節點
    //X通過遞歸返回的方式找到
    //左左：插入點位於X的左孩子節點的左子樹
    //左右：插入點位於X的左孩子節點的右子樹
    //右右：插入點位於X的右孩子節點的右子樹
    //右左：插入點位於X的右孩子節點的左子樹

    //單旋轉
    AVLNode * __ll_Rotation(AVLNode *root);//left-left rotation
    AVLNode * __rr_Rotation(AVLNode *root);//right-right rotation
    //雙旋轉
    AVLNode * __lr_Rotation(AVLNode *root);//left-right rotation
AVLNode * __rl_Rotation(AVLNode *root);//right-left rotation



    AVLNode * __Balance(AVLNode *root);//平衡操作
    AVLNode * __Insert(AVLNode *root, const KeyType &k);//插入的內部實現


    //中序遍歷的兩種重載
    void __InorderTraversal(const AVLNode* root);//輸出
    void __InorderTraversal(const AVLNode*root, std::vector&vec);//結果保存


    bool __isLeaf(AVLNode* const &);//判斷是否是葉子節點
    bool __isNodeWithTwoChild(AVLNode * const &);//判斷是否有兩個孩子

    AVLNode* __search(AVLNode *const root, const KeyType &k);//查找的內部實現


    void __deleteTree(AVLNode * root);//刪除樹的所有節點


    AVLNode* __Delete(AVLNode * root, const KeyType& k);//刪除節點

    AVLNode*__treeMin(AVLNode *root);//求當前根節點最小（一路向左）
    AVLNode*__treeMax(AVLNode*root);//求當前根節點的最大（一路向右）

public:
    AVLTree(){ avlroot = NULL; }//默認構造函數
    ~AVLTree();//析構函數刪除樹中所有節點
    AVLTree(const std::vector&);//構造函數，容器構造
    AVLTree(const KeyType * arr, size_t len);//構造函數，數組構造
    void InorderTraversal();//中序遍歷外部接口
    void InorderTraversal(std::vector&);//中序遍歷外部接口重載2
    bool Delete(const KeyType &k);//刪除節點的外部接口
    bool Insert(const KeyType & k);//插入節點的外部接口
    bool IsEmpty(){ return avlroot == NULL; }//樹空？
    bool search(const KeyType &k);//查詢外部接口

};//class AVLTree
//...
#endif

（3）插入節點

套路與BST一樣，小的往左走，大的往右走，新節點插到葉子節點處，這裡只需要根據新節點的位置進行四種不同的旋轉即可。

//AVLTree.h

//插入節點的私有成員實現
template 
AVLNode * AVLTree::__Insert(AVLNode * root, const KeyType&k)
{
    if (NULL == root)
    {
        root = new AVLNode(k);
        return root;
    }//遞歸返回條件
    else if (k < root->key)
    {
        root->left = __Insert(root->left, k);//遞歸左子樹
        //balance operation
        root = __Balance(root);//平衡操作包含了四種旋轉
    }
    else if (k>root->key)
    {
        root->right = __Insert(root->right, k);//遞歸右子樹
        //balance operation
        root = __Balance(root);//平衡操作包含了四種旋轉
    }
    return root;
}

這裡還寫了一個平衡操作的函數，就把四種旋轉包含進去了。

//AVLTree.cpp

//樹高
template 
int AVLTree::__height(const AVLNode *root)//求樹高
{
    if (root == NULL)
        return 0;
    return std::max(__height(root->left) , __height(root->right)) + 1;
}
//平衡因子
template 
int AVLTree::__diff(const AVLNode *root)//求平衡因子，即當前節點左右子樹的差
{
    return __height(root->left) - __height(root->right);
}

//平衡操作
template 
AVLNode * AVLTree::__Balance(AVLNode *root)
{
    int balanceFactor = __diff(root);//__diff用來計算平衡因子（左右子樹高度差）
    if (balanceFactor > 1)//左子樹高於右子樹
    {
        if (__diff(root->left) > 0)//左左外側
            root=__ll_Rotation(root);
        else//左右內側
            root=__lr_Rotation(root);
    }
    else if (balanceFactor < -1)//右子樹高於左子樹
    {
        if (__diff(root->right) > 0)//右左內側
            root=__rl_Rotation(root);
        else//右右外側
            root=__rr_Rotation(root);
    }
    return root;
}

四種旋轉

AVL Tree的核心：在剛學數據結構的時候，這部分的要求是理解即可，現在要寫代碼還真有點懵逼，好在雙旋轉可以由單旋轉合成，這樣也就降低了我們的工作量，只需要完成兩個單旋轉即可（指針操作，兩個單旋轉操作對稱），旋轉的命名以插入節點與X節點相對位置來決定。

//AVLTree.h

//四種AVL旋轉

template 
AVLNode * AVLTree::__rr_Rotation(AVLNode *root)//right-right rotation
{
    AVLNode* tmp;
    tmp = root->right;
    root->right = tmp->left;
    tmp->left = root;
    return tmp;
}
template 
AVLNode * AVLTree::__ll_Rotation(AVLNode *root)//left-left rotation
{
    AVLNode * tmp;
    tmp = root->left;
    root->left = tmp->right;
    tmp->right = root; 
    return tmp;
}
template 
AVLNode * AVLTree::__lr_Rotation(AVLNode *root)//left-right rotation
{
    AVLNode * tmp;
    tmp = root->left;
    root->left = __rr_Rotation(tmp);
    return __ll_Rotation(root);
}

template 
AVLNode * AVLTree::__rl_Rotation(AVLNode *root)//right-left rotation
{
    AVLNode * tmp;
    tmp = root->right;
    root->right = __ll_Rotation(tmp);
    return __rr_Rotation(root);
}

（4）刪除節點

刪除節點就麻煩了，也是要分情況討論，刪除節點後，還要根據不同的情況做相應的旋轉。

//AVLTree.h
//刪除節點的私有成員實現
template 
AVLNode* AVLTree::__Delete(AVLNode *root, const KeyType& k)
{
    if (NULL == root)
        return root;
    if (!search(k))//查找刪除元素是否存在
    {
        std::cerr << "Delete error , key not find" << std::endl;
        return root;
    }

    if (k == root->key)//根節點
    {
        if (__isNodeWithTwoChild(root))//左右子樹都非空
        {
            if (__diff(root) > 0)//左子樹更高，在左邊刪除
            {
                root->key = __treeMax(root->left)->key;//以左子樹的最大值替換當前值
                root->left = __Delete(root->left, root->key);//刪除左子樹中已經替換上去的節點
            }
            else//右子樹更高，在右邊刪除
            {
                root->key = __treeMin(root->right)->key;
                root->right = __Delete(root->right, root->key);
            }
        }
        else//有一個孩子、葉子節點的情況合並
        {
            //if (!__isLeaf(root))
                AVLNode * tmp = root;
                root = (root->left) ? (root->left) :( root->right);
                delete tmp;
                tmp = NULL;
        }
    }//end-if
    else if (k < root->key)//往左邊刪除
    {
        root->left = __Delete(root->left, k);//左子樹中遞歸刪除
        //判斷平衡的條件與在插入時情況類似
        if (__diff(root) < -1)//不滿足平衡條件，刪除左邊的後，右子樹變高
        {
            if (__diff(root->right) > 0)
            {
                root = __rl_Rotation(root);
            }
            else
            {
                root = __rr_Rotation(root);
            }
        }
    }//end else if
    else
    {
        root->right = __Delete(root->right, k);
        if (__diff(root) > 1)//不滿足平衡條件
        {
            if (__diff(root->left) < 0)
            {
                root = __lr_Rotation(root);
            }
            else
            {
                root = __ll_Rotation(root);
            }
        }
    }
    return root;
}


//刪除節點的外部接口
template 
bool AVLTree::Delete(const KeyType &k)
{
    return __Delete(avlroot, k)==NULL?false:true;
}

（5）構造與析構

構造

以插入元素為基礎，構造函數就簡單了，我寫了三個構造函數，應該足夠。
1.默認構造函數
2.用容器構造
3.數組構造

//AVLTree.h
template 
class AVLTree
{
    typedef AVLNode AVLNode;//類型定義
    //...
public:
    AVLTree(){ avlroot = NULL; }//默認構造函數
    AVLTree(const std::vector&);//構造函數，容器構造
    AVLTree(const KeyType * arr, size_t len);//構造函數，數組構造
    //...
};

//構造函數1-容器構造
template < typename KeyType >
AVLTree::AVLTree(const std::vector&vec)
{
    avlroot = NULL;
    for (int i = 0; i < (int)vec.size(); i++)
    {
        Insert(vec[i]);
    }
}

//構造函數2-數組構造
template < typename KeyType >
AVLTree::AVLTree(const KeyType * arr,size_t len)
{
    avlroot = NULL;
    for (int i = 0; i < (int)len; i++)
    {
        Insert(*(arr + i));
    }
}

析構

由於節點數據結構是動態申請的，這裡在程序結束後，需要手動釋放，AVL-Tree的析構很簡單，因為它本質上就是一棵二叉樹麼，直接按照二叉樹的方式去做就OK~

template 
void AVLTree::__deleteTree(AVLNode *root)//刪除所有節點
{
    if (NULL == root)
        return;
    __deleteTree(root->left);
    __deleteTree(root->right);
    delete root;
    root = NULL;
    return;
}

//析構函數
template 
AVLTree::~AVLTree()
{
    __deleteTree(avlroot);
}

（6）AVL-Tree的查找與遍歷

AVL-tree也是二叉搜索樹，其中序遍歷滿足升序，且不允許有相同元素。
同理，AVL-tree的查找與BST一樣，也是小的往左走，大的往右走，不同是，由於加了平衡條件，AVLTree查找的復雜度能控制在對數范圍O(log n)，這也是AVL相比較BST在有序情況下會退化為線性表的一個最大優勢了。

//AVLTree.h

//查找內部實現
template 
AVLNode* AVLTree::__search(AVLNode *const root, const KeyType &k)
{
    if (NULL == root)
        return NULL;
    if (k == root->key)
        return root;
    else if (k > root->key)
        return __search(root->right, k);
    else
        return __search(root->left, k);
}
//查找外部接口
template 
bool AVLTree::search(const KeyType &k)
{
    return __search(avlroot, k) == NULL ? false : true;
}


//中序遍歷內部調用（1直接打印）
template 
void AVLTree::__InorderTraversal(const AVLNode*root)
{
    if (NULL == root)
        return;
    __InorderTraversal(root->left);
    std::cout << root->key << " ";
    __InorderTraversal(root->right);
}

//中序遍歷內部調用（2存入容器）
template 
void AVLTree::__InorderTraversal(const AVLNode*root,std::vector&vec)
{
    if (NULL == root)
        return;
    __InorderTraversal(root->left);
    vec.push_back(root->val);
    __InorderTraversal(root->right);
}

//中序遍歷外部接口（重載版本1）
template 
void AVLTree::InorderTraversal()
{
    __InorderTraversal(avlroot);
}

//中序遍歷外部接口（重載版本2）
template 
void AVLTree::InorderTraversal(std::vector&vec)
{
    __InorderTraversal(avlroot,vec);
}

（7）測試代碼

測試環境
Visual Studio 2013
Windows 7 32bits

主要測試插入刪除等函數：

//main.cpp

#include "AVLTree.h"
int main()
{

#if 1
    std::vectorvec = { 7, 6, 5, 4, 3, 2, 1 };
    AVLTree avl(vec);
    avl.Insert(8);
    int keyToFind = 9;
    if (avl.search(keyToFind))
    {
        std::cout << keyToFind << " is found" << std::endl;
    }
    else
    {
        std::cerr << keyToFind << " is not found" << std::endl;
    }

    keyToFind = 4;
    if (avl.search(keyToFind))
    {
        std::cout << keyToFind << " is found" << std::endl;
    }
    else
    {
        std::cerr << keyToFind << " is not found" << std::endl;
    }

    avl.Delete(4);
    //avl.InorderTraversal();
#endif
    std::cout << std::endl;
    system("pause");
    return 0;
}