为什么我们只将二叉搜索树的重复节点放在右子树或左子树中，而不是同时放在两者中？

Question

我在考试中遇到的一道试题问为什么我们只将二叉搜索树根的重复节点放在右子树或左子树中，而不是同时放在两者中，那么为什么只放置重复的根任何地方都不好，选择右或左会发生什么好事？

这个问题没有给出详细说明或图表，这是期末考试，一定只是一个隐含的假设，即这是一个常见的概念或实践。我在这次考试中仍然得了 B，但我错过了这一次，而且仍然不明白为什么你不能在任何地方都加上任何值而不考虑重复项。

Answer 1

why we only put duplicate nodes of the root of a binary search tree in either the right or left subtree?

我想你的意思是重复的值，它们存储在不同的节点中。

在二叉搜索树中存储新值的算法需要决定是向左还是向右。当要存储的值与根的值不同时，选择是唯一的。小的时候放在左子树，大的时候放在右子树。

然而，当它相等时，就变成了一个选择的问题：两种选择都可以。所以在实践中，在这种情况下，实现总是选择左边，或者总是选​​择右边——这只是实现它的最简单方法。

why is just putting duplicates of the root anywhere bad

没有人说这不好，但请考虑以下几点：

• 如果必须有时在左子树中插入，有时在右子树中插入，那么你需要引入一些额外的算法来驱动该选择，例如随机数生成，这只会减慢过程。

• 如果您需要计算树中给定值的重复次数，那么当您知道它们是all 在根的一侧。否则你需要在两个方向上遍历才能找到它们。这也是可能的，但会导致更多代码。

• 不过，如果二叉搜索树有额外的机制来保持它很好 平衡，例如 AVL 或红黑树有，那么重复值可以通过旋转在根的任一侧结束。例如，如果你的二叉搜索树是一个 AVL 树，并且插入算法是这样的，总是在 right 子树中插入相等的值，那么看看下面插入值 6 的是什么树：

    5               5                   5     
     \   insertion   \     rotation    / \
      5   =======>    5    =======>   5   6
                       \       
                        6 (inserted)
  

  ...所以重复值突然出现在左侧。