红黑树与AVL解决方案

红黑树与AVL
请大家讨论一下：红黑树要比AVL有什么优势，以及各自应用的场合？
高手指教一下吧
[解决办法]
红黑树所有操作都在logn之内

[解决办法]

引用:

不过 AVL树一定是红黑树——将所有点变成黑色

这好像不一定, 例如：
    3
   /  \
  2    4
 /
1
是AVL树,所有点变成黑色就不是RB树了。
[解决办法]
红黑树更实用一点。
[解决办法]

引用:

红黑树更实用一点。

AVL树是纯数学家发明的，用于课堂教学比较实用了。RB树是计算机科学家发明的，工程中比较实用，呵呵
[解决办法]

引用:

引用:

红黑树更实用一点。

知道红黑树在STL和linux内核中使用，但是采用它肯定有优势，优势在哪里呢？

旋转操作非常局部化，而且次数极少（插入最多两次旋转，删除最多三次旋转），而改变颜色的操作不会影响到用户对树的query操作（即不要lock），另外很多树，如AVL树，2-3树,2-4树都可以转化成红黑树，红黑树能达到O(logn)高度，但是不像AVL树那样严格要求左右子树高度差必需相差不超过1。可以说RB树是目前为止高度要求最灵活的准平衡BST。我说准平衡是相对完全二叉树来说的，AVL树(比如Fibonacci树)也不是完美平衡的。

查看更多 下一篇