平衡树

Reference

http://www.cnblogs.com/skywang12345/p/3577360.html4

https://www.cnblogs.com/cg-wang/p/6096123.html

https://stackoverflow.com/questions/13484943/print-a-binary-tree-in-a-pretty-way

数据结构与算法课程资料

Intro

为什么需要AVL树

二叉查找树的高度越小,平均查找长度越小。

n 个结点的二叉查找树的高度最大为 n-1, 最小为 log2n.

别名及定义

AVL树是根据它的发明者G.M. Adelson-Velsky和E.M. Landis命名的。它是最先发明的自平衡二叉查找树,也被称为高度平衡树。

定义: 一棵AVL树或者是空树,或者是具有下列性质的二叉查找树:它的左子树和右子树都是AVL树,且左子树和 右子树的高度之差的绝对值不超过1。

1543046996408

AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)

如果在AVL树中插入或删除节点后,使得高度之差大于1。此时,AVL树的平衡状态就被破坏,它就不再是一棵二叉树;为了让它重新维持在一个平衡状态,就需要对其进行旋转处理

结点的平衡因子balance (balance factor)

  • 每个结点附加一个数字,给出该结点右子树的高度减去左子树的高度所得的高度差。这个数 字即为结点的平衡因子balance。
  • 根据AVL树的定义,任一结点的平衡因子只能取 -1,0和 1
  • 如果一个结点的平衡因子的绝对值大于1,则这 棵二叉查找树就失去了平衡,不再是AVL树。
  • 如果一棵二叉查找树是高度平衡的,它就为 AVL树。如果它有n 个结点,其高度可保持在 O(logn),平均查找长度也可保持在O(logn)

1543047268499

插入

  • 在向一棵本来是高度平衡的AVL树中插入 一个新结点时,如果树中某个结点的平
    衡因子的绝对值 |balance| > 1,则出现了 不平衡,需要做平衡化处理。
  • 算法从一棵空树开始,通过输入一系列 对象的关键字,逐步建立AVL树。在插入 新结点时使用算法进行平衡旋转

插入失衡的分析

根据平衡树的定义,平衡树上所有结点的平衡因子的绝对值都不超过1。在插入结点之后, 若查找树上某个结点的平衡因子的绝对值大于1, 则说明出现不平衡。同时,失去平衡的最小子树的根结点必然离插入结点最近,其平衡因子的绝对值在插入之前大于零。

插入的步骤

  1. 在查找S结点的插入位置过程中,记录与S结点最近,且平衡因子不等于零的结点a。
    如果需要旋转, 则必定对以a作为根节点的子树进行旋转, 且插入旋转前后该子树的高度不变
  2. 修改自a到S的路径上所有结点的平衡因子值。
    如果a和路径上它的子节点平衡因子同正负, 则进行单旋, 否则进行双旋.
  3. 判断树是否出现不平衡,即a的平衡因子是否大于1。
  4. 若出现不平衡,进行平衡调整。

删除

删除的步骤

  1. 找到被待删除节点curNode
  2. 寻找targetNode
    1. 如果curNode左子树非空, 以curNode左子树最大节点作为targetNode
    2. 不然, 如果curNode右子树非空, 以curNode右节点作为targetNode
    3. 不然, 删除curNode

失衡子树的平衡化旋转

  • 如果在一棵平衡的二叉查找树中插入一个新结点,造成了不平衡。此时必须调整树的结构,使之平衡化。
  • 每插入一个新结点时,AVL树中相关结点的平衡状态会发生改变。因此,在插入一 个新结点后,需要从插入位置沿通向根的路径回溯,检查各结点的平衡因子(左、右 子树的高度差)
  • 每次旋转只需要处理距离插入节点最近的问题节点, 其他节点都会正常.

失衡二叉树的四种姿势

1543047454045

281625317193879

寻找被旋转子树和旋转种类

判断L,R的方法是从根节点向新节点处方向更新balance, 当找到最后一个$|balance|>1$的节点, 这个节点即为最小失衡子树根节点. 从这个最小失衡子树根节点出发走向新节点, 观察经过这三个节点路径的形状, 以此来判断旋转种类.

旋转前后树的性质

  • 旋转后子树的高度和插入前一致, 所以我们无需更新上层节点平衡因子, 而且保证旋转后整棵树都是平衡的

LL—>右单旋转

