【C++】AVL樹（平衡搜尋二叉樹）

在上一篇C++部落格中，講述了關于搜尋二叉樹以及KVL樹的實作。也提到了搜尋二叉樹的最壞情況：插入的資料已經有序。

而本篇部落格涉及到的AVL樹，又稱平衡搜尋二叉樹。就是為了解決搜尋二叉樹的最壞情況而生的。

文章目錄

1. 什麼是AVL樹

1.1 二叉搜尋樹的性質

2. 實作一顆AVL樹

2.1 AVL樹的節點
2.2 AVL樹的插入（重要）

2.2.1 左/右單旋
2.2.2 左右/右左雙旋

2.3 AVL樹的搜尋
2.4 如何判斷是否符合AVL樹的性質

2.4.1 層序周遊（OJ題）
2.4.2 檢查平衡因子

2.5 利用随機值和順序值進行測試
2.6 AVL樹的删除
2.7 二叉樹性能

結語

1. 什麼是AVL樹

二叉搜尋樹雖然縮短了查找的效率，但是資料有序的時候，就會出現一邊非常長的情況，導緻原本的

O(logN)

時間複雜度被迫變成了

O(N)

平衡樹也是搜尋二叉樹，其引入了一個平衡因子的概念，用于控制搜尋二叉樹的平衡。它會保證左右子樹的高度之差（絕對值）不超過1。當新插入節點導緻高度之差超過1時，便會觸發旋轉，使得樹的高度降低。

簡單說來：AVL樹能保證兩邊高度的相對平衡，這樣就穩定了二叉搜尋樹的效率

1.1 二叉搜尋樹的性質

一顆AVL樹或空樹，其有以下性質

它的左右子樹是AVL樹
左右子樹的高度之差的絕對值不超過1

這裡引入平衡因子來友善我們控制二叉樹的高度。每一個節點都會有一個平衡因子，它的值是

1/0/-1

。如果平衡因子的值超過了1，那麼說明這個節點的子樹已經不平衡，需要進行旋轉。

實際上，AVL樹不一定非要用平衡因子。我們可以用計算樹的高度的方式來确認平衡因子，但是這樣需要周遊左右子樹，時間複雜度較高

2. 實作一顆AVL樹

2.1 AVL樹的節點

基本的概念了解之後，我們需要設計出一個節點的結構來。關于各個值的含義，可以參考下方的注釋

平衡搜尋二叉樹是一個“三叉鍊”。這代表每一個節點都有左右孩子，還有一個prev指針指向它的父節點。

為了辨別樹是否平衡，準确來說是某個節點的左右子樹是否平衡。我們需要引入一個“平衡因子”來進行判斷，友善我們控制平衡

左右子樹高度相同 0

左子樹高于右子樹 -1

右子樹高于左子樹 1

template<class K,class V>
struct AVLTreeNode
{
  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)
  {}
};

關于鍵值對的内容，在上篇部落格的KVL樹中有提到過【傳送門】

2.2 AVL樹的插入（重要）

因為AVL需要控制樹的高度，其插入的時候就沒有KVL樹那麼友善了。我們每次插入之後，都需要向上更新并判斷樹的平衡因子是否正常

先來理清一下思路:

如果是空樹，new一個新節點交給root，無需進行後續操作
插入新節點的時候，利用搜尋二叉樹的規則（在這裡我采用了左小右大的規則）來找到新節點應該插入的位置，直接進行插入
插入之後，需要向上更新平衡因子（利用父節點 parent ）

如果該插入節點在父節點的右邊，平衡因子+1
如果在該節點的左邊，平衡因子-1。

更新了平衡因子之後，需要及時進行判斷。如果平衡因子等于0，則不需要繼續往上更新。如果平衡因子的絕對值大于1，說明目前就需要旋轉了

根據這個思路，我們可以先寫出插入的一個基本架構

bool Insert(const pair<K, V>& kv)
  {
    //判斷root為空，即空樹
    if (_root == nullptr)
    {
      _root = new Node(kv);
      return true;
    }
    //kv樹的操作
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
            //利用key來判斷，尋找待插入的位置
      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--;//左-1
      }
      else{
        parent->_bf++;//右+1
      }

      //更新了之後，需要判斷是否繼續更新，還是需要旋轉
      if (parent->_bf == 0) {
        break;//為0代表高度沒有變化，不需要繼續更新
      }
      else if (parent->_bf == 1 || parent->_bf == -1)
      {
        cur = cur->_parent;//向上更新
        parent = parent->_parent;
      }
      else if (parent->_bf == 2 || parent->_bf == -2)
      {
        //旋轉
      }
      else
      {
        //插入之前AVL就存在不平衡子樹
        assert(false);
      }
    }
    return true;
  }

