数据结构：平衡二叉树（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;
}