AVL树的原理以及实现-阿里云开发者社区

在二叉搜索树的基础上，我们了解到利用二叉搜索树可以快速的查询数据！时间复杂度只要O(lgn)，但是二叉搜索树的确有一个缺点，如果数据都是有序的插入，那么此时就是一颗单支树，此时的查找效率为O(n)，AVL树的提出就是为了解决这一个缺点！

1 平衡因子

在二叉搜索树中加入一个数据，用来记录右子树与左子树之间的高度差的值（也可以左子树的高度与右子树高度的差值），这个值就被称为平衡因子！我们规定，平衡因子必须为0,1，-1三个数中的一个，如果为2或者-2就必须进行旋转调整为平衡二叉树！也就是说引入平衡因子的目的就是为了让我们可以直观的看出该树是否是平衡树，根据平衡因子做出旋转！

2 AVL树的插入

1 根据二叉搜索树的原则，进行插入

2 插入之后，就要判断插入的位置，如果插入的是parent的左边，那么parent的平衡因子就需要减1，右边的话就需要加1

3 在判断一下平衡因子，如果平衡因子为0了，说明没有改变这棵子树的高度，就不需要改变之前节点的平衡因子了，如果是1或者-1，那就说明以parent节点的子树，右子树的高度变高了或者是左子树变高了，那么此时就需要我们parent往上走，在判断它在它的父节点的左边还是右边，如果平衡因子等于2或者是-2了，那就是需要对二叉搜索树进行旋转调整了！

以上就是实现AVL树的插入的基本思想，实现的代码如下：

//AVL树的插入
bool Insert(pair<K,V> kv)
{
  //按照二叉搜索树的方式进行插入
  if (_root == nullptr)
  {
    _root = new Node(kv);
    return true;
  }
  Node* parent = _root;
  Node* cur = _root;
  while (cur)
  {
    parent = cur;
    if (kv.first > parent->_KV.first)
    {
      cur = parent->_right;
    }
    else if (kv.first < parent->_KV.first)
    {
      cur = parent->_left;
    }
    else {
      return false;
    }
  }

  if (kv.first > parent->_KV.first)
  {
    parent->_right = new Node(kv);
    cur = parent->_right;
    cur->_parent = parent;
  }
  else {
    parent->_left = new Node(kv);
    cur = parent->_left;
    cur->_parent = parent;
  }
    
  

  //调节节点确保是AVL树
  while (parent)
  {
    if (cur == parent->_left)
    {
      parent->_bf--;
    }
    else if (cur == parent->_right)
    {
      parent->_bf++;
    }
    else
    {
      assert(false);
    }

    if(parent->_bf==1||parent->_bf==-1)
    {
      cur = parent;
      parent = parent->_parent;
    }else if (parent->_bf == 2 || parent->_bf == -2)
      {
      //需要调节
      if (parent->_bf==2&&cur->_bf == 1)
      {
        //左单旋
        RotateL(parent);
      }
      else if (parent->_bf==-2&&cur->_bf==-1)
      {
        //右单旋
        RotateR(parent);
      }
      else if (parent->_bf == 2&& cur->_bf==-1)
      {
        RotateRL(parent);
      }
      else if (parent->_bf==-2&&cur->_bf==1)
      {
        RotateLR(parent);
      }
      else
      {
        assert(false);
      }
      break;
    }
    else if (parent->_bf == 0)
    {
      break;
    }
    else
    {
      assert(false);
    }
  }

  return true;
}

2.1 右子树高，继续往右子树的右边插入

示意图如下，图中bf就是平衡因子：

此时就需要我们进行调整，调整的方式就是左单旋，进行左单旋之后的树变化如下：

具体实现代码如下，左单旋与右单旋实现思路差不多：

//左单旋
void RotateL(Node* parent)
{
  Node* subR = parent->_right;
  //要注意这个节点可能为空，因为h可以等于0
  Node* subRL = subR->_left;
  
  //开始调整
  subR->_left = parent;
  parent->_right = subRL;
  
  //先记录下此时parent的parent，因为我们还要将subL与parent的parent进行连接
  Node* ppnode = parent->_parent;

  if (subRL)
    subRL->_parent = parent;
  parent->_parent = subR;
  
  //判断parent与它父亲节点之间的位置关系
  if (parent == _root)
  {
    _root = subR;
  }
  else if (ppnode->_left == parent)
  {
    ppnode->_left = subR;

  }
  else if(ppnode->_right == parent)
  {
    ppnode->_right = subR;
  }
  //进行连接
  subR->_parent = ppnode;

  //更新一下平衡因子
  parent->_bf = 0;
  subR->_bf = 0;
  if (subRL)
  {
    subRL->_bf = 0;
  }   
}

