来自：Nicol的博客铭

作者：taozj

链接：https://taozj.org/2016/11/数据结构和算法（二）：AVL自平衡二叉树/（点击尾部阅读原文前往）

一、二叉树的基础知识

1.1 二叉树

二叉树(Binary Tree)是n个结点的有限集合，该集合或者为空集，或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成，且二叉树的左右要求是有顺序的。

1.1.1 特殊种类的二叉树

(1). 斜树：所有的结点都只有左子树的二叉树称为左斜树，所有结点都只有右子树的二叉树称为右斜树。
(2). 满二叉树：在一棵二叉树中，如果所有分支节点都存在左子树和右子树，而且所有叶子都在同一层上，称为满二叉树。
(3). 完全二叉树：对一棵具有n个节点的二叉树按层序编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，称为完全二叉树。在实际操作上，就是按照从上到下、从左到右这种层次顺序遍历各个元素，如果该出现元素的位置出现了空档，则不是完全二叉树。
根据定义我们可知，满二叉树是完全二叉树的一种特殊情况。

1.1.2 二叉树的性质

这里主要总结了二叉树结构中，数据元素、高度、父子节点位置的信息：
(1). 在二叉树的第i层上至多有2^(i-1)个结点。
(2). 深度为k的二叉树最多有2^k-1个结点。
(3). 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
(4). 具有n个结点的完全二叉树的深度为[log2(n)]+1，其中[x]表示不大于x的最大整数。满二叉树的度数k=log2(n+1)。
(5). 对一棵有n个结点的完全二叉树按照层序编号(从1层到[log2(n)]+1层，每层从左到右)，对任意一节点i，则有：

a. 如果i=1，则i是二叉树的根，无双亲；
b. 如果i>1，则其双亲是结点[i/2]；
c. 如果2i>n，则结点i无左孩子(结点i为叶子节点)，否则其左孩子是节点2i；

d. 如果2i+1>n，则节点i无右孩子，否则其右孩子为结点2i+1。
通常顺序方式(数组)存储二叉树结构也是十分的常见的，如果按照完全二叉树从顶部分层遍历的，所以上面列出的二叉树的孩子和父亲之间的位置关系，也就对应了在数组中元素的索引值，这在堆排序中会被应用的最为典型。

1.1.3 遍历二叉树

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点都被访问到一次且仅被访问一次。

(1). 前序遍历：先访问根节点，然后前序遍历左子树，再前序遍历右子树；
(2). 中序遍历：从根节点开始，中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树；
(3). 后序遍历：从左到右先叶子后结点的方式遍历访问左右子树，最后访问根节点；
(4). 层序遍历：从树的第一层开始，从上而下逐层遍历，在同一层次中，按照从左到右的顺序对结点逐个访问。

二叉树的遍历虽然在语言上描述起来较为的复杂，其实代码实现上极为的简单，就是左树递归、右树递归、根元素访问三种操作顺序的排列组合的结果而已；而且，对于前序递归，其输出则是得到的元素从小到大排列的：

1
2
3
4
5
6

void pre_order(SmartAvlNodePtr node) {
if (!node) return;
std::coutdata_", ";
pre_order(node->left_);
pre_order(node->right_);
}

当给定条件需要重建二叉树的时候，已知前序遍历序列和中序遍历序列，就可以唯一确定一棵二叉树；已知后序遍历序列和中序遍历序列，业可以唯一确定一棵二叉树；但是已知前序遍历序列和后序遍历序列，不能确定一棵二叉树。

1.2 二叉排序树(Binary Sort Tree, BST)

1.2.1 二叉排序树的性质

二叉排序树又称为二叉查找树，其如果不是空树，BST其具有以下性质(很显然，这是一个二叉树组织的递归定义)：

(1). 如果左子树不为空，则左子树上所有的节点都小于它的根结构的值；
(2). 若右子树不为空，则右子树上所有的节点都大于它的根结构的值；
(3). 其左右子树也分别是二叉排序树。

1.2.2 二叉排序树的操作

二叉排序树的操作包括查找、插入和删除，其中查找就是根据当前给定的键值和每个节点比较是否相等，如果不相等根据大小关系递归在左右子树上面去查找，这里我想到C++的很多标准库中表明，当查找某个值如果没有找到的话，其返回就是该值可以被插入的位置，此时想来不无道理。

