algorithm - 在 O(log n) 中找到第 k 个最小元素

Question

我知道如果平衡，BST 高度是 O(log(n))，这意味着搜索是 O(log(n))，但是将一棵不平衡的树变成平衡的树会增加插入/删除，因为您必须在每次插入/删除后重新平衡它。

是否有另一种方法可以修改 BST，以便我可以在 O(log(n)) 时间内找到第 K 个最小项，而不影响其他函数的运行时间？

Answer 1

but making an unbalanced tree into a balanced one would increase the run-time of inserting / deleting, since you would have to rebalance it after each insertion / deletion.

不对，自平衡二叉树也有O(log n)的插入和删除。基本原因是，虽然您确实需要进行重新平衡，但每次操作重新平衡本身总共需要 O(log n)。

看看AVL trees了解它如何能够在不影响操作复杂性的情况下重新平衡。