2.2 左子树高，继续往左子树的左边插入

插入的示意图如下：

那么此时就需要右单旋，旋转的示意图如下所示：

实现的代码如下所示：

//右单旋
void RotateR(Node* parent)
{
  Node* subL = parent->_left;
  Node* subLR = subL->_right;

  subL->_right = parent;
  parent->_left = subLR;

  Node* ppnode = parent->_parent;

  parent->_parent = subL;
  if (subLR)
    subLR->_parent = parent;

  if (parent == _root)
  {
    _root = subL;
  }
  else if (parent == ppnode->_left)
  {
    ppnode->_left = subL;
  }
  else if (parent == ppnode->_right)
  {
     ppnode->_right = subL;
  }
  subL->_parent = ppnode;

  subL->_bf = 0;
  if(subLR)
    subLR->_bf = 0;
  parent->_bf = 0;
}

2.3 左子树高，往左子树中的右子树中插入

插入的示意图如下所示：其实此时有两种情况，往右子树的右边插入，或者往右子树的左边插入，下图就是以往右子树中的右边插入

此时需要经过两次旋转，先左转在右转就可以调整为平衡二叉树了，也就是复用左转与右转的代码！调整之后如图所示：

此时我们可以发现，经过两次旋转之后，得到的平衡因子是不对的！所以经过两次旋转之后的平衡因子还需要我们进行调节！具体的实现代码如下：

void RotateLR(Node* parent)
{
  Node* subL = parent->_left;
  Node* subLR = subL->_right;
  int bf = subLR->_bf;

  RotateL(parent->_left);
  RotateR(parent);

  if (bf == -1)
  {
    subLR->_bf = 0;
    parent->_bf = 1;
    subL->_bf = 0;
  }
  else if (bf == 1)
  {
    subLR->_bf = 0;
    parent->_bf = 0;
    subL->_bf = -1;
  }
  else
  {
    subLR->_bf = 0;
    subL->_bf = 0;
    parent->_bf = 0;
  }
}

2.4 右子树高，往右子树中的左子树中插入

插入的示意图如下所示，插入的位置也有两个，分别为在左子树的左边或者在左子树的右边

然后进行双旋，先进行右旋，然后在进行左旋。从而调整成为平衡树！调整过程如下图所示：

具体的实现代码如下所示：

void RotateRL(Node* parent)
{
  Node* subR = parent->_right;
  Node* subRL = subR->_left;
  int bf = subRL->_bf;
  RotateR(subR);
  RotateL(parent);

  if (bf == -1)
  {
    subR->_bf = 1;
    subRL->_bf = 0;
    parent->_bf = 0;
  }
  else if (bf == 1)
  {
    subRL->_bf = 0;
    parent->_bf = -1;
    subR->_bf = 0;
  }
  else
  {
    parent->_bf = 0;
    subR->_bf = 0;
    subRL->_bf = 0;
  }
}

3 判断一棵树是否为平衡树

要判断一棵树是否是平衡树，就需要我们去计算左右两边的树的高度差，以及验证高度差是否等于该节点的平衡因子，有了这样的一个思路，实现的代码逻辑如下：

  int height(Node* root)
  {
    if (root == nullptr)
      return 0;
    int leftheight = height(root->_left);
    int rightheight = height(root->_right);

    return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
  }

  //判断一棵树是否是平衡二叉树
  bool isAVLTree(Node* root)
  {
    if (root == nullptr)
      return true;
    int leftheight = height(root->_left);
    int rightheight = height(root->_right);
    if (abs(leftheight - rightheight) >= 2)
    {
      return false;
    }
    if (rightheight - leftheight != root->_bf)
    {
      cout << "平衡因子出错了" << endl;
    }
    return isAVLTree(root->_left) && isAVLTree(root->_right);
  }

这样的写法过于冗余了，每次都需要计算树的高度，我们可以采用后序遍历的方式，计算出树的高度，利用引用，记录左右子树之间的高度，避免重复计算，写法如下所示：


  bool isAVLTree(Node* root, int& height)
  {
    if (root == nullptr)
      return true;
    int leftheight = 0;
    int rightheight = 0;
    if (!isAVLTree(root->_left,leftheight) || !isAVLTree(root->_right,rightheight))
    {
      return false;
    } 
    if (abs(leftheight - rightheight) >= 2)
    {
      return false;
    }
    if (rightheight - leftheight != root->_bf)
    {
      cout << "平衡因子出错了" << endl;
    }
    height = leftheight > rightheight ? leftheight + 1 : rightheight + 1;
  }

AVL树的原理以及实现