数据结构重读 – 平衡二叉树(AVL树)

大二那会根本没蹋下心来看,觉得天书一般,连旋转都没搞明白。

今天仔细看了书,发现真的一点不难啊,鄙视自己……

首先是概念:

平衡二叉树是为了解决前面二叉排序树不均衡的问题,而加入了一种平衡机制。所以,平衡二叉树是一种特殊的二叉排序树(BST)

AVL树查找的平均和最差复杂度都是O(logn) !!!(BST的最坏是O(n))

AVL树的插入复杂度是O(logn)。

平衡二叉树(简称AVL树):对任意一个结点,它的左子树和又子树都是平衡二叉树(左子树都小于结点,右子树都大于结点),且左子树深度和右子树深度不超过1。

书上那个平衡因子的概念只是为了辅助书上的实现方法,没有太大意义。

一般是在AVL树的构造(插入)阶段,做树的平衡处理(左、右旋),使得它称为一个平衡二叉树。

可以证明,AVL树的深度是logN

中序遍历AVL树(其实这是二叉排序树),可以从小到大还原出一个序列

下面的图摘自董师兄的博客《数据结构之AVL树》

一般,我们在插入时会遇到4种不平衡情况:

(1)Insert在左子树的左子树,此时需要根右旋转。

(2)Insert在左子树的右子树,此时先要对左子树左旋转,然后对根右旋转。

(3)Insert在右子树的右子树,此时需要根左旋转。

(4)Insert在右子树的左子树,此时先要对右子树右旋转,然后对根左旋转。

我们的实现中,没有用平衡因子,而是直接记录每个结点子树的深度,如下:

为了方便处理null结点的深度,我们定义如下深度函数:

当空结点为-1时,它的父亲结点+1正好是0。

然后是左旋操作:

特别注意:更新结点时要先更新下面的(原tree结点),再更新新的mid

返回要返回mid。

同理,右旋操作:

好了,下面是插入的代码:

特别注意,Java中的引用实际是C++中的指针,即对函数传入的“临时变量”修改,将不会影响外围原变量

因此,我们每次需要返回这个树引用。调用时也应该是

查找和排序二叉树一样的,如下:

好了,上面的版本有点土,用了Java还用static,下面这个版本是将AVLNode封装在了类内。调用时候不用在保存更新的AVLNode了,内部处理了,如下:

 

 

Leave a Reply

Your email address will not be published.