AVL 树 - AVL Tree

Posted on In , Views: Word count in article: 720 Reading time ≈ 3 mins.

AVL Tree…

  • Single Rotation
  • Double Rotation

Property of AVL Tree

二叉自平衡树 AVL(Adelson-Velskii and Landis)

AVL Tree 是一种二叉树，其有一条平衡条件：

  • 树中所有节点，其左右树的高度差最大为 1（空树的高度定义为-1）

其平衡条件保证了树的高度为

构建 AVL 树时，有 种插入情况

  1. 在左树的左孩子上插入
  2. 在左树的右孩子上插入
  3. 在右树的右孩子上插入
  4. 在右树的左孩子上插入

Single Rotation

其中 两种情况可以通过单旋转 (Single Rotation) 解决，因为我们通过插入构建平衡树，插入之前整树平衡，插入之后出现了不平衡，那么我们可以找到理插入位置最近的一个不平衡节点

那么在这个节点上，以 为例，很容易想到其左树与右树高度差为 ，那么我们通过一次单右旋转，即可平衡，这是因为右旋后左树高度 ，右数高度 ，假设本来右树高度为 ，则左树高度为 ，旋转后两树高度均为 。同理， 可以通过单左旋转实现平衡

具体来说，单右旋转时

  • 将节点的左树的右孩子 (node->left->right) 作为节点的左树，随后将节点作为节点的左树的右孩子，并用节点的左树替换节点原来所在位置
right rotation
1
2
3
4
5
6
7
8
void rightRotate(TreeNode<T>*& k2) {
  TreeNode<T>* k1 = k2->left;
  k2->left = k1->right;
  k1->right = k2;
  k2->height = max(height(k2->left), height(k2->right)) + 1;
  k1->height = max(height(k1->left), k2->height) + 1;
  k2 = k1;
}

同理单左旋转时

  • 将节点的右树的左孩子 (node->right->left) 作为节点的右树，随后将节点作为节点的右树的左孩子，并用节点的右树替换节点原来所在位置
left rotation
1
2
3
4
5
6
7
8
void leftRotate(TreeNode<T>*& k2) {
  TreeNode<T>* k1 = k2->right;
  k2->right = k1->left;
  k1->left = k2;
  k2->height = max(height(k2->left), height(k2->right)) + 1;
  k1->height = max(k2->height, height(k1->right)) + 1;
  k2 = k1;
}

Double Rotation

对于 的情况，容易看出单旋转无法解决，因为此时出现不平衡是由于插入节点的祖父节点不平衡所造成（因为如果是父节点，那么必然先解决父节点的不平衡——单旋转）

以 为例，因为其插入节点在左子树的右孩子上，那么设左子树的左右孩子高度分别为 和 （不破坏父节点平衡），那么左子树高度为 ，因此右子树高度为 ，那么我们可以先对左子树进行一次单左旋转，随后左子树高度不变，但左孩子高度变为 ，右孩子高度变为 ，此时对于祖父节点来说，不平衡相当于在左子树的左孩子上插入，变为了单旋转情况，于是进行一次单右旋转即可解决不平衡

left-right rotation
1
2
3
4
void leftRightRotate(TreeNode<T>*& k3) {
  leftRotate(k3->left);
  rightRotate(k3);
}

同样的，对于 的情况，我们也可以对称的进行操作，对右子树进行单右旋转，随后进行单左旋转以实现平衡

right-left rotation
1
2
3
4
void rightLeftRotate(TreeNode<T>*& k3) {
  rightRotate(k3->right);
  leftRotate(k3);
}

Implement

AVL Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct TreeNode {
  TreeNode* left;
  TreeNode* right;
  T data;
  int height;
};
template <typename T>
class AVLTree {
 public:
  TreeNode<T>* root;
  AVLTree() : root(nullptr) {}

  void leftRotate(TreeNode<T>*& k2) {
    TreeNode<T>* k1 = k2->right;
    k2->right = k1->left;
    k1->left = k2;
    k2->height = max(height(k2->left), height(k2->right)) + 1;
    k1->height = max(k2->height, height(k1->right)) + 1;
    k2 = k1;
  }

  void rightRotate(TreeNode<T>*& k2) {
    TreeNode<T>* k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2->height = max(height(k2->left), height(k2->right)) + 1;
    k1->height = max(height(k1->left), k2->height) + 1;
    k2 = k1;
  }

  void leftRightRotate(TreeNode<T>*& k3) {
    leftRotate(k3->left);
    rightRotate(k3);
  }

  void rightLeftRotate(TreeNode<T>*& k3) {
    rightRotate(k3->right);
    leftRotate(k3);
  }

  int height(TreeNode<T>* t) const { return t == nullptr ? -1 : t->height; }

  void balance(TreeNode<T>*& t) {
    if (t == nullptr) {
      return;
    } else if (height(t->left) - height(t->right) > 1) {
      if (height(t->left->left) >= height(t->left->right)) {
        rightRotate(t);
      } else {
        leftRightRotate(t);
      }
    } else if (height(t->right) - height(t->left) > 1) {
      if (height(t->right->right) >= height(t->right->left)) {
        leftRotate(t);
      } else {
        rightLeftRotate(t);
      }
    }
    t->height = max(height(t->left), height(t->right)) + 1;
  }

  void insertImpl(T& data, TreeNode<T>*& t) {
    if (!t) {
      t = new TreeNode<T>;
      t->data = data;
      t->left = t->right = nullptr;
    } else if (data >= t->data) {
      insertImpl(data, t->right);
    } else if (data <= t->data) {
      insertImpl(data, t->left);
    }
    balance(t);
  }

  void insert(T& data) { insertImpl(data, root); }

  void BFS() {
    if (!root) return;
    queue<tuple<TreeNode<T>*, int, bool>> q;
    q.push({root, 0, false});
    int l = 0;
    while (q.size()) {
      auto [v, h, isNull] = q.front();
      q.pop();
      if (h != l) {
        cout << endl;
        l = h;
      }
      if (!isNull)
        cout << v->data << " ";
      else
        cout << "nil ";
      if (v && v->left)
        q.push({v->left, h + 1, false});
      else if (v)
        q.push({nullptr, h + 1, true});
      if (v && v->right)
        q.push({v->right, h + 1, false});
      else if (v)
        q.push({nullptr, h + 1, true});
    }
    cout << endl;
  }
};

int main() {
  vector<int> arr;
  for (int i = 0; i < 5; i++) arr.push_back(i);
  AVLTree<int> tr;
  for (int i : arr) {
    tr.insert(i);
  }
  tr.BFS();
  return 0;
}
/**
1 
0 3 
nil nil 2 4 
nil nil nil nil
*/