算法导论(五)——树
算法导论(五)——树
【主要参考资料:MIT算法导论视频,《数据结构,算法与应用,c++语言描述》】
完全二叉树:
只有最下面两层度小于2,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
已知节点总数为n,则叶子结点数n0=(n+1)/2 。
假设元素编号i[1,n],若i==1,则为根元素,i>1则父节点的编号为i/2;若2i>n,则该元素无左孩子,否则其左孩子的编号为2i; 若2i+1>n,则该元素无右孩子,否则其右孩子的编号为2i+1。
满二叉树:
高度为h,恰好有2^h-1个元素。它是完全二叉树的特例。一棵具有n个结点的深度为k的二叉树,它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应。
动态查找树
主要有: 二叉查找树(BST),平衡二叉查找树(AVL),红黑树(RBT),B~/B+树(B-tree)。
优势:
①都是动态结构。在删除,插入操作的时候,都不需要彻底重建原始的索引树。最多就是执行一定量的旋转,变色操作来有限的改变树的形态,代价较小。②查找的时间复杂度大体维持在O(log(N))数量级上(除BST最坏情况O(N))。
(1) 排序(查找)二叉树
二分查找效率为Θ(lgn),但不适于动态的插入和删除;散列表查找效率可以到达Θ(1),但不能进行“范围查找。二叉树可以实现。操作的效率与二叉树的高度成正比,期望效率为Θ(lgn)。最坏情况下为Θ(n),解决方法是"旋转"使"平衡。
【效率:查找最好时间复杂度O(logN),最坏时间复杂度O(N)。插入删除操作算法简单,时间复杂度与查找差不多】
m叉搜索树:
(2)平衡二叉树
为了防止上述的顺序查找,考虑如何最大限度的减小树的深度。
除了具备二叉查找树的基本特征之外,它或者是一棵空树,或者是: 左右子树都平衡,且高度之差绝对值不超过1。在最坏情况下的高度为O(lgn)的树。
常用算法有:红黑树、AVL树、Treap等。
红黑树、AVL树:适合内部存储的应用;对于n>=0,都存在一颗AVL树。
【AVL效率:查找维持在O(logN),不会出现最差情况。AVL树在执行每个插入操作时最多需要1次旋转,其时间复杂度在O(logN)左右。AVL树执行每个删除操作的时间复杂度需要O(2logN)】
【RBT效率:查找最好情况下O(logN),但在最坏情况下比AVL要差一些,但也远远好于BST。插入和删除操作改变树的平衡性的概率要远远小于AVL(平衡度AVL > RBT)。因此需要的旋转操作的可能性要小,而且一旦需要旋转,插入一个结点最多只需要旋转2次,删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN),但是实际上,这种操作由于简单所需要的代价很小】
(3) B-树(平衡多路查找树)
【通过减少树高来降低二叉查找树的查找代价】【海量存储时,提高磁盘的存储效率】
适合索引方法的数据结构,也是一种平衡树,度大于2,适合化外部存储的应用(如存储在磁盘上的大型词典)。随机访问元素时,先搜索磁盘索引(每个磁盘的最大关键字),确定所属的磁盘,然后从中取出块索引(该磁盘每个块中的最大关键字),确定所属的块,再从块中搜索,确定该元素。
a .查找: 将结点中的有序关键字序列放入内存,进行优化查找(可以用折半). B+树作为B树的变种,其查找效率更高。
b.插入: B-Tree的插入会发生结点的分裂操作。当插入操作引起了s个节点的分裂时,磁盘访问的次数为h(读取搜索路径上的节点)+2s(回写两个分裂出的新节点)+1(回写新的根节点或插入后没有导致分裂的节点)。因此,所需要的磁盘访问次数是h+2s+1,最多可达到3h+1。代价是很大的。
c. 删除代价:B-Tree的删除会发生结点合并操作。最坏情况下磁盘访问次数是3h=(找到包含被删除元素需要h次读访问)+(获取第2至h层的最相邻兄弟需要h-1次读访问)+(在第3至h层的合并需要h-2次写访问)+(对修改过的根节点和第2层的两个节点进行3次写访问)
【B-Tree效率: 由于考虑磁盘储存结构,B树的查找、删除、插入的代价都远远要小于任何二叉结构树(读写磁盘次数的降低)】
B+树:是应文件系统所需而产生的一种B~树的变形树。
i.一棵m阶的B+树和m阶的B-树的差异在于:
1) 有n棵子树的结点中含有n个关键字; (B~树是n棵子树有n+1个关键字)
2) B+树的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。 (B~树的叶子节点并没有包括全部需要查找的信息) ,B+树的非终节点只是作为叶子结点中最大(最小)关键字的索引,没有文件内容所在物理存储的地址(而B~树所有结点均有文件内容所在的磁盘物理地址)。
3) 所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。 (B~树的非终节点也包含需要查找的有效信息)
ii.B+树的查找与B~树类似。但通常B+树有两个头指针,一个指向根结点。另一个指向关键字最小的叶子节点。此外,所有叶子结点也按照大小顺序链接。因此,B+树有两种查找算法:一种从根结点出发,一种从叶子结点出发的顺序查找。B+树与B~树在插入删除操作中的效率是差不多的。
iii.B+树比B~树更适合实际应用中操作系统的文件索引和数据库索引
1、 B+树的磁盘读写代价更低(内部结点相对更小)
2、 B+树的查询效率更加稳定(非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当)
分裂树:分裂节点是在字典操作中所检察的最深层的节点。
二叉搜索(查找)树BST:
操作:基本查询,查询最小、最大关键值、前驱、后继,单个节点的插入和删除操作。
动态集合的操作平均时间为Θ(lgn)【期望效率】。同样一组数据集合,不同的添加顺序会导致查找树的结构完全不一样,直接影响了查找效率。
根节点有关键字,其左子树的关键字都小于它,右子树的关键字都大于它。
代码参考http://www.cnblogs.com/zhoutaotao/p/4096237.html
二叉搜索树VS快排,make same comparision,butin a different order.
索引二叉搜索树;节点的数值域为三元:leftSize,key,value。假设此树高为h,则查找,插入,删除的时间均为O(h)
应用:1. 直方图,统计文本中的单词频率(构造元素the pair,一个成员是关键字,另一个是对应的频率,不断插入,若有匹配则频率增1);
2. 箱子装载问题(关键字表示箱子的剩余容量(可重复),即查找>=x的最小关键字,删除已经匹配的箱子,重新计算它的剩余容量再插入;若查找失败则启用新箱子)
二叉平衡树AVL
描述;链表。(每个节点增加一个平衡因子,-1/0/1,hL-hR)
查找(同二叉查找树)
1. 插入
保持平衡的基本思想:插入节点时,首先检查是否因插入而破坏了平衡,若破坏,则找出其中的最小不平衡二叉树(离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树),在保持二叉排序树特性的情况下,调整最小不平衡子树中节点之间的关系,以达到新的平衡。
旋转类型及代码参考:http://blog.****.net/caisini_vc/article/details/5674764
AvlNode<T>添加成员平衡因子bFactor
①当树中节点X的右孩子的右孩子上插入新元素,且平衡因子从-1变成-2后,就需要绕节点X进行左旋转
②当树中节点X的左孩子的左孩子上插入新元素,且平衡因子从1变成2后,就需要绕节点X进行右旋转。
③当树中节点X的左孩子的右孩子上插入新元素,且平衡因子从1变成2后,就需要 先绕X的左子节点Y左旋转,接着再绕X右旋转
④当树中节点X的右孩子的左孩子上插入新元素,且平衡因子从-1变成-2后,就需要 先绕X的右子节点Y右旋转,接着再绕X左旋转
2. 删除
找到要删除的元素,选择替换的元素。
http://www.cnblogs.com/QG-whz/p/5167238.html
AvlNode<T>添加成员高度hight
【删除右子树的节点导致AVL树失衡时,相当于在左子树插入节点导致AVL树失衡】
3. 性能分析
优势:不会出现普通二叉查找树的最差情况。其查找的时间复杂度为O(logN)。
缺陷: (1)为了保证高度平衡,动态插入和删除的代价也随之增加。——》红黑树
(2) 所有二叉查找树结构的查找代价都与树高紧密相关——》减少树高,多路查找树
(3) 在大数据量查找环境下(比如说系统磁盘里的文件目录,数据库中的记录查询等),平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁,进而导致效率低下。——》多路查找树/B-树/B+树
红黑树RBT:
它是是一种自平衡二叉查找树,确保拥有对数阶高度。能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。同样多内部节点时,最坏情况下,红黑树的高度大于AVL树的高度。
它是在计算机科学中用到的一种数据结构,主要存储有序的数据,典型的用途是实现关联数组。例如,Java集合中的TreeSet和TreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。
特性; 1.节点为红色/黑色 2.根节点,叶节点为黑色 3.每个红节点的父节点为黑色 4.从某个节点出发到叶子结点的所有路径,均拥有相同的黑节点数。
相关定理
1. 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
2. 红黑树的树高(h)不大于两倍的红黑树的黑深度(bd),即h<=2bd
3. 一棵拥有n个内部结点(不包括叶子结点)的红黑树的树高h<=2log(n+1)
操作
插入和删除操作,恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂,但操作时间仍可以保持为 O(log n) 次
1. 查找(同二叉查找树)。
2. 插入(假设新加入的结点为N,父亲结点为P,叔父结点为Ui,祖父结点G)
将红黑树当做一颗二叉查找,将节点插入;将插入的节点着色为“红色”;通过一系列的旋转或着色等操作,使之重新成为一颗红黑树。
分5种情况讨论,http://hxraid.iteye.com/blog/611816核心思想都是将红色的节点移到根节点;然后将根节点设为黑色。
3. 删除(假设要删除的点为 N,它的父亲为P,它的兄弟为S,SL为S的左儿子,SR为右儿子)
将红黑树当作一颗二叉查找树,将节点删除;通过“选转和重新着色”等一系列来修正该树,使之重新成为一颗红黑树。首先用child替换
分6种情况讨论,http://hxraid.iteye.com/blog/611816
1. 按关键字查找,插入和删除,优先选择散列技术。
2. 按关键字实施字典操作,且操作时间不能超过指定范围,选用平衡搜索树。
按名次实施的查找和删除,不按精确的关键字匹配进行的字典操作(寻找关键字大于k的最小元素),选用平衡搜索树。
3. AVL树和红黑树是常用的平衡二叉树,都采用“旋转”保持平衡,他们的实际运行时间性能类似,分裂树对任意的字典操作序列更快速,实现更简单。
4. STL类的map和multimap都用了红黑树结构,保证查找,插入和删除都有对数级的操作时间。
5. 对存储在磁盘上的大型字典,需要用B-树。
参考:
http://blog.****.net/crystal_avast/article/details/7700386
http://www.cnblogs.com/zhoutaotao/p/4096237.html
http://blog.****.net/caisini_vc/article/details/5674764
http://blog.****.net/sunjerdege/article/details/6861698
http://www.cnblogs.com/QG-whz/p/5167238.html
http://www.cnblogs.com/skywang12345/p/3624291.html