从 BST 获取最大值和最小值（C++ vs Java）

Question

我知道给定一个平衡的二叉搜索树，得到最小和最大元素需要O(logN)，我想问一下它们分别在C++和Java中的实现。

C++

以std::set为例，调用*set.begin() / *set.rbegin()即可得到min/max，而且是常数时间

Java

以HashSet为例，调用HashSet.first()和HashSet.last()可以得到min/max，但是是对数时间

我想知道这是否是因为 std::set 做了一些额外的技巧来始终更新 beigin() 和 rbegin() 指针，如果是这样，谁能告诉我那个代码？顺便说一句，为什么 Java 没有添加这个技巧，对我来说似乎很方便......

编辑：

我的问题可能不是很清楚，我想看看 std::set 是如何实现 insert/erase 的，我很好奇 begin() 和 rbegin() 迭代器是如何实现的在这些操作期间更新..

编辑 2：

我现在很迷茫。假设我有以下代码：

set<int> s;

s.insert(5);
s.insert(3);
s.insert(7);
... // say I inserted a total of n elements.
s.insert(0);
s.insert(9999);

cout<<*s.begin()<<endl;  //0
cout<<*s.rbegin()<<endl; //9999

*s.begin() 和 *s.rbegin() 不都是 O(1) 操作吗？你说他们不是？ s.rbegin() 实际上迭代到最后一个元素？

Answer 1

begin() 和 rbegin() 只有 return 迭代器，在常数时间内。迭代它们不是恒定时间。

没有'begin()/rbegin()指针'。最小值和最大值是通过迭代到最左边或最右边的元素来达到的，就像在 Java 中一样，只有 Java 没有显式迭代器。

Answer 2

我的回答不是特定于语言的。要在 BST 中获取 MIN 或 MAX，您需要始终分别迭代到最左边或最右边的节点。这个操作在O(height)，大概是O(log n)。

现在，为了优化这个检索，实现Tree的class总是可以存储两个额外的指向最左边和最右边节点的指针，然后检索它们变成O(1)。当然，这些指针带来了在树中每次插入操作时更新它们的开销。

从 BST 获取最大值和最小值（C++ vs Java）

Getting max and min from BST (C++ vs Java)

c++

java

binary-search-tree

data-structures