BST 中出现重复的情况是怎样的？
如何解决二叉搜索树的重复问题？
How to solve the problem with duplication in Binary Search Tree?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
如何解决二叉搜索树的重复问题？
How to solve the problem with duplication in Binary Search Tree?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（2）
我不太确定你在问什么。但这不会阻止我发布答案。
通常，BST 中不允许出现重复的键。这往往会让事情变得容易得多，而且这种情况很容易避免。
如果您确实希望允许重复，那么插入不是问题。您可以将其粘贴到左子树或右子树中。
问题是，如果它是像 AVL 树或红黑树这样的自平衡树，则不能指望特定一侧的重复项。看起来这可能是删除的问题，但我曾经实现过一个 AVL 树，它没有对重复项做出特殊规定，而且完全没有问题。
从 AVL 树中删除节点涉及 (1) 查找该节点，(2) 用左子树中的最大键或右子树中的最小键替换该节点，然后递归删除该节点。如果没有子树，则无需执行任何操作。
实际上，删除具有重复项的节点意味着具有最接近根的所查找键的节点将被替换为具有另一个键的节点或具有相同键的节点。无论哪种方式，都不会违反排序约束，一切都会顺利进行。
我不知道红黑树或其他类型的 BST。
I am not really sure what you are asking. But that won't stop me from posting an answer.
Usually, duplicate keys are disallowed in a BST. That tends to make things a lot easier, and it is a condition that is easy to avoid.
If you do want to allow duplicates, then insertions are not a problem. You can just stick it either in the left subtree or the right subtree.
The problem is that you can't count on the duplicates being on a particular side if it is a self-balancing tree like an AVL-tree or a red-black-tree. It seems like this might be a problem for deletions, but I once implemented an AVL-tree that made no special provisions for duplicates, and it had no problems at all.
Deleting a node from an AVL tree involves (1) finding the node, (2) replacing that node with either the greatest key in the left subtree or the smallest key in the right subtree, and then recursively deleting that node. If there is no subtree, then nothing more needs to be done.
In practice, deleting a node with duplicates means that the node with the sought key nearest the root will be replaced with something, either a node with another key, or a node with the same key. Either way, the ordering constraints are not violated, and everything proceeds with no trouble.
I don't know about red-black trees or other sorts of BSTs.
这取决于您的比较检查：如果 equal 和 lesser 相等，则重复项将被放置在“较小”节点中，否则它们将被放置在“较大”节点中。除此之外，不应该存在重复的问题，除非您当然想避免它们，在这种情况下您需要额外的相等检查。
It's up to your comparison check: if equal and smaller are equivalent, duplicates will be placed in the "smaller" node, otherwise they're in the "larger" node. Besides this, there shouldn't be an issue with duplicates, unless you want to avoid them of course, in which case you need an extra equality check.