好久没更新了,今天来讲二叉树的一个重要应用:二叉搜索树。这次介绍的是平衡二叉树(
也叫AVL
树),
刚开始本来想自己写这篇文章的,书上关于AVL
树这里讲得很复杂(
我是看了半天才看懂)
。好了,废话少说,一起来看吧~
平衡二叉树
(AVL
树
)
这个恐怕是整个《数据结构》教科书里面最难的和最“没用”的数据结构了(
现在的教科书还有部分算法内容)
。说它没用,恰恰是因为它太有用——有着和普通的二叉搜索树完全一样的接口界面,绝大多数情况下比普通的二叉搜索树效率高(
很多)
。因此,通常情况下,人们都是一劳永逸的——写完后就重用,而不会再写了。所以说,你虽然学完了平衡二叉树,但很可能你永远也不会亲自写一个。你现在随便在身边拉个人,让他来写一个,能顺利的写出来的恐怕不多,玩笑之词,且勿当真。
在开始写之前,我很担心,能不能把这部分写清楚,毕竟书上满天的
switch…case
,并且还只是一半——有左旋没有右旋,有插入没有删除。后来,我变得有信心了——因为书上都没有说清楚,都在那里说梦话
。我没有找到
AVL
树的发明者的原著(
G. M. Adelson-Velskii and Y. M. Landis
. An algorithm for the organization of information
. Soviet Math. Dokl., 3:1259--1262, 1962.
)
也不知道我下面所写的是不是体现了发明者的本意
,
但至少
,
我认为现在的教科书歪曲了发明者的本意。
基本概念
Ø
平衡
下面的引文出自Algorithms and Data Structures
(Niklaus Wirth
, Prentice-Hall, Englewood Cliffs, NJ, 1986 ISBN: 0-13-022005-1 pp. 215–226
)
One such definition of balance has been postulated by Adelson-Velskii and Landis [4-1]. The balance criterion is the following:
A tree is balanced
if and only if for every node the heights of its two subtrees differ by at most 1.
Trees satisfying this condition are often called AVL-trees (after their inventors). We shall simply call them balanced trees
because this balance criterion appears a most suitable one. (Note that all perfectly balanced trees are also AVL-balanced.)
The definition is not only simple, but it also leads to a manageable rebalancing procedure
and an average search path length practically identical to that of tbe perfectly balanced tree.
科技文都比较好懂,本人翻译水平比较差,就不献丑了,我只想让大家注意最后一段的画线部分,平衡化应该是易于操作的
,而绝不是现在你在书上看到的铺天盖地的
switch…case
。
Ø
旋转
平衡化靠的是旋转。参与旋转的是3
个节点(
其中一个可能是外部节点NULL)
,旋转就是把这3
个节点转个位置。注意的是,左旋的时候p->right
一定不为空,右旋的时候p->left
一定不为空,这是显而易见的。
可以看到,左旋确实是在向“
左”
旋转,还是很形象的。右旋是左旋的镜像,就不再另行说明了。下表是左旋和右旋各个节点的指针变换情况。(
括号表示NULL
的情况不执行)
左旋 |
右旋 |
||
t->parent = p->parent |
p->parent = t |
t->parent = p->parent |
p->parent = t |
(t->left->parent = p) |
p->right = t->left |
(t->right->parent = p) |
p->left = t->right |
t->left = p |
p = t |
t->right = p |
p = t |
Ø
平衡因子
(
bf
——
balance factor
)
AVL
树的平衡化靠旋转,而是否需要平衡化,取决于树中是否出现了不平衡。为了避免每次判断平衡时,都求一下左右子树的高度,引入了平衡因子。很可能是1962
年的时候AV&L
没有亲自给出定义,时下里平衡因子的定义乱七八糟——我看了4
本书,两本是bf
= 左高-右高,两本是bf
= 右高-左高。最有意思的是两本中国人(
严蔚敏和殷人昆)
写的一本左减右,一本右减左;两本外国人写的也是这样。虽然没什么原则上的差别,可苦了中国的莘莘学子们——考试的时候可不管你是哪个门派的。我照顾自己的习惯,下面的bf =
左高-右高,习惯不同的请自己注意。
这样一来,是否需要平衡化的条件就很明了了——|bf| > 1
。如果从空树开始建立,并时刻保持平衡,那么不平衡只会发生在插入删除操作上,而不平衡的标志就是出现bf == 2
或者 bf == -2
的节点。
插入和删除
在AVL
树插入和删除,实际上就是先按照普通二叉搜索树插入和删除,然后再平衡化。可以肯定的说,插入和删除需要的最多平衡化次数不同(
下面会给出根本原因)
,但这不表明插入和删除时的平衡化的思路有很大差别。现有的教科书,仅仅从表面上看到了到了平衡化操作次数不同的假象,而没有从根本上认识到插入和删除对称的本质
,搞得乱七八糟不说(
铺天盖地的switch…case)
,还严重的误导了读者——以为删除操作复杂的不可捉摸。
AVL
树体现了一种平衡的美感,两种旋转是互为镜像的,插入删除是互为镜像的操作,没理由会有那么大的差别。实际上,平衡化可以统一的这样来操作:
1
.while (current != NULL)
修改current
的平衡因子。
Ø
插入节点时
current->bf += (current->data > *p)?1:-1;
Ø
删除节点时
current->bf -= (current->data > *p)?1:-1;
Ø
current
指向插入节点或者实际删除节点的父节点,这是普通二叉搜索树的插入和删除操作带来的结果。
*p
初始值是插入节点或者实际删除节点的
data
。因为删除操作可能实际删除的不是
data
。
2
.
判断是否需要平衡化
if (current->bf == -2) L_Balance(c_root); else if (current->bf == 2) R_Balance(c_root);
3
.
是否要继续向上修改父节点的平衡因子
Ø
插入节点时
if (!current->bf) break;
这时,以
current
为根的子树的高度和插入前的高度相同。
Ø
删除节点时
if (current->bf) break;
这时,以
current
为根的子树的高度和删除前的高度相同
Ø
之所以删除操作需要的平衡化次数多,就是因为平衡化不会增加子树的高度,但是可能会减少子树的高度,在有有可能使树增高的插入操作中,一次平衡化能抵消掉增高;在有可能使树减低的删除操作中,平衡化可能会带来祖先节点的不平衡
。
4
.
当前节点移动到父节点,转
1
p = &(current->data); current = current->parent;
完整的插入删除函数如下:
insert(
const
T
&
data) {
if
(
!
BSTree
<
T
>
::insert(data))
return
false
;
const
T
*
p
=
&
data;
while
(current) {
current
->
bf
+=
(current
->
data
>
*
p)
?
1
:
-
1
;
if
(current
->
bf
==
-
2
) L_Balance(c_root);
else
if
(current
->
bf
==
2
) R_Balance(c_root);
if
(
!
current
->
bf)
break
;
p
=
&
(current
->
data);
current
=
current
->
parent;
}
return
true
;
}
bool
remove(
const
T
&
data) {
if
(
!
BSTree
<
T
>
::remove(data))
return
false
;
const
T
*
p
=
&
r_r_data;
//
在class BSTree里添加proteceted: T r_r_data,
//
在BSTree<T>::remove(const T &data)
//
里修改为实际删除的节点的data
while
(current) {
current
->
bf
-=
(current
->
data
>
*
p)
?
1
:
-
1
;
if
(current
->
bf
==
-
2
) L_Balance(c_root);
else
if
(current
->
bf
==
2
) R_Balance(c_root);
if
(current
->
bf)
break
;
p
=
&
(current
->
data);
current
=
current
->
parent;
}
return
true
;
}
你可以看到,他们是多么的对称。
平衡化
显然的,平衡化后的子树应该是平衡的,以此为原则,很容易得知在各种情况下应该怎么旋转。
:
void
L_Balance(BTNode
<
T
>*
&
p) {
if
(p
->
right
->
bf
==
1
) R_Rotate(p
->
right);
L_Rotate(p); current
=
p;
}
void
R_Balance(BTNode
<
T
>*
&
p) {
if
(p
->
left
->
bf
==
-
1
) L_Rotate(p
->
left);
R_Rotate(p);
current
=
p;
}
他们也是对称的。
修改平衡因子
这是整个AVL
树能运转的核心,现在的教科书,也正是因为没有真正弄明白如何修改平衡因子,才搞的switch…case
满天飞。平衡因子的变化发生在旋转中——正因为这样,旋转才能有平衡化的作用——所以,应该把修改平衡因子的工作放在旋转操作中,而不是放在平衡化中。让我们来看看可能的旋转会带来的平衡因子变化的情况:
左旋(旋转后p |
右旋(旋转后p |
|||||||
旋转前p |
旋转前t |
旋转后p |
旋转后t |
旋转前p |
旋转前t |
旋转后p |
旋转后t |
|
-2 |
0 |
-1 |
1 |
2 |
0 |
1 |
-1 |
|
-2 |
-1 |
0 |
0 |
2 |
1 |
0 |
0 |
|
-2 |
-2 |
1 |
0 |
2 |
2 |
-1 |
0 |
|
-1 |
0 |
0 |
1 |
1 |
0 |
|