我知道如果平衡，BST 高度是 O(log(n))，意味着搜索是 O(log(n))，但是将不平衡树变成平衡树会增加插入/删除的运行时间，因为您必须在每次插入/删除后重新平衡它。
是否有另一种方法来修改 BST，以便我可以在 O(log(n)) 时间内找到第 K 个最小的项目，而不会影响其他函数的运行时间？
问问题
1847 次
1 回答
2
但是将不平衡的树变成平衡的树会增加插入/删除的运行时间，因为您必须在每次插入/删除后重新平衡它。
不正确，自平衡二叉树也有O(log n)插入和删除。基本原因是，虽然您确实需要进行重新平衡，但重新平衡本身将需要O(log n)每次操作的总和。
查看AVL 树，了解它如何在不影响操作复杂性的情况下进行重新平衡。
于 2013-10-10T20:29:09.393 回答