1543048277743

  • 如果在子树E中插入一个新结点,该子树高度增1导致结点A的平衡因子变成+2,出现不平衡
  • 沿插入路径检查三个结点A、C和E。它们处于一条方向为“\”的直线上,需要做左单旋转。
  • 以结点C为旋转轴,让结点A反时针旋转
1
2
3
4
5
6
void rightRotate(PTreeNode& tree_node) {
PTreeNode old_root = tree_node;
tree_node = old_root->leftChild;
old_root->leftChild = tree_node->rightChild;
tree_node->rightChild = old_root;
}

RR—>左单旋转

1543048259247

  • 在左子树D上插入新结点使其高度增1,导致结点A的平衡因子增到-2,造成了不平衡。
  • 为使树恢复平衡,从A沿插入路径连续取3个结 点A、B和D,它们处于一条方向为“/”的直线 上,需要做右单旋转。
  • 以结点B为旋转轴,将结点A顺时针旋转。
1
2
3
4
5
6
void leftRotate(PTreeNode& tree_node) {
PTreeNode old_root = tree_node;
tree_node = old_root->rightChild;
old_root->rightChild = tree_node->leftChild;
tree_node->leftChild = old_root;
}

LR—>左右旋转

1543048348785

  • 在子树F或G中插入新结点,该子树的高度增1。 结点A的平衡因子变为-2,发生了不平衡。
  • 从结点A起沿插入路径选取3个结点A、B和E, 它们位于一条形如“<”的折线上,因此需要 进行先左后右的双旋转。
  • 首先以结点E为旋转轴,将结点B反时针旋转, 以E代替原来B的位置,做左单旋转。
  • 再以结点E为旋转轴,将结点A顺时针旋转, 做右单旋转。使之平衡化。
1
2
leftRotate(tree_node->leftChild);
rightRotate(tree_node);

RL—>右左旋转

1543048362473

  • 右左双旋转是左右双旋转的镜像。
  • 在子树F或G中插入新结点,该子树高度增1。 结点A的平衡因子变为2,发生了不平衡。
  • 从结点A起沿插入路径选取3个结点A、C和D, 它们位于一条形如“>”的折线上,需要进行 先右后左的双旋转。
  • 首先做右单旋转:以结点D为旋转轴,将结点C顺时针旋转,以D代替原来C的位置。
  • 再做左单旋转:以结点D为旋转轴,将结点A反时针旋转,恢复树的平衡。
1
2
rightRotate(tree_node->rightChild);
leftRotate(tree_node);

总结

中间自作聪明用height代替balance, 结果发现实现起来复杂很多, 连插入都得递归更新

删除部分未讨论, 因为觉得没必要将平衡树研究地太透彻, 大概思路是移动节点后自下向上递归更新高度, 每更新一层都必须平衡化旋转, 因为参考旋转的结果, 旋转前后高度减一, 很有可能引发雪崩反应.

我在stackoverflow找到一个rawPrint二叉树的函数

代码

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#pragma once

#include <queue>
#include <iostream>
#include <iomanip>

