我的要求是能够快速检索树中的最小值和最大值。 (注意,不是最小/最大 key ,而是卫星数据的最小/最大)。
树将基于字符串作为键,每个节点将存储一个整数。这个整数必然会改变并不断更新。键保持固定
我正在考虑使用 here 中描述的方法扩充红黑树的方法,以便每个节点存储与最小值相似的最大值(左侧最大值和右侧最大值的最大值及其自身)。
因此,当我更新一个节点时,我会简单地更新遍历到达我当前节点的每个节点的最小值/最大值。
避免重写红/黑树的 STL 实现的最佳方法是什么。
最佳答案
您不能使用 STL 容器(例如 set
,据我所知,从技术上讲它甚至不需要 BST),因为它无法让您访问底层结构。
您的选择是:
正如您已经提到的,编写您自己的 BST。
只需使用按您的整数值排序的辅助 BST(或堆)。
使用 Boost 的
multi_index_container
.
关于C++ 扩充 STL 数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21216530/