如果一个节点等于二叉搜索树中的parent，我们把它放在哪一边
Which side do we place a node if it is equal to the parent in a binary search tree
我正在学习数据结构和算法。特别是，我正在学习二叉搜索树 (BST)。
我的问题，正如标题所暗示的那样，如果我们放置一个值，并且它等于它的 parent，我们应该把它放在哪一边？左侧是小于 parent 的值，右侧是大于 parent 的值。那么，我们在哪里放置等于 parent 的值？
感谢您对此的任何帮助。
没有一个普遍认可的标准方法来做到这一点。有些人根本不允许 BST 存储重复项，基本上定义了这个问题。 （这就是您在将树用于地图和集合时经常看到的）。其他实现可能将所有相同的键存储在同一个节点中，可能通过使用链表。其他人可能会说左子树包含较小的键，而右子树包含大于或等于节点自身键的键。
这些方法中的每一种都有优点和缺点，select哪种方法最适合您的用例取决于您。
算法只是选择在哪一侧插入与当前节点相同的值。 It is of course easiest (and cost effective) to implement when that choice is always the same.
但是，二叉搜索树只有在保持一定平衡的情况下才能保证对数效率，因此我们还必须考虑重新平衡对具有相同值的节点位置的影响。
例如，如果二叉搜索树是AVL树，那么当任何子树中的不平衡度大于1时，就会发生旋转。
假设我们有一个 AVL 树的算法，当值等于当前节点的值时选择右侧。假设我们在一棵空树中按顺序插入值 1、1 和 2。然后在第二次插入之后，我们得到这个：
1
\
1 (insert at right side of root)
然后我们插入2:
1
\
1
\
2
现在 AVL 机械师执行简单的左旋转，我们最终得到：
1
/ \
1 2
...现在第二个插入的节点成为根，将原始根放在左侧侧。
所以，总而言之，当我们谈到 自平衡 二叉搜索树时，即使算法选择了一个特定的边来插入重复值，也没有由于树的重新平衡特性，保证在该侧总是 found 所有相等的值。
正如@templatetypedef 提到的，一种常见的方法是只允许 BST 中的每个值（即键）有一个节点。对于多集语义（跟踪一个键出现的次数），在每个节点存储一个计数器就足够了。这种方法简单有效。
我正在学习数据结构和算法。特别是，我正在学习二叉搜索树 (BST)。
我的问题，正如标题所暗示的那样，如果我们放置一个值，并且它等于它的 parent，我们应该把它放在哪一边？左侧是小于 parent 的值，右侧是大于 parent 的值。那么，我们在哪里放置等于 parent 的值？
感谢您对此的任何帮助。
没有一个普遍认可的标准方法来做到这一点。有些人根本不允许 BST 存储重复项，基本上定义了这个问题。 （这就是您在将树用于地图和集合时经常看到的）。其他实现可能将所有相同的键存储在同一个节点中，可能通过使用链表。其他人可能会说左子树包含较小的键，而右子树包含大于或等于节点自身键的键。
这些方法中的每一种都有优点和缺点，select哪种方法最适合您的用例取决于您。
算法只是选择在哪一侧插入与当前节点相同的值。 It is of course easiest (and cost effective) to implement when that choice is always the same.
但是，二叉搜索树只有在保持一定平衡的情况下才能保证对数效率，因此我们还必须考虑重新平衡对具有相同值的节点位置的影响。
例如，如果二叉搜索树是AVL树，那么当任何子树中的不平衡度大于1时，就会发生旋转。
假设我们有一个 AVL 树的算法，当值等于当前节点的值时选择右侧。假设我们在一棵空树中按顺序插入值 1、1 和 2。然后在第二次插入之后，我们得到这个：
1
\
1 (insert at right side of root)
然后我们插入2:
1
\
1
\
2
现在 AVL 机械师执行简单的左旋转，我们最终得到：
1
/ \
1 2
...现在第二个插入的节点成为根，将原始根放在左侧侧。
所以，总而言之，当我们谈到 自平衡 二叉搜索树时，即使算法选择了一个特定的边来插入重复值，也没有由于树的重新平衡特性，保证在该侧总是 found 所有相等的值。
正如@templatetypedef 提到的，一种常见的方法是只允许 BST 中的每个值（即键）有一个节点。对于多集语义（跟踪一个键出现的次数），在每个节点存储一个计数器就足够了。这种方法简单有效。