BST的第n个最小元素

Question

给出了BST（二叉搜索树）T. 如何找到T的第n个最小元素？

Answer 1

二叉搜索树被有效排序，所以你只需要按顺序遍历树并到达第n个点。如果树是完全平衡的，你可以计算要去的地方。

Answer 2

如果二叉搜索树不完全平衡，那么您需要执行递归搜索以查找第n个最小元素。通过让每个节点存储每个分支指针所指向的子节点的数量，可以大大加速这种情况，从而有效地将搜索转换为二进制指针。但是，这会增加树更新的开销，因为每次插入或删除都需要通过叶到根遍历来更新节点计数。

或者，您可以保持树平衡，并使用上述答案。