Minimum/maximum个元素在O(1)时间的平衡二分查找时间
Minimum/maximum element in a balanced binary search time in O(1) time
我知道我们可以在 O(logn) 时间内在二叉搜索树中找到 minimum/maximum。但是 c++ 中的 map 在常数时间内给了我们 minimum/maximum 。我们可以使用 map::begin and maximum using map::rbegin 在地图中找到最小元素。这两个操作都需要恒定的时间。任何人都可以建议一种方法来找到 minimum/maximum O(1) 吗？
BST 未实现 C++ 映射。它由红黑树实现。如果你想通过 O(1) 在 BST 中找到 min/max ，你可以将两个指针存储到树中的最左节点和最右节点。
否则，您可以使用 minheap 或 maxheap 在 O(1) 中找出 min/max。
我知道我们可以在 O(logn) 时间内在二叉搜索树中找到 minimum/maximum。但是 c++ 中的 map 在常数时间内给了我们 minimum/maximum 。我们可以使用 map::begin and maximum using map::rbegin 在地图中找到最小元素。这两个操作都需要恒定的时间。任何人都可以建议一种方法来找到 minimum/maximum O(1) 吗？
BST 未实现 C++ 映射。它由红黑树实现。如果你想通过 O(1) 在 BST 中找到 min/max ，你可以将两个指针存储到树中的最左节点和最右节点。 否则，您可以使用 minheap 或 maxheap 在 O(1) 中找出 min/max。