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

Question

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

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

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

Answer 1

正在搜索此树

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

将花费Θ(N)时间。正在搜索此树

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

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

Answer 2

它确保了平均搜索的最小跨度。

如果您的树不平衡，某些搜索将比其他搜索花费更长的时间。在最坏的情况下，O(n)。