注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

极夜.潜的博客

 
 
 

日志

 
 

树的结构:满二叉树 完全二叉树 二叉查找树 平衡二叉树 AVL树 红黑树 伸展树 SBT Fibonacci树 B树 kd树  

2011-06-10 12:40:48|  分类: Algorithm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

满二叉树
  树的结构:满二叉树 完全二叉树 二叉查找树  平衡二叉树 AVL树 红黑树 伸展树 SBT Fibonacci树 B树 kd树 - 极夜.潜 - 极夜.潜的博客 

满二叉树是每一层上的所有结点数都达到最大值的二叉树。深度为m的满二叉树有2^m-1个结点。

完全二叉树
  树的结构:满二叉树 完全二叉树 二叉查找树  平衡二叉树 AVL树 红黑树 伸展树 SBT Fibonacci树 B树 kd树 - 极夜.潜 - 极夜.潜的博客

完全二叉树除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。完全二叉树来说的叶子结点只可能在层次最大的两层上出现,对于任何一个结点,若其右分支下的子孙结点的最大层次为p,则其左分支下的子孙结点的最大层次为p或p+1。满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树。

完全二叉树也称为近似满二叉树

二叉查找树
  树的结构:满二叉树 完全二叉树 二叉查找树  平衡二叉树 AVL树 红黑树 伸展树 SBT Fibonacci树 B树 kd树 - 极夜.潜 - 极夜.潜的博客  树的结构:满二叉树 完全二叉树 二叉查找树  平衡二叉树 AVL树 红黑树 伸展树 SBT Fibonacci树 B树 kd树 - 极夜.潜 - 极夜.潜的博客

二叉查找树或者是一棵空树,或者是具有下列性质的二叉树:
(1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)它的左、右子树也分别为二叉查找树。

二叉查找树也称为二叉排序树、二叉搜索树

平衡二叉树
  树的结构:满二叉树 完全二叉树 二叉查找树  平衡二叉树 AVL树 红黑树 伸展树 SBT Fibonacci树 B树 kd树 - 极夜.潜 - 极夜.潜的博客

平衡二叉树或者是一棵空树,或者树的左子树和右子树的深度之差不超过1且左右子树皆为平衡二叉树时。

AVL树

自平衡二叉查找树是当二叉查找树插入或删除任意结点时,二叉查找树是一颗平衡二叉树。AVL树是最先发明的自平衡二叉查找树,AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis。

红黑树

红黑树是一种自平衡二叉查找树。它是在1972年由鲁道夫·贝尔发明的,他称之为"对称二叉B树",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。

伸展树

伸展树(Splay Tree)是一种二叉排序树。为使查找时间更少,被查频率高的那些条目就应当经常处于靠近树根的位置。伸展树是一种自调整形式的二叉查找树, 在每次查找之后对树进行重构,沿着某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。

相比于红黑树,AVL树等,伸展树的空间要求与编程复杂度要小得多。

SBT(Size Balanced Tree,节点大小平衡树)

  树的结构:满二叉树 完全二叉树 二叉查找树  平衡二叉树 AVL树 红黑树 伸展树 SBT Fibonacci树 B树 kd树 - 极夜.潜 - 极夜.潜的博客

节点大小平衡树是一种自平衡二叉查找树。对于每一个结点t,我们使用left[t]和right[t]来储存它两个儿子的指针,s[t]表示以t为根的子树的大小(Size),维持它成为这棵树上结点的个数。每一个在SBT中的结点t,保证:
(1)s[right[t]] >= s[left[left[t]]], s[right[t]] >= s[right[left[t]]];
(2)s[left[t]] >= s[right[right[t]]], s[left[t]] >= s[left[right[t]]]。

在上图例中:s[A] <= s[R],s[B] <= s[R],s[C] <= s[L],s[D] <= s[L]。

广东纪念中学的陈启峰于2006年底完成论文《Size Balanced Tree》,并在2007年的全国青少年信息学奥林匹克竞赛冬令营中发表。它常被中国的信息学竞赛选手和ACM/ICPC选手们戏称为“傻B树”、“Super BT”等。相比红黑树、AVL树等自平衡二叉查找树,SBT更易于实现。

线段树(Segment Tree)

线段树是一种二叉搜索树,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a, (a+b)/2],右儿子表示的区间为[(a+b)/2, b]。线段树是满二叉树。线段树类似于区间树(Interval Tree)。

Fibonacci树

  树的结构:满二叉树 完全二叉树 二叉查找树  平衡二叉树 AVL树 红黑树 伸展树 SBT Fibonacci树 B树 kd树 - 极夜.潜 - 极夜.潜的博客

n阶Fibonacci树的每个节点的左子树和右子树分别为n-2和n-1阶的Fibonacci树,0阶Fibonacci树为空。

一种Fibonacci树的构造方法:

procedure FibonacciTree(d:integer; Var T:binarytree){//d是 Fibonacci树的深度 if  d=0  then  T := nil else{  new(T);  if  d=1  then  { T^.leftptr:=nil; T^.rightptr:=nil }  else{// d>=2   FibonacciTree(d – 2, T^.leftptr);   FibonacciTree(d – 1, T^.rightptr);  } }}

当d=4时,如上图所示。

B树
  树的结构:满二叉树 完全二叉树 二叉查找树  平衡二叉树 AVL树 红黑树 伸展树 SBT Fibonacci树 B树 kd树 - 极夜.潜 - 极夜.潜的博客

B树是一种适用于外查找的平衡多叉树,一棵m阶的B树满足下列条件:
(1)树中每个结点至多有m个孩子;
(2)除根结点和叶子结点外,其它每个结点至少有m/2个孩子;
(3)若根结点不是叶子结点,则至少有2个孩子;
(4)所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息;
(5)有k个孩子的非终端结点恰好包含有k-1个关键字。
在B树中,每个结点中关键字从小到大排列,并且当该结点的孩子是非叶子结点时,该k-1个关键字正好是k个孩子包含的关键字的值域的分划。阶数为4的B树称为2-3-4树。B树的变种有B+树B*树等。

Dancing Tree

Dacing tree类似B+树,由Hans Reiser发明并用于Reiser4文件系统。与自平衡二叉搜索树时刻均保持平衡不同,dancing tree只在数据写入磁盘时使树的结点保持平衡。

kd树(k-dimensional tree)

  树的结构:满二叉树 完全二叉树 二叉查找树  平衡二叉树 AVL树 红黑树 伸展树 SBT Fibonacci树 B树 kd树 - 极夜.潜 - 极夜.潜的博客

kd树就是每个节点有k个域的二叉树。以2d树为例说明kd树的构造方法。2d树的每个节点有2个域:(X, Y),当插入一个节点时,在奇数层比X的大小,偶数层比Y的大小,大的节点到右树中,否则在左树中。

如上图例:
(1)有二维数组(5, 4),(10, 8),(7, 9),(20, 9),以(7, 9)为根;
(2)取(5, 4),因为第一层是根(7, 9),而且7大于5,所以(5, 4)是它的左孩子;
(3)取(10, 8),因为第一层是根(7, 9),而且7小于10,所以(10, 8)是它的右孩子;
(4)取(20, 9),因为20大于第一层根(7, 9)中的7,继续向右分枝查找,到第2层,9大于(10, 8)中的8,所以(20, 9)是(10, 8)的右孩子。

Treap

Treap,是有一个随机附加域满足堆的性质的二叉搜索树,其结构相当于以随机数据插入的二叉搜索树。相对于其他的平衡二叉搜索树,Treap的特点是实现简单,且能基本实现随机平衡的结构。

随机二叉树

 

  评论这张
 
阅读(1019)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018