平衡二叉树 —— AVL树

上篇二叉树的文章中,我们提到了在某些极端情况下,二叉树就会退化成链表。复杂度从O(log2N)退化成O(N)

为了解决这个问题,首先被提出来的平衡树的方式是AVL树,然后提出来的是Tree Heap树,最后目前在实践中最为高效的红黑树。

在这篇文章中我们重点放在AVL树上,其他树以后有机会的话再去了解。

一、 定义

父节点的左子树和右子树的高度之差不能大于1,也就是说不能高过1层,否则该树就失衡了,此时就要旋转节点,在编码时,我们可以记录当前节点的高度,比如空节点是-1,叶子节点是0,非叶子节点的height往根节点递增。

avl树高度定义

高度为 h 的 AVL 树,节点数N 最多2^h − 1; 最少N(h)=N(h−1) + N(h−2) + 1
最少节点数n 如以斐波那契数列可以用数学归纳法证明:
即:
N(0) = 0 (表示 AVL Tree 高度为0的节点总数)
N(1) = 1 (表示 AVL Tree 高度为1的节点总数)
N(2) = 2(表示 AVL Tree 高度为2的节点总数)
N(h)=N(h−1) + N(h−2) + 1 (表示 AVL Tree 高度为h的节点总数)

二、旋转

二叉树选择一般分为以下四种情况。

1、左左旋转(左子树的左边节点)

旋转-左左旋转

如图,可以看到节点1造成了节点3节点6之间高度差大于绝对值1了,那么就处于不平衡状态。此时就需要将节点3左移就可以达到平衡状态。

2、右右旋转(右子树的右边节点)
旋转-右右旋转

如图,右右旋转与左左旋转差不多。

3、左右旋转(左子树的右边节点)
旋转-左右旋转

如图,左右旋转需要通过2次旋转之后才能达到平衡,首先以节点5为中心进行右右旋转,然后再以节点10为中心进行左左旋转。

为什么需要2次呢?只进行一次以节点10为中心的左左旋转不能达到平衡吗?如下图,二叉树会再次进入不平衡状态。
旋转-左右旋转-错误师范

4、右左旋转(右子树的左边节点)
旋转-右左旋转

与左右旋转原理类似,先进行左左旋转,再进行右右旋转。

三、代码实现

四、 扩展

1、是否支持范围查找
因为数据是有序的,所以理论上来说是能够支持范围查找的,但从细节来说,支持的方法却不是完全相同。

2、集合是否能够随着数据的增长而自动扩展
当然

3、读写性能如何
在内存中指针的跳转速度虽然不如使用数组快,不过也是很快的,基本上我们可以认为查询效率就是O(log2N), 对于写来说,效率也是O(log2N)

4、是否面向磁盘结构
磁盘的特性,一次取出一块数据,能比较好的处理顺序读写,而对随机读写则不擅长。
对于内存来说,根据指针的要求在内存中进行跳跃,代价并不高,但如果这个操作在磁盘中进行,那么根据指针的要求的每一次跳跃,都是一次磁盘的随机读写,因为在取出节点来实际看看之前,我们无法预测这个父节点的子节点被放在磁盘的哪个位置上的。那么查询一次数据需要跳跃多少次呢?O(log2N-1)次。。跳跃的次数还是非常夸张的。
因此,平衡二叉查找树,不是个面向磁盘的结构。

5、并行指标
不大适合并行操作,在进行结构调整的时候读取肯定是错误的,能够使用的并行读写的思路,主要是两类:
一个是锁分离
一个是copy on write
不过因为在目前的平衡二叉树实现中基本都需要做旋转操作,无法保证这个旋转的原子性,所以在主流的平衡二叉排序树中没见过能够很好地处理并发的。

6、内存占用
相比较数组而言,链表的内存占用是固定的,每个节点上固定的两个到下层子节点的指针,以及到父节点的一个指针。 其他空间全部可以存放数据,空间消耗上,如果数组上的数据是全满的,那么链表没优势。不过如果要是自增的数组,也即每次都以2倍空间大小做自动扩展,那么链表的内存占用一般是优于自动扩展数组的各类实现的,因为自动扩展数组最坏情况下有一半的空间都是空着的。

参考:
http://blog.sina.com.cn/s/blog_693f08470101mnna.html
http://www.cnblogs.com/huangxincheng/archive/2012/07/22/2603956.html

二叉树

1、 什么是二叉树

在计算机科学中,二叉树(英语:Binary tree)是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点;深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0=n_2+1。

一棵深度为k,且有2^k-1个节点称之为满二叉树;深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树。

与树不同,树的结点个数至少为1,而二叉树的结点个数可以为0;树中结点的最大度数没有限制,而二叉树结点的最大度数为2;树的结点无左、右之分,而二叉树的结点有左、右之分。
—— 引用自维基百科

上面说了一堆东西,很难理解,简单点来说,二叉树主要用来表示树形结构的数据

它的主要应用场景是,实现数据映射,或者实现压缩算法(哈夫曼树)。

它的特性有:

  • 有一个ROOT节点
  • 一个节点有两个子节点
  • 左边的子节点上的数据一定比父节点的小,而右边子节点一定比父节点的数据大

二叉树

一个标准的二叉树就出来了,如上图。
在某些极端情况下,二叉树将会退化成之后右节点,或之有左节点。此时时间复杂度就会从O(log2N)退化成O(N)。如下图。

极端情况下的二叉树

2、二叉树的实现

为了具有通用性,我们定义成泛型模板,在每个结点中增加一个”数据附加域”。

添加节点
根据上述的表述,我们可以很轻松的来写出添加节点的代码。
当第一个数字/对象时,默认为根节点。
当第二个数字/对象时,和地一个数字/对象比较,较大存放在有节点,较小存放于左节点。
当第二个数字/对象时,依次类推….

二叉树添加节点

查找/范围查找

这个才是我们使用二叉树的最终目的,既然是范围查找,我们就知道了一个”min“和”max“,其实实现起来也很简单,

第一步:我们要在树中找到min元素,当然min元素可能不存在,但是我们可以找到min的上界,耗费时间为O(log2n)

第二步:从min开始我们中序遍历寻找max的下界。耗费时间为m。m也就是匹配到的个数。

删除节点
1. 没有子节点
直接删除
2. 单子节点
这个比较简单,如果删除的节点有左子节点那就把左子节点顶上去,如果有右子节点就把右子节点顶上去,然后打完收工。
单子节点删除
3. 双子节点
将右侧最小或者左侧最大节点,移动替换要被删除节点上即可
双子节点删除

以下为全部代码:

参考:
http://www.cnblogs.com/huangxincheng/archive/2012/07/21/2602375.html