我正在学习数据结构和算法。特别是，我正在学习二进制搜索树(BST(。
正如标题所暗示的那样，我的问题是，如果我们正在放置一个值，并且它等于它的父值，我们应该将它放在哪一边？左侧用于小于父级的值，右侧用于大于父级的数值。那么，我们在哪里放置与父项相等的值呢？
谢谢你在这方面的帮助。
没有一种普遍认可的标准方法。有些人根本不允许BST存储重复项，本质上就是定义了这个问题。(这是在将树用于地图和集合时经常看到的情况(。其他实现可能通过使用链表将所有相等的键存储在同一节点中。其他人可能会说，左子树包含较小的键，而右子树包含大于或等于节点自身键的键。
每种方法都有优点和缺点，您可以选择哪种方法最适合您的用例。
算法只需选择在哪一侧插入与当前节点相同的值。当然，当选择总是相同时，实施起来最容易(而且成本效益高(。
然而，二进制搜索树只有在保持一定平衡的情况下才能保证对数效率，因此我们还必须考虑重新平衡对具有相同值的节点的位置会产生什么影响。
例如，如果二进制搜索树是AVL树，那么当任何子树中存在大于1的不平衡时，都会发生旋转。
让我们假设我们有一个AVL树的算法，当值等于当前节点的值时，它会选择右侧。假设我们在一个空树中按顺序插入值1、1和2。然后在第二次插入之后，我们得到：
1
1 (insert at right side of root)
然后我们插入2:
1
1
2
现在AVL机制执行一个简单的左旋转，我们最终得到：
1
/
1 2
现在，第二个插入的节点成为根，将原始根放在其左侧。
因此，总之，当我们谈到自平衡二进制搜索树时，即使算法选择一个特定的边来插入重复值，由于树的再平衡特性，也不能保证所有相等的值总是在该边找到。
正如@templateypepedef所提到的，一种常见的方法是只允许BST中每个值(即密钥(有一个节点。对于多集语义(跟踪密钥存在的次数(，在每个节点存储一个计数器就足够了。这种方法简单而高效。