昨晚看到map 和 hash_map 对其中的红黑树概念模糊了。于是晚上翻了下书,以此为记。

1.平衡二叉树: 当且仅当两个子树的高度差不超过1时,这个树是平衡二叉树。(同时是排序二叉树)

 平衡二叉树,又称AVL树。它或者是一棵空树,或者是具有下列性质的二叉树:

它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差之差的绝对值不超过1.

常用算法有:红黑树、AVL树、Treap等。

  平衡二叉树的调整方法

  平衡二叉树是在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入新结点而破坏了二叉排序树的平衡性,
若是,则找出其中的最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的
旋转,使之成为新的平衡子树。具体步骤如下:

  ⑴ 每当插入一个新结点,从该结点开始向上计算各结点的平衡因子,即计算该结点的祖先结点的平衡因子,
 若该结点的祖先结点的平衡因子的绝对值均不超过1,则平衡二叉树没有失去平衡,继续插入结点;
 
  ⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1,则找出其中最小不平衡子树的根结点;

  ⑶ 判断新插入的结点与最小不平衡子树的根结点的关系,确定是哪种类型的调整;

  ⑷ 如果是LL型或RR型,只需应用扁担原理旋转一次,在旋转过程中,如果出现冲突,应用旋转优先原则调整冲突;如果是LR型或LR型,
 则需应用扁担原理旋转两次,第一次最小不平衡子树的根结点先不动,调整插入结点所在子树,第二次再调整最小不平衡子树,在旋
 转过程中,如果出现冲突,应用旋转优先原则调整冲突;
 
  ⑸ 计算调整后的平衡二叉树中各结点的平衡因子,检验是否因为旋转而破坏其他结点的平衡因子,
 以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。
 
 
2.完全二叉树(Complete Binary Tree)

  若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层从右向左连续缺若干结点,这就是完全二叉树。


3.满二叉树(Full Binary Tree)

  一棵深度为h且有 2^h-1个结点的二叉树。

4.红黑树

红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。

 它是在1972年由Rudolf Bayer发明的,他称之为"对称二叉B树",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇
 论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的:
 
 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。
 
 红黑树是一种很有意思的平衡检索树。

 它的统计性能要好于平衡二叉树(有些书籍根据作者姓名,Adelson-Velskii和Landis,将其称为AVL-树),
 
 因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,
 
 这些修改提供了更好的性能,以及对set操作的支持)。

 红黑树是每个节点都有颜色特性的二叉查找树,颜色的值是红色或黑色之一。除了二叉查找树带有的一般要求,
 我们对任何有效的红黑树加以如下增补要求:
 
  1.节点是红色或黑色。

  2.根是黑色。

  3.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

  4.从每个叶子到根的所有路径都包含相同数目的黑色节点。

  这些约束强制了红黑树的关键属性:

 从根到叶子的最长的可能路径不大于最短的可能路径的两倍长。
 
 结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值都要求与树的高度成比例的最坏情况时间,
 
 这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。
 
 在很多树数据结构的表示中,一个节点有可能只有一个儿子,而叶子节点包含数据。

 用这种范例表示红黑树是可能的,但是这会改变一些属性并使算法复杂。为此,本文中我们使用 "null 叶子"
 
 或"空(null)叶子",如上图所示,它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略,
 
 导致了这些树好像同上述原则相矛盾,而实际上不是这样。与此有关的结论是所有节点都有两个儿子,尽管其中的一个或两个可能是空叶子。

posted on 2008-11-18 11:00 -274°C 阅读(2606) 评论(1)  编辑  收藏 所属分类: 计算机综合


FeedBack:
# re: 数据结构中常用树之概念
2013-10-24 19:17 | ipo
uoi  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航:
 

常用链接

留言簿(21)

随笔分类(265)

随笔档案(242)

相册

JAVA网站

关注的Blog

搜索

  •  

积分与排名

  • 积分 - 872787
  • 排名 - 37

最新评论