从二叉搜索树

Question

查找第n个最小元素如何从二叉搜索树找到第n个最小元素

约束是：

1. 时间复杂度必须O(1)
2. 没有多余的空间，应使用

我已经尝试了2种方法。

1. 做序遍历和寻找第n个元素 - 时间复杂度O(n)
2. 维护没有。小元素比当前节点，并找到有m个元素小的元素 - 时间复杂度O(log n)

Answer 1

我能想到的唯一的办法是改变保存在内存中的BST的数据结构。如果实际上将每个节点视为结构本身（value，left_child和right_child）而不是将它们存储在无序数组中，那么应该很简单，可以将它们存储在有序数组中。因此第n个最小的元素将是你数组中的第n个元素。额外的计算将在插入和删除。但是，如果您使用例如C++集（用于插入和删除的log（n）），它仍然会更有效。

它主要取决于你的用例。

如果你不使用数据结构来处理树（基于数组的位置），我认为你不能用比log（n）更好的东西来完成它。