AVL树实现

1.AVL的概念

    1.AVL树属于二叉搜索树的一种，但它不同与普通的二叉搜索树还具有以下的性质：

    每一个根的左右子树的高度差的绝对值不超过1。AVL树是通过高度差去控制平衡的，所以又称作为平衡二叉搜索树。

    2.AVL树实现我们引入了一个平衡因子的概念，每一个结点都有它的平衡因子，所谓平衡因子即结点的右子树的高度减去左子树的高度，AVL树的平衡因子有0/1/-1三种，如果平衡因子不属于这三种之一便不是AVL树。

    3.AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在logN,那么增删查改的效率也可以控制在O(logN)

   下图就为典型的AVL树：

2.AVL树的实现 

   2.1AVL树的结构

template<class K, class V>

struct AVLTreeNode

{

// 需要parent指针，后续更新平衡因子可以看到

     pair<K, V> _kv;

    AVLTreeNode<K, V>* _left;

    AVLTreeNode<K, V>* _right;

    AVLTreeNode<K, V>* _parent;

    int _bf;                                                 // 平衡因子

AVLTreeNode(const pair<K, V>& kv)

    :_kv(kv)

    , _left(nullptr)

    , _right(nullptr)

    , _parent(nullptr)

    , _bf(0)

     {}

};

template<class K, class V>

class AVLTree

 {

       typedef AVLTreeNode<K, V> Node;

public:

    bool Insert(const pair<K, V>& kv)

 {

    if (_root == nullptr)

{

    _root = new Node(kv);

   return true;

 }

Node* parent = nullptr;

Node* cur = _root;

while (cur)

 {

if (cur->_kv.first < kv.first)

 {

    parent = cur;

    cur = cur->_right;

 }

else if (cur->_kv.first > kv.first)

 {

    parent = cur;

    cur = cur->_left;

 }

else

  {

    return false;

  }

}

  cur = new Node(kv);

if (parent->_kv.first < kv.first)

{

  parent->_right = cur;

}

else

{

  parent->_left = cur;

}

// 链接父亲

cur->_parent = parent;

// 控制平衡

// 更新平衡因子

while (parent)

{

if (cur == parent->_left)

    parent->_bf--;

else

     parent->_bf++;

if (parent->_bf == 0)

{

    break;

}

else if (parent->_bf == 1 || parent->_bf == -1)

{

    cur = parent;

    parent = parent->_parent;

}

else if (parent->_bf == 2 || parent->_bf == -2)

{

   // 旋转

    break;

}

else

{

    assert(false);

 }

}

   return true;

}

private:

   Node* _root = nullptr;

};

上面为一个完整的AVL的结构，接下来就是对AVL树的深层次了解

   2.2  AVL树的插入 

      2.2.1 AVL树插入一个值的过程

1.插入一个值按二叉搜索树的规则进行插入

2.如果插入后平衡因子都符合AVL树的规则插入就结束

3.如果不符合AVL树的规则，就更新平衡因子，对不平衡子树进行旋转

     2.2.2 平衡因子更新

更新的原则：

1. 平衡因子 = 0/1/-1；

2.插入的结点在右子树则parent的平衡因子++，在左子树则parent的平衡因子--

更新停止条件：

1.更新后parent的平衡因子等于0，更新前的平衡因子为1或者-1，说明一边高一边低，而插入的新结点插入在低的一边，插入后parent所在的子树高度不变，不会影响parent的父亲结点的平衡因子，更新结束。

2.更新后parent的平衡因子等于1或者-1，说明在更新前parent的平衡因子等于0，parent的左右子树一样高，但插入新结点后高度增加1了，就会影响parent的父结点，如果此时父结点不符合AVL树的规则就要去继续更新。

3.更新后parent的平衡因子等于2或者-2，说明更新前parent的平衡因子等于1或者-1，而新插入的结点恰好在较高的子树上。破坏了平衡,parent所在的子树不符合平衡要求，则需要旋转处理。

旋转的目标有两个：        1.把parent子树旋转平衡

                                        2.降低parent子树的高度，恢复到插入结点以前的高度，所以旋转后插入                                             结束。

 2.3 旋转

     2.3.1 旋转的原则

1.保持搜索树的原则

2.让旋转的树从不满足变平衡，其次降低旋转树的高度

旋转总共分为四种：左单旋/右单旋/左右双旋/右左双旋

      2.3.2 右单旋

在上图中就是右单旋的流程图， 有a/b/c抽象为三颗高度为h的子树（h>=0),a/b/c均符合AVL树的要求，10可能是整数的根也可能是一个整颗树局部的子树的根，该图也只是右单旋的形态之一，但易于理解。

如上图所示：在a点插入了一个新结点导致10的平衡因子变为了-2，为让其符合平衡规则，需要让10的过高的的左子树右旋，如第三步所示，从而控制两颗树的平衡。

