一篇文章教会你什么是高度平衡二叉搜索(AVL)树（下）-阿里云开发者社区

3.3 新节点插入较高左子树的右侧—左右：先左单旋再右单旋

void RotateLR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
    RotateL(parent->_left);
    RotateR(parent);
    subLR->_bf = 0;
    if (bf == 1)//上图为例,新增节点在c下方
    {
        parent->_bf = 0;
        subL->_bf = -1;
    }
    else if (bf == -1)//上图为例,新增节点在b下方
    {
        parent->_bf = 1;
        subL->_bf = 0;
    }
    else if (bf == 0)//上图为例,无其他子树,60为新增节点的情况
    {
        parent->_bf = 0;
        subL->_bf = 0;
    }
    else
    {
        assert(false);
    }
}

首先，保存父节点 parent 的左子树 subL 和 subL 的右子树 subLR 的指针，以及 subLR 的平衡因子 bf。
对 parent 的左子树 subL 进行左旋转操作，以调整子树的结构。
然后，对 parent 进行右旋转操作，以将 subL 成为 parent 的右子树。
将 subLR 的平衡因子 _bf 设置为0，因为它在旋转后的位置高度没有变化。
根据subLR的平衡因子bf的不同值来更新节点的平衡因子：

如果 bf 为1，表示 subL 的左子树高度大于右子树，将 parent 的平衡因子设置为0，subL 的平衡因子设置为-1。
如果 bf 为-1，表示 subL 的右子树高度大于左子树，将 parent 的平衡因子设置为1，subL 的平衡因子设置为0。
如果 bf 为0，表示 subL 的左右子树高度相等，将 parent 和 subL 的平衡因子都设置为0。

如果 bf 不是1、-1或0，那么会触发 assert(false)，表示出现了异常情况。

3.4 新节点插入较高右子树的左侧—右左：先右单旋再左单旋

void RotateRL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    subRL->_bf = 0;
    if (bf == 1)
    {
        subR->_bf = 0;
        parent->_bf = -1;
    }
    else if (bf == -1)
    {
        subR->_bf = 1;
        parent->_bf = 0;
    }
    else if (bf == 0)
    {
        parent->_bf = 0;
        subR->_bf = 0;
    }
    else
    {
        assert(false);
    }
}

首先，保存父节点 parent 的右子树 subR 和 subR 的左子树 subRL 的指针，以及 subRL 的平衡因子 bf。
对 parent 的右子树 subR 进行右旋转操作，以调整子树的结构。
然后，对 parent 进行左旋转操作，以将 subR 成为 parent 的左子树。
将 subRL 的平衡因子 _bf 设置为0，因为它在旋转后的位置高度没有变化。
根据subRL的平衡因子bf的不同值来更新节点的平衡因子：

如果 bf 为1，表示 subRL 的左子树高度大于右子树，将 subR 的平衡因子设置为0，parent 的平衡因子设置为-1。
如果 bf 为-1，表示 subRL 的右子树高度大于左子树，将 subR 的平衡因子设置为1，parent 的平衡因子设置为0。
如果 bf 为0，表示 subRL 的左右子树高度相等，将 parent 和 subR 的平衡因子都设置为0。

如果 bf 不是1、-1或0，那么会触发 assert(false)，表示出现了异常情况。

原理同先左单旋再右单旋

总结：

假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑

pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR

当pSubR的平衡因子为1时，执行左单旋

当pSubR的平衡因子为-1时，执行右左双旋

pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL

当pSubL的平衡因子为-1是，执行右单旋

当pSubL的平衡因子为1时，执行左右双旋

旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。

4.AVL树的验证

4.1 验证其为二叉搜索树

中序遍历可得到一个有序的序列，就说明为二叉搜索树

void InOrder()
{
    _InOrder(_root);
    cout << endl;
}
private:
    void _InOrder(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_kv.first << ":" << root->_kv.second << endl;
        _InOrder(root->_right);
    }

