數據結構：平衡二叉樹（AVL樹）

AVL樹是每一個結點的左子樹和右子樹的高度最多差1的2叉查找樹。

要保持這個樹，必須在插入和刪除的時候都檢測是不是出現破壞樹結構的情況。然后立刻進行調劑。

看了好久，網上各種各種的AVL樹，千奇百怪。

關鍵是要理解插入的時候旋轉的概念。

//
//  AvlTree.h
//  HelloWorld
//  csdn blog：http://blog.csdn.net/u012175089
//  Created by feiyin001 on 17/1/9.
//  Copyright (c) 2017年 FableGame. All rights reserved.
//

#ifndef __HelloWorld__AvlTree__
#define __HelloWorld__AvlTree__


#include <iostream>
namespace Fable
{
    int max(int a, int b)
    {
        return a > b? a:b;
    }
    //2叉查找樹，對Comparable,必須實現了><=的比較
    template<typename Comparable>
    class AvlTree
    {
    public:
        //構造函數
        AvlTree(){}
        //復制構造函數
        AvlTree(const AvlTree& rhs)
        {
            root = clone(rhs.root);
        }
        //析構函數
        ~AvlTree()
        {
            makeEmpty(root);
        }
        //復制賦值運算符
        const AvlTree& operator=(const AvlTree& rhs)
        {
            if (this != &rhs)
            {
                makeEmpty(root);//先清除
                root = clone(rhs.root);//再復制
            }
            return *this;
        }
        //查找最小的對象
        const Comparable& findMin()const
        {
            findMin(root);
        }
        //查找最大的對象
        const Comparable& findMax()const
        {
            findMax(root);
        }
        //是不是包括了某個對象
        bool contains(const Comparable& x)const
        {
            return contains(x, root);
        }
        //樹為空
        bool isEmpty()const
        {
            return root == nullptr;
        }
        //打印整棵樹
        void printTree()const
        {
            printTree(root);
        }
        
        
        //清空樹
        void makeEmpty()
        {
            makeEmpty(root);
        }
        //插入某個對象
        void insert(const Comparable& x)
        {
            insert(x, root);
        }
        //移除某個對象
        void remove(const Comparable& x)
        {
            remove(x, root);
        }
    private:
        struct AvlNode
        {
            Comparable element;
            AvlNode* left;
            AvlNode* right;
            int height;
            AvlNode(const Comparable& theElement, AvlNode* lt, AvlNode* rt, int h = 0)
            :element(theElement), left(lt), right(rt), height(h){}
        };
        typedef AvlNode* AvlNodePtr;
        
        
        AvlNodePtr root;//根結點
        
        
        //順時針旋轉
        void clockwiseRotate(AvlNodePtr& a)
        {
            AvlNodePtr b = a->left;//左葉子
            a->left = b->right;//a的左葉子變成b的右葉子，b本來的子結點都比a小的。
            b->right = a;//b的右結點指向a，b的高度上升了。
            a->height = max(height(a->left), height(a->right)) + 1;//重新計算a的高度
            b->height = max(height(b->left), a->height) + 1;//重新計算b的高度
            a = b;//a的位置現在是b，當前的根結點
        }
        //逆時針旋轉
        void antiClockWiseRotate(AvlNodePtr& a)
        {
            AvlNodePtr b = a->right;//右結點
            a->right = b->left;//a接收b的左結點
            b->left = a;//自己成為b的左結點
            a->height = max(height(a->left), height(a->right)) + 1;//計算高度
            b->height = max(b->height, height(a->right)) + 1;//計算高度
            a = b;//新的根結點
        }
        //對左側結點的雙旋轉
        void doubleWithLeftChild(AvlNodePtr& k3)
        {
            antiClockWiseRotate(k3->left);//逆時針旋轉左結點
            clockwiseRotate(k3);//順時針旋轉本身
        }
        //對右側結點的雙旋轉
        void doubleWithRightChild(AvlNodePtr& k3)
        {
            clockwiseRotate(k3->right);//順時針旋轉有節點
            antiClockWiseRotate(k3);//逆時針旋轉本身
        }
        