其中最複雜的部分：旋轉，需要拿出來單獨講解一番

下面是一個最簡單的二叉樹進行插入之後，平衡因子的變化。

因為搜尋二叉樹需要保證兩邊的

高度之差不大于1

，是以此時我們的樹還沒有違背AVL樹的規則。

可如果我們繼續往右子樹插入節點呢？

可以看到，最後一顆子樹的根節點的平衡因子為2，超過了1。此時兩邊子樹的高度差為2，需要我們進行旋轉操作

2.2.1 左/右單旋

為了簡化，我們把上圖的插入情況直接簡化為下面的樣子

當我們在這棵樹高度較高的那一側的邊緣插入的時候，就需要進行單旋。

比如右邊高，就是在最右邊的葉子處插入

單旋的思路很好了解，下面以左單旋為例（藍色代表新增節點）

這裡我們設定了3個不同的節點，分别是prev起始節點（即平衡因子大于1的節點）以及它的右子樹

subR

、右子樹的左子樹

subRL

（即圖中的b子樹）

需要做的操作，就是把 subRL 連結給 prev 的右，再将 prev 連結到 subR 的左
因為 subRL 在 prev 的右側，其的值肯定大于 prev ，是以這樣連結是不會破壞搜尋二叉樹的結構的。

旋轉完成之後，我們需要把

prev

和

subR

的平衡因子都更新為0

右單旋的操作和左單旋的思路完全相同，隻不過方向相反

思路搞定了，下面就來寫一個代碼吧！

void RotateL(Node* parent)//左單旋
{
    Node* prev = parent;
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    //用來記錄目前parent的父親，最後的連結需要
    Node* ppNode = parent->_parent;

    prev->_right = subRL;
    if (subRL != nullptr)
    {//不為空才能進行parent操作
        subRL->_parent = prev;
    }

    subR->_left = prev;
    prev->_parent = subR;

    if (prev == _root)
    {//單獨操作為根節點的情況
        //subR->_parent = nullptr;
        _root = subR;
        _root->_parent = nullptr;
    }
    else
    {
        if (prev == ppNode->_left) {
            ppNode->_left = subR;
        }
        else {
            ppNode->_right = subR;
        }
        subR->_parent = ppNode;
    }
    //預設全都改成0
    subR->_bf = parent->_bf = 0;
}

右單旋的代碼和這個類似，這裡就不貼出來了

完整代碼可以到我的代碼倉庫裡面看哦！【Gitee】

旋轉的代碼寫好了，我們現在還需要了解的是，什麼時候需要進行單旋？

看圖可以得知，當prev的平衡因子為-2，subL的平衡因子為-1的時候，需要進行一次右單旋

同理，我們可以推斷出一個結論，那就是當父節點的平衡因子的絕對值超過1，其左/右邊節點的平衡因子為1且和父節點平衡因子的正負相同時，需要向另外一個方向進行單旋。

左單旋

就是父節點為2，其右子樹為1，需要向另外一個方向左進行單旋

需要注意的是，雖然圖裡面畫出來的prev是根節點，但實際上進行單旋的時候，prev可能是另外一棵樹的子樹。在單旋的處理過程中，我們必須要儲存prev的父節點，并重新連結至

subR

//插入函數的旋轉部分
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
    {
        //……
    }
    break;
}

我們用下面的代碼進行測試

void TestAVLTree1()
{
  int a[] = {9,8,7,6,5,4,3,2,1 };
  AVLTree<int, int> t;
  for (auto e : a)
  {
    t.Insert(make_pair(e, e));
  }
  t.InOrder();
  cout << endl;
}

進行中序列印，可以擷取道下面的結果。可以看到資料已經有序

在VS2019的調試視窗中可以看到，我們廠家的這棵樹是符合平衡搜尋二叉樹的性質的

2.2.2 左右/右左雙旋

上面的情況還算容易，一次單旋就能解決。那如果我們插入不有序的資料呢？