首先，检查当前节点 root 是否为空（即树是否为空）。如果为空，则返回，结束递归。
接着，递归地调用 _InOrder 函数，遍历左子树 root->_left。这将按照升序访问左子树中的节点。
然后，输出当前节点 root 的关键字和关联的值，通常使用 cout 输出到控制台。
最后，再次递归调用 _InOrder 函数，遍历右子树 root->_right。这将按照升序访问右子树中的节点。

4.2 验证其为平衡树

每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
节点的平衡因子是否计算正确

高度成员函数

int Height(Node* root)
{
    if (root == nullptr)
        return 0;
    return max(Height(root->_left), Height(root->_right)) + 1;
}

首先，检查当前节点 root 是否为空（即树是否为空）。如果为空，则返回高度0，表示空树的高度为0。
如果当前节点 root 不为空，那么递归地调用 Height 函数来计算左子树的高度和右子树的高度。
使用 max 函数比较左子树和右子树的高度，然后加上1（当前节点的高度），得到整棵树的高度。
返回树的高度作为函数的结果。

平衡树检测函数

bool IsBalance()
{
    return _IsBalance(_root);
}
private:
  bool _IsBalance(Node* root)
  {
    if (root == nullptr)
    {
      return true;
    }
    int leftHT = Height(root->_left);
    int rightHT = Height(root->_right);
    int diff = rightHT - leftHT;
    if (diff != root->_bf)
    {
      cout << root->_kv.first << "平衡因子异常" << endl;
      return false;
    }
    return abs(diff) < 2
      && _IsBalance(root->_left)
      && _IsBalance(root->_right);
  }

首先，检查当前节点 root 是否为空（即树是否为空）。如果为空，则返回 true，因为空树是平衡的。
如果当前节点 root 不为空，那么首先计算左子树和右子树的高度，分别存储在 leftHT 和 rightHT 中。
然后，计算左子树和右子树高度差（右子树高度减去左子树高度），存储在 diff 变量中。
检查当前节点的平衡因子 _bf 是否等于 diff，如果不相等，表示平衡因子异常，输出错误信息并返回 false。
继续检查当前节点是否满足AVL树的平衡条件，即平衡因子的绝对值不超过1，以及递归检查左子树和右子树是否也是平衡的（调用 _IsBalance 函数）。
如果所有条件都满足，返回 true 表示当前子树是平衡的。

4.3 验证用例

常规场景1

{16, 3, 7, 11, 9, 26, 18, 14, 15}

特殊场景2

{4, 2, 6, 1, 3, 5, 15, 7, 16, 14}

AVL树实现及验证所有代码

1.AVL代码实现

AVL.hpp

#pragma once
#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
  AVLTreeNode<K, V>* _left;
  AVLTreeNode<K, V>* _right;
  AVLTreeNode<K, V>* _parent;
  pair<K, V> _kv;
  int _bf;
  AVLTreeNode(const pair<K, V>& kv)
    :_left(nullptr)
    , _right(nullptr)
    , _parent(nullptr)
    , _kv(kv)
    , _bf(0)
  {}
};
template<class K, class V>
struct 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->_right)
      {
        parent->_bf++;
      }
      else
      {
        parent->_bf--;
      }
      if (parent->_bf == 0)
      {
        break;
      }
      else if (abs(parent->_bf) == 1)
      {
        parent = parent->_parent;
        cur = cur->_parent;
      }
      else if (abs(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)
        {
          RotateLR(parent);
        }
        else if (parent->_bf == 2 && cur->_bf == -1)
        {
          RotateRL(parent);
        }
        else
        {
          assert(false);
        }
        break;
      }
      else
      {
        assert(false);
      }
    }
    return true;
  }
  void InOrder()
  {
    _InOrder(_root);
    cout << endl;
  }
  bool IsBalance()
  {
    return _IsBalance(_root);
  }
