在二叉搜索树中插入重复值

Question

我可以在二叉搜索树中插入相同的值吗？ 如果可以的话，这个插入应该发生在具有该值的现有节点的左侧还是右侧？

我可以向这棵树插入 23 吗？

Answer 1

是的，除非实际上下文另有规定，否则二叉搜索树可以有重复项。选择一方没有规则。

此外，即使双方达成一致，二叉搜索树通常也是自平衡的，这意味着这种选择不会得到维持。

例如，想象一下极端情况，仅将值 42 插入树中，例如五次，并且我们同意将重复项插入到右子树中，那么我们将得到这棵树：

       42
         \
          42
            \
             42
               \
                42
                  \
                   42

但是，BST 会在几次插入后重新平衡，并且生成的树将更像这样（通过重新平衡）：

       42
      /  \
    42    42
      \     \
       42    42
       

现在很明显，您不能假设重复值可以存储在哪一侧。

另一种方法是允许重复，但不将它们存储为单独的节点。相反，您可以将“有效负载”（如果有）设置为使用相同密钥插入的数据数组。或者，如果没有与密钥一起使用的有效负载，请在每个节点处有一个

counter 指示插入该密钥的频率。

这可能更好。