可以看到中序列印的結果已經有序，可它符合平衡二叉樹的規則嗎？

再插入一個25，會發現觸發了斷言，說明AVL樹的規則被破壞了

就好比下面的這種情況，我們是以

15 6 7

這種非有序方式插入的，就會出現單旋完全處理不了的情況

如果進行單旋會發生什麼呢？

可以看到，毫無變化。旋轉了之後的節點依舊是違反AVL樹的規則

這時候我們就需要進行兩次循環了！

概念了解了之後，我們就可以直接來寫代碼了。

因為本質上就是兩次單旋，是以我們可以直接複用之前寫好的單旋代碼

void RotateLR(Node* parent)//左右
{
    RotateL(parent->_left);
    RotateR(parent);
}

但事情遠沒有這麼簡單！

在2.2.1單旋的操作中，我們旋轉完畢後會把prev和subL的平衡因子都改成了0。在這種雙旋的情況下，全改成0顯然不符合要求。

下面的情況，我們就需要在旋轉之後，把10的平衡因子改成-1，20和30的平衡因子改成0

雙旋的情況分為下面3種，我們可以直接用紫色框中所指的這個節點來判斷屬于哪一種情況，再針對性的處理！

處理之後的結果如下

其代碼邏輯如下

//這種雙旋轉的情況，基本如下
//   9
// 7
//   8
//必須要雙旋轉才能解決問題
void RotateLR(Node* parent)//左右
{
    Node* prev = parent;
    Node* subL = parent->_left;
    Node* subLR = subL->_right;
    int bf = subLR->_bf;

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

    if (bf == 0)
    {
        prev->_bf = 0;
        subL->_bf = 0;
        subLR->_bf = 0;
    }
    else if (bf == 1)
    {
        subL->_bf = -1;
        prev->_bf = 0;
        subLR->_bf = 0;
    }
    else if (bf == -1)
    {
        subL->_bf = 0;
        prev->_bf = 1;
        subLR->_bf = 0;
    }
    else {
        assert(false);
    }
}
void RotateRL(Node* parent)//右左
{
    Node* prev = parent;
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;

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

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

}

到這裡我們就可以把插入函數給補全了！

完整代碼可以到我的代碼倉庫裡面看哦！【Gitee】

還是剛剛的測試用例，這一次我們可以看到，它已經沒有報錯了！

2.3 AVL樹的搜尋

本質上AVL樹還是一個平衡二叉樹，是以搜尋肯定是少不了的！

它的搜尋和

KVL

樹完全一緻，利用key來進行搜尋，定位value。

是以，我們可以直接搬過來用。

//因為kvl樹我們需要修改value，是以傳回節點的指針
  Node* _FindR(Node* root, const K& key)
  {
    if (root == nullptr)
      return nullptr;

    if (root->_kv.first < key)
    {
      return _FindR(root->_right, key);
    }
    else if (root->_kv.first > key)
    {
      return _FindR(root->_left, key);
    }
    else
    {
      return root;//傳回節點的指針
    }
  }

上面的這個函數我們定義為私有，在公有裡面定義一個下面的函數

//查找是通過key來進行的
  Node* FindR(const K& key)
  {
    return _FindR(_root, key);
  }

測試一下可以看到，列印了全0的位址值，即

nullptr

，說明沒有找到34

2.4 如何判斷是否符合AVL樹的性質

如果每一次我們都要用調試去看目前的代碼是否符合二叉樹的性質，未免有些太麻煩了

下面我們有兩種辦法來簡潔地判斷！

2.4.1 層序周遊（OJ題）

下面的代碼是一道OJ題的答案，其要求是讓我們把樹每一層的節點都插入一個vector，最後傳回的是一個嵌套的

vector<vector<int>>

來自 https://leetcode.cn/problems/binary-tree-level-order-traversal/

因為我們目前測試的用例都是int類型，是以這裡就沒有用模闆參數。實際上我們應該改成key的類型

vector<vector<int>> levelOrder() 
{
  vector<vector<int>> vv;
  if (_root == nullptr)
    return vv;

  queue<Node*> q;
  int levelSize = 1;
  q.push(_root);

  while (!q.empty())
  {
    // levelSize控制一層一層出
    vector<int> levelV;
    while (levelSize--)
    {
      Node* front = q.front();
      q.pop();
      levelV.push_back(front->_kv.first);
      if (front->_left)
        q.push(front->_left);

      if (front->_right)
        q.push(front->_right);
    }
    vv.push_back(levelV);
    for (auto e : levelV)
    {
      cout << e << " ";
    }
    cout << endl;

    // 上一層出完，下一層就都進隊列
    levelSize = q.size();
  }

  return vv;
}

