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

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)。