        //插入對象，這里使用了援用
        void insert(const Comparable& x, AvlNodePtr& t)
        {
            if (!t)
            {
                t = new AvlNode(x, nullptr, nullptr);
            }
            else if (x < t->element)
            {
                insert(x, t->left);//比根結點小，插入左側
                if (height(t->left) - height(t->right) == 2)//高度差到達2了
                {
                    if (x < t->left->element)//插入左側
                    {
                        clockwiseRotate(t);//順時針旋轉
                    }
                    else
                    {
                        doubleWithLeftChild(t);//雙旋轉
                    }
                }
            }
            else if (x > t->element)
            {
                insert(x, t->right);//比根結點大，插入右側
                if (height(t->right) - height(t->left) == 2)//高度差到達2
                {
                    if (t->right->element < x)//插入右側
                    {
                        antiClockWiseRotate(t);//旋轉
                    }
                    else
                    {
                        doubleWithRightChild(t);//雙旋轉
                    }
                }
            }
            else
            {
                //相同的
            }
            t->height = max(height(t->left), height(t->right)) + 1;//計算結點的高度
        }
        void removeMin(AvlNodePtr& x, AvlNodePtr& t)const
        {
            if (!t)
            {
                return;//找不到
            }
            if (t->left)
            {
                removeMin(t->left);//使用了遞歸的方式
            }
            else
            {
                //找到最小的結點了
                x->element = t->element;
                AvlNodePtr oldNode = t;
                t = t->right;
                delete oldNode;//刪除原來要刪除的結點
            }
            if (t)
            {
                t->height = max(height(t->left), height(t->right)) + 1;//計算結點的高度
                if(height(t->left) - height(t->right) == 2)
                { //如果左兒子高度大于右兒子高度
                    if(height(t->left->left) >= height(t->left->right))//并且左兒子的左子樹高度大于左兒子的右子樹高度
                    {
                        clockwiseRotate(t); //順時針旋轉
                    }
                    else
                    {
                        doubleWithLeftChild(t);//雙旋轉左子樹
                    }
                    
                }
                else
                {
                    if(height(t->right->right) - height(t->right->left) == 2) //如果右子樹大于左子樹
                    {
                        antiClockWiseRotate(t);//逆時針旋轉
                    }
                    else
                    {
                        doubleWithRright(t);//雙旋轉右子樹
                    }
                }
            }
            
        }
        //刪除某個對象，這里必須要援用
        void remove(const Comparable& x, AvlNodePtr& t)const
        {
            if (!t)
            {
                return;//樹為空
            }
            else if (x < t->element)
            {
                remove(x, t->left);//比根結點小，去左側查找
            }
            else if (x > t->element)
            {
                remove(x, t->right);//比根結點大，去右側查找
            }
            else if (!t->left && !t->right)//找到結點了，有兩個葉子
            {
                removeMin(t, t->right);//這里選擇的方法是刪除右子樹的最小的結點
            }
            else
            {
                AvlNodePtr oldNode = t;
                t = (t->left) ? t->left : t->right;//走到這里，t最多只有1個葉子，將t指向這個葉子
                delete oldNode;//刪除原來要刪除的結點
            }
            if (t)
            {
                t->height = max(height(t->left), height(t->right)) + 1;//計算結點的高度
                if(height(t->left) - height(t->right) == 2)
                { //如果左兒子高度大于右兒子高度
                    if(height(t->left->left) >= height(t->left->right))//并且左兒子的左子樹高度大于左兒子的右子樹高度
                    {
                        clockwiseRotate(t); //順時針旋轉
                    }
                    else
                    {
                        doubleWithLeftChild(t);//雙旋轉左子樹
                    }
                    
                }
                else
                {
                    if(height(t->right->right) - height(t->right->left) == 2) //如果右子樹大于左子樹
                    {
                        antiClockWiseRotate(t);//逆時針旋轉
                    }
                    else
                    {
                        doubleWithRright(t);//雙旋轉右子樹
                    }
                }
            }
        }
        //左側子樹的結點肯定比當前根小的，所以1直往左側尋覓
        AvlNodePtr findMin(AvlNodePtr t)const
        {
            if (!t)
            {
                return nullptr;//找不到
            }
            if (!t->left)
            {
                return t;
            }
            return findMin(t->left);//使用了遞歸的方式
        }
        //右側子樹的結點肯定比當前根大，所以1直往右側找
        AvlNodePtr findMax(AvlNodePtr t)const
        {
            if (t)
            {
                while (t->right)//使用了循環的方式
                {
                    t = t->right;
                }
            }
            return t;
        }
        //判斷是不是包括某個對象，由于要使用遞歸，所以還有1個public版本的
        bool contains(const Comparable& x, AvlNodePtr t)const
        {
            if (!t)
            {
                return false;//空結點了
            }
            else if (x < t->element)
            {
                //根據2叉樹的定義，比某個結點小的對象，肯定只能存在與這個結點的左側的子樹
                return contains(x, t->left);
            }
            else if (x > t->element)
            {
                //根據2叉樹的定義，比某個結點大的對象，肯定只能存在與這個結點的右側的子樹
                return contains(x, t->right);
            }
            else
            {
                //相等，就是找到啦。
                return true;
            }
        }
        //清空子樹
        void makeEmpty(AvlNodePtr& t)
        {
            if (t)
            {
                makeEmpty(t->left);//清空左側
                makeEmpty(t->right);//清空右側
                delete t;//釋放本身
            }
            t = nullptr;//置為空
        }
        //打印子樹，這里沒有使用復雜的排位，純屬打印
        void printTree(AvlNodePtr t)const
        {
            if (!t)
            {
                return;
            }
            std::cout << t->element << std::endl;//輸出本身的對象
            printTree(t->left);//打印左子樹
            printTree(t->right);//打印右子樹
        }
        AvlNodePtr clone(AvlNodePtr t)const
        {
            if (!t)
            {
                return nullptr;
            }
            return new AvlNode(t->element, clone(t->left), clone(t->right));
        }
        int height(AvlNodePtr t)const
        {
            return t == nullptr ? ⑴ : t->height;
        }

    };
}
#endif

//
//  AvlTree.cpp
//  HelloWorld
//  csdn blog：http://blog.csdn.net/u012175089
//  Created by feiyin001 on 17/1/9.
//  Copyright (c) 2017年 FableGame. All rights reserved.
//

#include "AvlTree.h"
using namespace Fable;
int main(int argc, char* argv[])
{
    
    AvlTree<int> a;
    for(int i = 0; i < 100; ++i)
    {
        a.insert(i);
    } 
    return 0;
}

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