c++ - 处理二叉搜索树中重复键的性能规范

Question

我正在阅读算法导论这本书，寻找处理二叉搜索树中重复键的最佳方法。

这个用例提到了几种方法:

1. 在节点x处保留一个 bool 标志x:b，并将x设置为x:left 或 x:right 基于 x:b 的值，它在 FALSE 和 TRUE 之间交替每次我们访问 x，同时插入与 x 具有相同键的节点。

2. 在 x 处保留具有相同键的节点列表，并将 ´ 插入列表。

3. 随机将 x 设置为 x:left 或 x:right。

我知道每个实现都有它自己的性能命中/未命中，STL 可能以不同于 Boost Containers 的方式实现它。

C++11 规范中是否提到了处理重复键的最差时间性能的性能限制，比如 multimap？

Answer 1

就插入/删除时间而言，时间 2 总是更好，因为它不会增加树的大小，并且在您插入或删除重复项时不需要复杂的结构更改。

如果有少量重复项，选项 3 是空间最优的。

选项 1 将需要存储 1 位额外信息(在大多数实现中需要 2 个字节)，但与 1 相比，树的高度将是最佳的。

TL;DR:实现 2 有点困难，但如果重复项数量很大，则值得。否则使用 3。我不会使用 1。