BST中重复出现什么情况? [英] What's the case for duplications in BST?

问题描述

如何解决二进制搜索树中的重复问题?

How to solve the problem with duplication in Binary Search Tree?

推荐答案

我不确定您要问什么.但这不会阻止我发布答案.

I am not really sure what you are asking. But that won't stop me from posting an answer.

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

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.

问题是，如果它是像AVL树或红黑树这样的自平衡树，则不能指望特定一侧的重复项.似乎这对于删除来说可能是个问题，但是我曾经实现了一个AVL树，该树没有为重复项做任何特殊规定，而且完全没有问题.

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.

从AVL树中删除节点包括(1)找到该节点，(2)用左子树中的最大键或右子树中的最小键替换该节点，然后递归删除该节点.如果没有子树，则无需执行其他操作.

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.

我不知道红黑树或其他种类的BST.

I don't know about red-black trees or other sorts of BSTs.

这篇关于BST中重复出现什么情况?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！