我们为什么要保持树木平衡

Question

我看到很多关于平衡树的问题.

例如,R-Tree比KD-Tree更好,因为它们是平衡的.

在非平衡树上使用平衡树有什么好处？

Answer 1

正在搜索这棵树

O
 \
  O
   \
    O
     \
      O
       \
        O
         \
          O
           \
            O

将采取Θ(N)时间.正在搜索这棵树

     O
   /   \
  O     O
 / \   / \
O   O O   O

将采取Θ(logN)时间.由于搜索时间与树的高度成正比.