如何处理红黑树中的重复项？

Question

所以我一直（到目前为止没有成功）试图让我的红黑树实现与重复一致地工作，但它似乎总是缺少那个小东西，所以我在这里。

我试图让树向一侧倾斜，但它似乎没有适当地平衡（从颜色的角度来看）。我想问一下应该如何向红黑树添加重复项？（显然分开使节点变胖，持有或指向重复的键值）。

不是真的在寻找代码审查，对建议更感兴趣。所以基本上我用于插入和平衡的方法（取自算法简介，第三版）是这些（而旋转很明显）：

Answer 1

如果您查看您在此处编写的伪代码，则对于键是否重复的问题完全不可知。这里的代码只看key的比较结果，并不关心它们是否相同。事实上，唯一键的实现需要不遗余力地RB-Insert检测重复键。数据结构自然不关心这个，算法和证明都持有是否存在重复键。如果您正确实现了这些功能，它应该可以正常工作。

我也不同意建议您保留所谓的“胖节点”的评论。例如，持有多个键是 C++ 的常见实现std::multimap。从计算复杂性的角度来看，并不是说你总共有n 个键，但每个k都是一个倍数。使用“高效”的胖节点版本，基本查找操作的复杂度将为Θ(log(n / k)) = Θ(log(n) - log(k))；使用多密钥版本，复杂度将为Θ(log(n))。在现实生活中，可能k << n，这意味着相对差异可以忽略不计。