红黑树必须按排序顺序吗？

Question

我在这里有一个非常简单的问题：红黑树必须按排序顺序吗？我问这是因为维基百科页面右侧的小方块（http://en.wikipedia.org/wiki/Red-black_tree）表示搜索时间是O（log（n））;然而，如果树被排序，这只会是真的。另一方面，虽然属性s

Answer 1

红黑树是排序树（整个所有RB树都是排序的二叉树，但并非所有排序后的二叉树都是红黑树的东西）。普通二叉树和红黑树之间的区别在于RB树保证搜索时间将是日志（n），因为它们是平衡的。实质上，它保证节点的层数永远不会超过log （n），保持二进制搜索。

没有平衡的纯二叉树不会总是产生时间复杂度。举例来说，如果我有这样的树：

4 
/\ 
3 6 
    \ 
     7 
     \ 
     10 
     \ 
     12 

对于这种不平衡的树，实际的搜索时间几乎是线性的找到12（最坏情况下的时间复杂度，5个比较）。对于具有一个平衡树至多日志（n）的层，上面的树可以是：

 7 
/ \ 
    4 10 
/\  \ 
3 6 12 

所以找到任何最低层节点将至多3个比较（其适合日志（n）的因为它实际上是向上舍入，小区[日志（6）] = 3）

这里的关键是要记住，层的数量在功能上等价到你在根目录开始时必须进行的比较次数。红黑树通过平衡将层数限制为最小值，而香草，不平衡二叉树不会。

Answer 2

红黑树的搜索时间为O（log n），因为它以自然顺序设置它们的节点。

当你做一个节点比较时，理论上你在分支上放弃了一半的选项。

既然你只能“半” log n times你到一个元素之前，那么您的搜索复杂度是O(log n)

Answer 3

红黑树是二叉搜索树。根据二叉搜索树的定义，左侧子元素（以及所有后代）必须小于父代，右侧子代（以及所有后代）必须大于父代。因此有一个命令。

Answer 4

红黑树的全部要点是保持树在某种程度上的平衡。如果你放松排序约束，那么保持树平衡是微不足道的，因为你可以把节点放在任何你想要的地方。