algorithm - 为什么我们要努力保持树木平衡

Question

我看到很多问题都在谈论平衡树。

例如，R-Tree 优于 KD-Tree，因为它们是平衡的。

与非平衡树相比，使用平衡树有什么优势？

Answer 1

搜索这棵树

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

将花费 Θ(N) 时间。搜索这棵树

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

将花费 Θ(logN) 时间。由于搜索时间与树的高度成正比。