private:
  int BalanceFactor(Node* node)
  {
    if (node == nullptr)
    {
      return 0;
    }
    return Height(node->_left) - Height(node->_right);
  }
  bool _IsBalance(Node* root)
  {
    if (root == nullptr)
    {
      return true;
    }
    int leftHT = Height(root->_left);
    int rightHT = Height(root->_right);
    int diff = rightHT - leftHT;
    if (diff != root->_bf)
    {
      cout << root->_kv.first << "平衡因子异常" << endl;
      return false;
    }
    return abs(diff) < 2
      && _IsBalance(root->_left)
      && _IsBalance(root->_right);
  }
  int Height(Node* root)
  {
    if (root == nullptr)
      return 0;
    return max(Height(root->_left), Height(root->_right)) + 1;
  }
  void RotateL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    parent->_right = subRL;
    if (subRL)
      subRL->_parent = parent;
    Node* ppNode = parent->_parent;
    subR->_left = parent;
    parent->_parent = subR;
    if (_root == parent)
    {
      _root = subR;
      subR->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subR;
      }
      else
      {
        ppNode->_right = subR;
      }
      subR->_parent = ppNode;
    }
    subR->_bf = parent->_bf = 0;
  }
  void RotateR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    parent->_left = subLR;
    if (subLR)
      subLR->_parent = parent;
    Node* ppNode = parent->_parent;
    subL->_right = parent;
    parent->_parent = subL;
    if (_root == parent)
    {
      _root = subL;
      subL->_parent = nullptr;
    }
    else
    {
      if (ppNode->_left == parent)
      {
        ppNode->_left = subL;
      }
      else
      {
        ppNode->_right = subL;
      }
      subL->_parent = ppNode;
    }
    subL->_bf = parent->_bf = 0;
  }
  void RotateLR(Node* parent)
  {
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;
    RotateL(parent->_left);
    RotateR(parent);
    subLR->_bf = 0;
    if (bf == 1)
    {
      parent->_bf = 0;
      subL->_bf = -1;
    }
    else if (bf == -1)
    {
      parent->_bf = 1;
      subL->_bf = 0;
    }
    else if (bf == 0)
    {
      parent->_bf = 0;
      subL->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }
  void RotateRL(Node* parent)
  {
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    subRL->_bf = 0;
    if (bf == 1)
    {
      subR->_bf = 0;
      parent->_bf = -1;
    }
    else if (bf == -1)
    {
      subR->_bf = 1;
      parent->_bf = 0;
    }
    else if (bf == 0)
    {
      parent->_bf = 0;
      subR->_bf = 0;
    }
    else
    {
      assert(false);
    }
  }
  void _InOrder(Node* root)
  {
    if (root == nullptr)
    {
      return;
    }
    _InOrder(root->_left);
    cout << root->_kv.first << ":" << root->_kv.second << endl;
    _InOrder(root->_right);
  }
private:
  Node* _root = nullptr;
};

2.AVL验证代码实现

AVLTEST.cpp

#include "AVL.hpp"
int main()
{
    //int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
    int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    AVLTree<int, int> avl1;
    for (auto e : a)
        avl1.Insert(make_pair(e, e));
    avl1.InOrder();
    cout << "IsBlance:" << avl1.IsBalance() << endl;
    return 0;
}

一篇文章教会你什么是高度平衡二叉搜索(AVL)树（下）

3.3 新节点插入较高左子树的右侧—左右：先左单旋再右单旋

3.4 新节点插入较高右子树的左侧—右左：先右单旋再左单旋

4.AVL树的验证

4.1 验证其为二叉搜索树

4.2 验证其为平衡树

4.3 验证用例

AVL树实现及验证所有代码

1.AVL代码实现

2.AVL验证代码实现

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

一篇文章教会你什么是高度平衡二叉搜索(AVL)树（下）

3.3 新节点插入较高左子树的右侧—左右：先左单旋再右单旋

3.4 新节点插入较高右子树的左侧—右左：先右单旋再左单旋

4.AVL树的验证

4.1 验证其为二叉搜索树

4.2 验证其为平衡树

4.3 验证用例

AVL树实现及验证所有代码

1.AVL代码实现

2.AVL验证代码实现

热门文章

最新文章

相关电子书