binary-search - BST 中的重复是什么情况？

Question

如何解决二叉搜索树中的重复问题？

Answer 1

我不确定你在问什么。但这不会阻止我发布答案。

通常，BST 中不允许重复键。这往往会使事情变得容易得多，而且这种情况很容易避免。

如果您确实想允许重复，那么插入不是问题。您可以将其粘贴在左子树或右子树中。

问题是，如果它是像 AVL 树或红黑树这样的自平衡树，则不能指望重复项位于特定的一侧。看起来这可能是删除的问题，但是我曾经实现过一个对重复没有特殊规定的AVL-tree，它完全没有问题。

从 AVL 树中删除节点涉及 (1) 查找节点，(2) 用左子树中的最大键或右子树中的最小键替换该节点，然后递归删除该节点。如果没有子树，则无需再做任何事情。

在实践中，删除具有重复项的节点意味着具有最接近根的所查找键的节点将被替换为具有另一个键的节点或具有相同键的节点。无论哪种方式，都不会违反排序约束，并且一切都会顺利进行。

我不知道红黑树或其他类型的 BST。

Answer 2

这取决于您的比较检查：如果相等和较小相等，则重复项将放置在“较小”节点中，否则它们将位于“较大”节点中。除此之外，重复不应该有问题，除非你当然想避免它们，在这种情况下你需要额外的相等检查。