//// AvlTree.h// HelloWorld// 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;  }  //二叉查找樹，對于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最多只有一個葉子，將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);//雙旋轉右子樹          }        }      }    }    //左邊子樹的結點肯定比當前根小的，所以一直往左邊尋找    AvlNodePtr findMin(AvlNodePtr t)const    {      if (!t)      {        return nullptr;//找不到      }      if (!t->left)      {        return t;      }      return findMin(t->left);//使用了遞歸的方式    }    //右邊子樹的結點肯定比當前根大，所以一直往右邊找    AvlNodePtr findMax(AvlNodePtr t)const    {      if (t)      {        while (t->right)//使用了循環的方式        {          t = t->right;        }      }      return t;    }    //判斷是否包含某個對象，因為要使用遞歸，所以還有一個public版本的    bool contains(const Comparable& x, AvlNodePtr t)const    {      if (!t)      {        return false;//空結點了      }      else if (x < t->element)      {        //根據二叉樹的定義，比某個結點小的對象，肯定只能存在與這個結點的左邊的子樹        return contains(x, t->left);      }      else if (x > t->element)      {        //根據二叉樹的定義，比某個結點大的對象，肯定只能存在與這個結點的右邊的子樹        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 ? -1 : t->height;    }  };}#endif

//// AvlTree.cpp// HelloWorld// 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;}