分类目录归档:算法

平衡二叉树 —— 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

有序数组

一、 概念

有序数组中也分有普通有序数组和循环有序数组。

普通有序数组是一种特殊的数组,里面的元素,按一定的顺序排列,我们这里假设由小到大排列。

循环有序数组指的是,将一个有序数组循环左/右移动若干距离之后变成的数组。如,[1,2,3,4,5]循环右移3位,就成为[4,5,1,2,3]。该数组的特点是,其中包含着一个转折点。转折点左右两侧的子数组都是有序的,并且左侧的子数组整体都比右侧的子数组大。

二、 二分查找

有一个古老的印度故事,国王要给大臣赢棋的奖赏,大臣希望能够“请在第一个格子里放一颗麦粒,第二个格子里放2颗,第三个格子里放4个,第四个格子里放8粒……依此类推,把64 个格子都放满。” 总共能有多少,结论是一千八百四十四吉六千七百四十四兆零七百三十七亿零九百五十五万一千六百一十五。

也就是说二分查找能够在64次运算后处理这样多的记录,结果还是很惊人的,这也就是O(log2N) 时间复杂度的由来,二分查找,2次可以从4条记录中找到对应记录,3次8条,4次16条。。依次类推。

使用二分查找的前提条件是:

  1. 数据能够按照某种条件进行排序
  2. 可以通过某种方式,取出该数据集中任意子集的中间值。
普通有序数组二分查找

循环有序数组二分查找

循环有序数组的二分查找,需要多一个步骤,就是查询到转折点。
但是,不要想着直接定位到转折点。

只需要知道转折点在中间点的哪一侧就行。因为不含转折点的一侧一定是单调递增的,依然能够帮助我判断出key在mid的哪一侧。

根据left和right下标,求得mid下标。

  • 如果A[left]<=A[mid],那么A[mid]一定不在转折点左侧,意味着从left到mid的整个左半部分都是严格递增的,因此我能够判断key是否在左半部分里。
  • 如果A[left]>A[mid],那么A[mid]一点在转折点左侧,意味着从mid到right的整个右半部分是严格递增的,因此我能够判断key是否在右半部分里。

三、 扩展

  1. 是否支持范围查找
    基本上来说,这个问题主要取决于两个方面,一个是数据是否有序,另外一个是该存储结构是否提供了快速读取下一个记录的方法。
    对于数组来说,所有数据都是有序的,并且只需要简单地做下标=下标+1的操作,就可以以程序提供的最快方法。因此,范围查找肯定是可以支持的。而且效率应该是很高的.

  2. 集合是否能够随着数据的增长而自动扩展
    现代语言中,一般都会提供一个支持自由扩展的数组。
    然而,虽然能够做到自动的扩展了,但是,要知道,要能够保持映射可以快速的查询,那么必须还要保证新写入的数据的有序性,这就很麻烦了。。因为你无法知道数据写入的顺序,那么如何处理中间值插入就是个很麻烦的问题了。
    比如,如果我的写入顺序是1,3,4,2,5 这个顺序,并且在开始的时候没有办法知道写入的顺序,那么我们唯一能做的事情就是,按照顺序,写1,然后在1的右临位,写3,然后再在右临位写4,这时候来个2,麻烦来了,我应该怎么做呢?
    在数组内,一种最容易想到的方式就是,找到1这个位置,然后将1右边的数据全部往右移动一个位置,然后将2填写进去。
    哈,你也看到了,这种方式会随着我们数据量的变大,而代价变得非常巨大,比如如果有100万行记录,那么就意味着最坏情况下,需要每次写入都移动100万行记录。。。这代价可是真大。
    因此,这也就是我们使用数组的时候的一个最大的问题了,单独的使用数组,是不支持更新的,而使用简单的策略比如自动扩增的数组,也无法支持有序数据的自增的。

  3. 读写性能如何
    对于读取,如果要快速查找数据,需要使用二分查找来找到一个数据,而二分查找的时间复杂度大概是O(log2N).
    对于写入,数组支持的代价很高,因此基本没人会想要用大数组来做需要频繁增加和删除对应关系的映射的实现的吧
  4. 是否面向磁盘结构
    大部分情况下,纯粹的数组并不是一个面向磁盘的结构。
    磁盘的特性是,一次读取一批数据,或一次写入一批数据时效率会高。
    顺序读大批数据,或者顺序写大批数据的时候,效率会变高。
    而如果要进行二分查找,如果能够一次从磁盘中取出整个数组再进行二分查找,则查找效率会变高,若不得不直接依托磁盘进行二分查找,则读取效率会很低,每次折半,都需要从磁盘中的一个随机位置取出一个block,并从中取出一条记录,随机读取的次数= log2N的结果,而每一次的随机读,对磁盘来说都是灾难。
    不过,在未来,我们会看到一些依托于数组的数据结构,部分的解决了这个问题:)
  5. 并行指标
    只要是不支持修改的数据模型,一般来说并行读取效率都可以做到很高,因为。。完全不会变就不需要加锁啊- -,因此是可以完全并行的
  6. 内存占用
    数组的内存占用应该是个标杆,如果再能比数组更节省空间,那就需要做大量hack和压缩了。

参考:
http://blog.csdn.net/ojshilu/article/details/17485787
http://blog.sina.com.cn/s/blog_693f08470101mi2o.html