插入操作和查找比较类似，也比较的简单，而删除的时候需要根据删除节点的情况分类来对待：

(1). 如果要删除的节点是叶子节点，其没有任何子树，那么就直接删除之；
(2). 如果要删除的节点仅有左子树或者仅有右子树，那么就将其对应的左子树或者右子树这个非空子树整个移动到删除节点的位置，以完成独子承父业；
(3). 如果要删除的节点其左右子树都有节点，具体的做法可以选择：

a. 要么沿着要删除节点的左子树，一直向右走，找出最右的节点，取出来替换该删除节点；

b. 或者沿着删除节点的右子树，一直向左走，找出最左的节点，然后替换之。

上面最后一种情况的删除原理，其实就是寻找待删除节点大小最相临的前驱或后驱来直接替代它，替代后整个二叉树还是保持有序的状态，同时替换的节点由于是选择的最左或者最右节点，其最多也就只有一个子数，所以替换节点的删除本身也是十分方便的，采用上面(2)的情况处理就可以了。

二叉树的性能取决于二叉树的层数，最好的情况是O(logn)，存在于完全二叉树情况下，其访问性能近似于折半查找；最差时候会是O(n)，比如在斜树的情况下，需要逐个遍历二叉树的元素才行。

1.3 自平衡二叉树(AVL)

前面说到，二叉树的查找、插入、删除操作的性能十分依赖于树的高度，所以如果能把树维持在一个完全二叉树的情况下，当然是最理想最高效的情况，所以在增加和删除这种会修改二叉树结构的操作中，能检测修改后的二叉树状态并修正之，限制二叉树的高度，即为平衡二叉树。

现实中绝对完全二叉树结构是很难维持的，而AVL作为最先发明的自平衡二叉树，通过对每个节点的左、右子树之间的高度差作出限定，同时在插入、删除的时候对不满足限定的子树进行一定的操作，以达到限制树的高度，从而保证其最优的查找性能。

AVL自平衡二规定每一个节点的左子树和右子树的高度差至多等于1，同时将二叉树上节点左子树高度减去右子树高度的值称为平衡因子BF，所以平衡的二叉树所有节点的平衡因子取值只可能是-1、0、1。

其它关于AVL自平衡二叉树的相关详细信息，将在下面实现部分再予以描述。

二、实现平衡二叉树

首先说道，AVL自平衡二叉树其本质上还是一个BST，所以AVL树的查找、添加和删除的基础操作都是上面描述到的BST的操作，只是在这些操作之后，需要修正节点的高度信息，在必要的情况下进行适当的操作来保证AVL树的约束。

本文借助于AVL Trees的实现，探究AVL树的插入、删除的维护过程。

2.1 旋转操作

2.1.1 基本旋转

不仅仅是AVL，几乎所有的平衡二叉树都是通过旋转调整来实现的。在树的旋转中有左旋和右旋两个最基本的操作，而实际中针对左右左、右左右等结构采用的双旋转，其实也是这种原子操作的组合而已。

看上面的图可知，左旋和右旋虽然结构表示不一，但是都保持了A

此时，A、B、C的子树都没有修改，而p、q的子树发生了变化，所以需要基于他们的子树修正p、q的高度。在传统学术上，AVL节点用一个字段保留记录平衡因子，但是这篇参考文章的作者建议保留树的高度信息height，因为一方面通过两个子树的height可以在需要的时候方便的计算出平衡因子，二来树的高度信息更新起来比较的方便明了，看看AvlTrees中维护平衡因子的分析就知道直接更新平衡因子是有多么麻烦了。不过这里的高度是一个绝对值，每次有修改的时候都必须让直接或者间接涉及到的节点全部更新调整，不过Nikolai Ershov的操作主要都是用递归方式来实现的，代码中绝大多数的操作都是返回修改或者平衡后的子树根节点，在递归函数中调用fix-height/rebalance会从最底层的修改节点一直检查处理到根节点去。

2.1.2 双旋转

双旋转通常在我们所称为的“左右左”或者“右左右”的情形下会发生，而这里也有专业的结论表示出来：当高度h(s)

