为什么二叉搜索树会变得向右不平衡？

Question

这是来自 Heap 讲座幻灯片 8。

添加、查看和删除对我来说很有意义，为什么这些操作是 O(log n) - 遍历 BST 在每次移动后将树切成两半。谁能解释一下最后一句话 "The tree tends to become unbalanced to the right" 背后的直觉？为什么不离开？对我来说，它应该是平衡的，因为平均法则，就像随着时间的推移，小于根的元素频率应该与大于根的元素频率持平。 Law of Averages

Answer 1

别想太多了。这仅仅是因为 remove 操作总是转到最左边的元素并将其删除。经过几个这样的操作之后，无论根节点或其他任何东西，您最终都会得到树 "heavier" 到树的右侧。

即使你有一个非常高价值的根节点倾向于将新添加的元素推到左边，你最终仍然会在左边得到一个子树 "right-heavy"。