核心步骤：因为5 < b子树的值 < 10,将b子树作为10结点的左子树，然后将5变成这颗新树的根，符合了搜索树的规则，控制了平衡，同时这颗树恢复到了之前的h+2,符合旋转原则。

以下的情况就不细讲了，根据第一张的思维可以理解下面的情况：

  2.3.3 右单旋代码的实现 

void RotateR(Node* parent)

{ 

     Node* subL = parent->_left;

     Node* subLR = subL->right;

     Node*Pparent = parent ->_parent;

    

     parent ->left = subLR;

     if(subLR)

     subLR->_parent = parent;

     parent ->_parent = subL;

     if(Pparent ==nullptr)

    {

        _root = subL;

        subL->_parent =nullptr;

    }

    else

     {

          if (parent ==Pparent->_left)

         {

             Pparent->_left = subL;

         }

        else

        {

           Pparent->_right = subL;

        }

          subL->_parent = Pparent;

     }

      subL->_parent = subL->_bf = 0;

}

2.3.4 左单旋 

  左单旋与右单旋类似，只是从原本过高的左子树的右旋变成现在的过高的右子树的左旋。

其他的情况也和右子树的情况类似这里就不一一列举了

 2.3.5 左单旋代码的实现

void RotateRL(Node* parent)

{
      Node*subR = parent->right;

      Node*subRL = parent->left;

      Node*Pparent = parent->_parent;

    

     parent ->_right =  subRL;

     if(subRL)

     subRL->_parent = parent;

     subR->_left =  parent;

     parent->_parent = subR;

     

    if(Pparent == nullptr)

  {

      _root = subR;

     subR->_parent = nullptr;

  }

  else if(Pparent->_left = parent)

 {

       Pparent ->_left = subR;

  }

  else 

  {

      Pparent ->_right = subR;

  } 

  subR->_parent = Pparent;

  parent->_bf = subR->_bf = 0;

}

 2.3.6 左右双旋

    

从上图可以看出右单旋没有解决两颗树的平衡问题，所以在这里就要使用左右双旋才能解决该问题。

 

在上图中有三个场景：

   场景1：h>=1时，新增结点插入在e子树，e子树高度从h-1并为h并不断更新8->5->10平衡因子，引发旋转，其中8的平衡因子为1，旋转后8和5平衡因子为0,10的平衡因子变为1.

   场景2：h >= 1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新8->5->10平衡因⼦，引发旋转，其中8的平衡因⼦为1，旋转后8和10平衡因⼦为0，5平衡因⼦为-1。

   场景3：h == 0时，a/b/c都是空树，b⾃⼰就是⼀个新增结点，不断更新5->10平衡因⼦，引发旋 转，其中8的平衡因⼦为0，旋转后8和10和5平衡因⼦均为0。

 2.3.7 左右双旋代码实现

void RotateLR(Node* parent)

{
   Node*subL = parent ->_left;

   Node*subLR = subL->_right;

   int bf = subLR->_bf；

 

  Rotatel(parent->_left);

  RotateR(parent);

   

     if (bf == 0)

  {

     subL->_bf = 0;

     subLR->_bf = 0;

     parent->_bf = 0;

  }

  else if (bf == -1)

  {

   subL->_bf = 0;

   subLR->_bf = 0;

   parent->_bf = 1;

  }

    else if(bf == 1)

  {

   subL->_bf = -1;

   subLR->_bf = 0;

   parent->_bf = 0;

  } 

   else

  {

    assert(false);

  }

}

2.3.8 右左双旋 

  同样分三个场景：

   场景1：h >= 1时，新增结点插⼊在e⼦树，e⼦树⾼度从h-1变为h并不断更新12->15->10平衡因 ⼦，引发旋转，其中12的平衡因⼦为-1，旋转后10和12平衡因⼦为0，15平衡因⼦为1。

  场景2：h >= 1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦，引发旋转，其中12的平衡因⼦为1，旋转后15和12平衡因⼦为0，10平衡因⼦为-1。

 场景3：h == 0时，a/b/c都是空树，b⾃⼰就是⼀个新增结点，不断更新15->10平衡因⼦，引发旋 转，其中12的平衡因⼦为0，旋转后10和12和15平衡因⼦均为0。

2.3.9 右左双旋代码实现 

void RotateRL(Node* parent)

{

  Node* subR = parent->_right;

  Node* subRL = subR->_left;

  int bf = subRL->_bf;

  RotateR(parent->_right);

  RotateL(parent);

  if (bf == 0)

{

   subR->_bf = 0;

   subRL->_bf = 0;

   parent->_bf = 0;

}

else if (bf == 1)

{

   subR->_bf = 0;

   subRL->_bf = 0;

   parent->_bf = -1;

}

else if (bf == -1)

{

  subR->_bf = 1;

  subRL->_bf = 0;

  parent->_bf = 0;

}

else

{

  assert(false);

}

}