各种树结构

满二叉树

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

完全二叉树

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

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

二叉查找树

  二叉查找树或者是一棵空树,或者是具有下列性质的二叉树:

  (1)若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

  (2)若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

  (3)它的左、右子树也分别为二叉查找树。

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

平衡二叉树

  平衡二叉树或者是一棵空树,或者树的左子树和右子树的深度之差不超过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,节点大小平衡树)

  节点大小平衡树是一种自平衡二叉查找树。对于每一个结点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树

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

  一种Fibonacci树的构造方法:















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

B树

  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)

  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的特点是实现简单,且能基本实现随机平衡的结构。

发表评论

电子邮件地址不会被公开。 必填项已用*标注