template<typename T>
class AvlTree
{
private:
struct TreeNode
{
TreeNode(TreeNode* l, TreeNode* r, T k, int h = 0)
: leftChild(l), rightChild(r), key(k), height(h)
{

}

int balance() const
{
return (rightChild ? rightChild->height : 0)
- (leftChild ? leftChild->height : 0);
}

void updateHeight()
{
int height_1 = leftChild ? leftChild->height : 0;
int height_2 = rightChild ? rightChild->height : 0;
height = 1 + (height_1 > height_2 ? height_1 : height_2);
}

TreeNode* leftChild;
TreeNode* rightChild;
T key;
int height;
};

typedef TreeNode* PTreeNode;

public:
AvlTree()
: mRoot(nullptr), mSize(0)
{

}

~AvlTree()
{
clear();
}

void rightRotate(PTreeNode& tree_node) {
PTreeNode old_root = tree_node;
tree_node = old_root->leftChild;
old_root->leftChild = tree_node->rightChild;
tree_node->rightChild = old_root;
}

void leftRotate(PTreeNode& tree_node)
{
PTreeNode old_root = tree_node;
tree_node = old_root->rightChild;
old_root->rightChild = tree_node->leftChild;
tree_node->leftChild = old_root;
}

void updateHeight(PTreeNode root, T key)
{
if (key < root->key) updateHeight(root->leftChild, key);
if (key > root->key) updateHeight(root->rightChild, key);

root->updateHeight();
}

PTreeNode find(T key)
{
PTreeNode node = mRoot;
while (node != nullptr) {
if (key == node->key) return node;
if (key < node->key) return find(node->leftChild);
if (key > node->key) return find(node->rightChild);
}
return nullptr
}

void insertStraight(PTreeNode* node_place, PTreeNode* &last_imbalance_node, T key)
{
if (*node_place == nullptr) *node_place = new TreeNode(nullptr, nullptr, key);
else if (key < (*node_place)->key) insertStraight(&(*node_place)->leftChild, last_imbalance_node, key);
else if (key > (*node_place)->key) insertStraight(&(*node_place)->rightChild, last_imbalance_node, key);
else ;

if (last_imbalance_node != nullptr) return;

(*node_place)->updateHeight();
int balance = (*node_place)->balance();
if (last_imbalance_node == nullptr && (balance == 2 || balance == -2))
last_imbalance_node = node_place;
}

void insert(T key)
{
// find insert place
PTreeNode* insert_place = &mRoot;
PTreeNode* last_imbalance_node = nullptr;

insertStraight(insert_place, last_imbalance_node, key);

if (last_imbalance_node) {
PTreeNode& tree_node = *last_imbalance_node;
if (key < tree_node->key) {
if (key < tree_node->leftChild->key) { // LL case R rotation
std::cout << "Rotated LL at: " << tree_node->key << std::endl;
rightRotate(tree_node);
tree_node->rightChild->height -= 2;
}
else { // LR case LR rotation
std::cout << "Rotated LR at: " << tree_node->key << std::endl;
leftRotate(tree_node->leftChild);
rightRotate(tree_node);
tree_node->height++;
tree_node->rightChild->height -= 2;
tree_node->leftChild->height -= 1;
}
}
else {
if (key > tree_node->rightChild->key) { // RR case L rotation
std::cout << "Rotated RR at: " << tree_node->key << std::endl;
leftRotate(tree_node);
tree_node->leftChild->height -= 2;
}
else { // RL case RL rotation
std::cout << "Rotated RL at: " << tree_node->key << std::endl;
rightRotate(tree_node->rightChild);
leftRotate(tree_node);
tree_node->height++;
tree_node->leftChild->height -= 2;
tree_node->rightChild->height -= 1;
}
}
}

mSize++;
}

void clearWorker(PTreeNode node) const
{
if (node->leftChild) clearWorker(node->leftChild);
if (node->rightChild) clearWorker(node->rightChild);
delete node;
}

void clear()
{
std::stack<PTreeNode> st;
if (mRoot) clearWorker(mRoot);
mSize = 0;
mRoot = nullptr;
}

void wfsPrint() const
{
using std::queue;
using std::cout;
using std::endl;

cout << "Size: " << mSize << " Height: " << (mRoot ? mRoot->height : 0) << endl;

queue<PTreeNode> wfs;
if (mRoot) wfs.push(mRoot);
while (!wfs.empty()) {
PTreeNode cur_node = wfs.front();
wfs.pop();
if (cur_node->leftChild) wfs.push(cur_node->leftChild);
if (cur_node->rightChild) wfs.push(cur_node->rightChild);
cout << cur_node->key << "(" << cur_node->balance() << ")" << " ";
}
cout << endl;
}

// https://stackoverflow.com/questions/13484943/print-a-binary-tree-in-a-pretty-way
void prettyPrintWorker(PTreeNode p, int indent = 0) const
{
if(p != NULL) {
if(p->rightChild) {
rawPrintWorker(p->rightChild, indent+4);
}
if (indent) {
std::cout << std::setw(indent) << ' ';
}
if (p->rightChild) std::cout<<" /\n" << std::setw(indent) << ' ';
std::cout<< p->key << "(" << p->height << "\n ";
if(p->leftChild) {
std::cout << std::setw(indent) << ' ' <<" \\\n";
rawPrintWorker(p->leftChild, indent+4);
}
}
}

void rawPrint() const
{
rawPrintWorker(mRoot);
std::cout << "Size: " << mSize << " Height: " << (mRoot ? mRoot->height : 0) << std::endl;
puts("---------------------");
}

private:
PTreeNode mRoot;
int mSize;
};
文章目录
  1. 1. Reference
  2. 2. Intro
    1. 2.1. 插入
  3. 3. 删除
    1. 3.1. 失衡子树的平衡化旋转
    2. 3.2. LL—>右单旋转
      1. 3.2.1. RR—>左单旋转
      2. 3.2.2. LR—>左右旋转
      3. 3.2.3. RL—>右左旋转
  4. 4. 总结
  5. 5. 代码
|