C++博客 联系 聚合 管理  

Blog Stats

随笔档案

glacjay

  最近在读候捷的书《STL源码剖析》,且刚好要做一些相关的作业,产生了一些疑问,但,嗯~~~,第一个已经忘了,不好意思。
  就说能记起的那个吧,为什么在STL中的map, set之类容器的底层实现要用RB-TREE,而不是(嗯,就我看来)平衡性要稍强,而实现也较易的AVL-TREE呢。我能想到的原因就是附加的标记的原因吧。因为要实现RB-TREE,只要多加一个颜色属性(BOOL型)即可,而AVL-TREE却需要一个HEIGHT属性,可能会产生问题。但在我看来,这个属性也可以用UNSIGNED CHAR来实现,其容量也可达到2的250次方,应该也不成问题的啊。而UNSIGNED CHAR和BOOL所占空间又一样,在我看来应该没什么问题的,不知道大家有没有什么更好的看法。

posted on 2005-11-22 13:38 Jay True 阅读(328) 评论(2)  编辑 收藏 引用

评论

# re: 关于STL的一些小疑问 2005-12-03 01:04 glacjay
好吧,我终于又看多了一些关于RB—TREE的分析(还没全懂),所以又多知道了一点,就是RB—TREE的实现不需要用递归,而AVL-TREE的实现一般用递归较好,啊对?  回复  更多评论
  

# re: 关于STL的一些小疑问 2006-03-15 00:58 sailor
AVL 不用递归也可以.AVL只用一个char 表示负载因子也可以.

但是AVL对于删除等操作的处理比较耗时间.而这方面RB Tree 表现要好过 AVL.所以大部分实际运用RB Tree好过AVL  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理