測試一下，可以看到每一層的結果，符合我們AVL樹的性質

2.4.2 檢查平衡因子

這裡我們用兩個遞歸函數，通過計算子樹的高度，來判斷是否滿足AVL樹的性質。

隻要兩個子樹的高度差大于1，就說明不是AVL樹

//計算高度
int _Height(Node* root)
{
    if (root == nullptr)
        return 0;

    int lh = _Height(root->_left);
    int rh = _Height(root->_right);
    //如果左子樹高于右子樹，就傳回左子樹+1（根）
    return lh > rh ? lh + 1 : rh + 1;
}
//判斷是否為平衡二叉樹
bool _IsBalanceTree(Node* root)
{
    // 空樹也是AVL樹
    if (nullptr == root)
        return true;

    // 計算pRoot節點的平衡因子：即pRoot左右子樹的高度差
    int leftHeight = _Height(root->_left);
    int rightHeight = _Height(root->_right);
    int diff = rightHeight - leftHeight;

    // 如果計算出的平衡因子與pRoot的平衡因子不相等，或者
    // pRoot平衡因子的絕對值超過1，則一定不是AVL樹
    if (abs(diff) >= 2)
    {
        cout << root->_kv.first << "節點平衡因子異常" << endl;
        return false;
    }

    if (diff != root->_bf)
    {
        cout << root->_kv.first << "節點平衡因子不符合實際" << endl;
        return false;
    }

    // pRoot的左和右如果都是AVL樹，則該樹一定是AVL樹
    return _IsBalanceTree(root->_left)
        && _IsBalanceTree(root->_right);
}

2.5 利用随機值和順序值進行測試

下面我們分别利用随機值和順序值測試AVL樹的正确性

void TestAVLTree2()
{
  const size_t N = 1024*1024;
  vector<int> v;
  v.reserve(N);
  srand(time(0));//使用随機數
  for (size_t i = 0; i < N; ++i)
  {
    v.push_back(rand());
    //v.push_back(i);
  }

  AVLTree<int, int> t;
  for (auto e : v)
  {
    t.Insert(make_pair(e, e));
  }

  cout << "是否平衡?" << t.IsBalanceTree() << endl;
  cout << "高度:" << t.Height() << endl;
}

利用随機數測試的結果如下

順序插入的結果如下

沒有問題辣！

2.6 AVL樹的删除

AVL樹的删除和KVL樹是基本相同的，但是我們需要更新平衡因子。

如果删除的是左節點，平衡因子+1
如果删除的是右節點，平衡因子-1

當我們遇到平衡因子錯誤（絕對值大于1）就需要進行旋轉

因為搜尋樹中一般不會進行删除，效率很低，是以這裡就不寫了！（懶）

2.7 二叉樹性能

在一些時候，搜尋二叉樹的性能并不會很高

比如當我們插入的元素已經有序，或者基本有序的時候，二叉樹的性能就和普通的容器差距不大了
AVL樹更适合于插入的元素不會被改變的情況。如果插入的元素需要經常被修改，那麼也不太适合。（比如删除的時候，AVL樹的平衡因子可能需要一直向上到根，時間複雜度不亞于二次插入）

結語

那麼本篇關于AVL樹的部落格到這裡就結束拉！

【C++】AVL樹（平衡搜尋二叉樹）

文章目錄

1. 什麼是AVL樹

1.1 二叉搜尋樹的性質

2. 實作一顆AVL樹

2.1 AVL樹的節點

2.2 AVL樹的插入（重要）

2.2.1 左/右單旋

2.2.2 左右/右左雙旋

2.3 AVL樹的搜尋

2.4 如何判斷是否符合AVL樹的性質

2.4.1 層序周遊（OJ題）

2.4.2 檢查平衡因子

2.5 利用随機值和順序值進行測試

2.6 AVL樹的删除

2.7 二叉樹性能

結語

繼續閱讀

swmm與lisflood-fp源碼如何一起編譯 CMake指令

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

hdu7108哈希