(1). h(s)

(2). h(s)>h(D)，两次旋转

比如下面左旋操作的代码，这里一定要注意操作的顺序，同时在修复高度的时候父节点的高度是根据子节点直接计算出来的，所以修复的时候一定要先修复子节点，再修复当前节点。

1
2
3
4
5
6
7
8
9

SmartAvlNodePtr rotate_left(SmartAvlNodePtr node) {
SmartAvlNodePtr tmp_root = node->right_;
node->right_ = tmp_root->left_;
tmp_root->left_ = node;
fix_height(node);
fix_height(tmp_root);
return tmp_root;
}

2.2 插入操作

插入操作先是进行常规的BST插入，通过递归的方式查找插入点，然后创建新的节点，修改指针完成插入。

插入完成后，要沿着插入链沿着修改节点向树根的方向，递归调用rebalance调整树高度、计算平衡因子，并在必要的时候进行旋转修复操作。

1
2
3
4
5


4
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

SmartAvlNodePtr insert(SmartAvlNodePtr node, int data) {
if (!node) {
node = std::make_shared(data);
return node;
}
assert(data != node->data_);
if (data data_) {
node->left_ = insert(node->left_, data);
node = rebalance(node);
}
else if (data > node->data_){
node->right_ = insert(node->right_, data);
node = rebalance(node);
}
return node;
}
SmartAvlNodePtr rebalance(SmartAvlNodePtr node) {
fix_height(node);
int bal_factor = get_bal_factor(node);
if (bal_factor > 1) {
if (get_bal_factor(node->right_) 0) //rotate right first
node->right_ = rotate_right(node->right_);
return rotate_left(node);
}
else if (bal_factor -1) {
if (get_bal_factor(node->left_) > 0) //rotate right first
node->left_ = rotate_left(node->left_);
return rotate_right(node);
}
return node;
}

2.3 删除操作

平衡二叉树最复杂的就是删除操作了(包括后面的红黑树，其删除更加的复杂)，首先根据BST的基本删除方法，进行左右子树递归查找要删除的节点，当找到待删除的节点的时候：

(1). 如果要删除的当前节点没有右子树，那么用其左孩子代替它的方式来直接删除之；否则
(2). 查找右子树中最小节点，用这个最小节点替代当前节点的方式来删除该节点，同时从替代节点原位置开始，递归修复树的高度和平衡关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

SmartAvlNodePtr remove_right_min(SmartAvlNodePtr node) {
if (!node->left_)
return node->right_;
node->left_ = remove_right_min(node->left_);
return rebalance(node);
}
SmartAvlNodePtr remove(SmartAvlNodePtr node, int data) {
if (data data_)
node->left_ = remove(node->left_, data);
else if (data > node->data_)
node->right_ = remove(node->right_, data);
else
{
if (!node->right_)
return node->left_;
SmartAvlNodePtr repl = find_right_min(node->right_);
repl->right_ = remove_right_min(node->right_);
repl->left_  = node->left_;
return rebalance(repl);
}
return rebalance(node);
}

上面remove操作实际进行的步骤为:

a. find_right_min采用遍历的方式，实现在待删除节点的右子树种寻求最小的节点，作为选定的替换种子节点；
b. 调用一个remove_right_min的函数，注意这个函数也是一个递归函数，递归找到最小节点后用其右子树(无论是否为空)来替换这个节点以删除之，同时调用rebalance不断平衡直到待删除节点的右子树根部位置；
c. 修改repl的指针，接管待删除节点的左右子树资源；
d. 这个函数一旦返回(repl)，就用于顶替待删除节点在其父节点对齐引用，此时待删除节点智能指针引用递减(并被析构释放)；
e. 从删除节点的父节点开始，递归调用rebalance()到整个树的根，完成删除操作。

2.4 小结

自认为讲清楚了，其实AVL还算是比较简单的自平衡二叉树了。
这里所有的节点都是使用智能指针管理的，所以看不到传统实现中那么多的new delete了，通过析构函数打印调试信息，发现删除的时候对象是被析构了，智能指针大法好！

●本文编号275，以后想阅读这篇文章直接输入275即可。

●输入m可以获取到文章目录。

推荐：《15个技术类公众微信》

涵盖：程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。