如何在二叉搜索树中允许重复值？

Question

我不需要代码，只需要概念。

根据UC伯克利分校（在线CS61b课程）的Jonathan Shewchuck教授的说法，如果找到一个完全匹配的节点，可以将新条目作为左子节点插入。

假设您总是选择完全匹配的左节点并在那里插入新条目，如果您找到的完全匹配已经有一个左子节点会发生什么？您会将其分离并强制在其位置上插入新条目，并重新将旧左子节点附加为此新节点的子节点吗？

如果完全匹配已经有一个左子节点，该左子节点本身就是一个完全匹配怎么办？如果允许重复，代码是否变得太复杂？

- Foo

Answer 1

在连接节点之前，您需要尽可能地向左移动。按照常规插入逻辑将新节点插入到左子树中。例如，如果您要插入的是

5, 3, 7, 2, 3, 8, 7, 2, 5

结果树将看起来像这样：

                      5
                    /   \
                   3     7
                  / \   / \
                 2   5 7   8
                / \
               2   3

请注意，此树中的3和5不在一起，因为在我们插入重复项时，第一个3已经有了左子节点，5也是如此。

当然，这并不理想，因为查找并不会在找到所需元素时结束。更好的方法是通过在树结构中放置每个节点的重复计数或附加到每个单独节点的数据列表来增强树结构，如果树用于关联存储。

                     5(2)
                    /    \
                  3(2)   7(2)
                 /         \
               2(2)        7(1)

- Sergey Kalinichenko