红黑树是否必须按顺序排列？

Question

我在这里有一个非常简单的问题:红黑树是否必须按顺序排列？我问这个是因为维基百科页面右侧的小方框(http://en.wikipedia.org/wiki/Red-black_tree)说搜索时间是O(log(n)); 但是,如果树被分类,这不会是真的.另一方面,属性s

Answer 1

红黑树是排序树(整个所有RB树都是排序的二叉树,但不是所有排序的二叉树都是红黑树的东西).普通二叉树和红黑树之间的区别在于RB树保证搜索时间将为log ₂(n),因为它们是平衡的.实质上,它保证n个节点的层数永远不会超过log ₂(n),从而保持二进制搜索.

没有平衡的普通二叉树不会总是产生log ₂(n)时间复杂度.例如,如果我有这样的树:

  4
 / \
3   6
     \
      7
       \
       10
         \
         12

对于这种不平衡树,实际搜索时间几乎是线性的12(最坏情况时间复杂度,5次比较).对于最多具有log ₂(n)层的平衡树,上面的树可以是:

     7
   /   \
  4    10
 / \     \
3   6    12

因此,找到任何最低层节点最多需要进行3次比较(这符合log ₂(n),因为它实际上是向上舍入的,ceil [log ₂(6)] = 3)

这里的关键是要记住,层数在功能上等同于从根开始时必须进行的比较次数.红黑树通过平衡将层数限制到最低限度,而香草,非平衡二叉树则不会.