algorithm - 如何在二叉搜索树中允许重复项？

Question

我不是在寻找代码，只是在寻找概念。

根据加州大学伯克利分校的 jonathan Shewchuck 教授(在线 CS61b 类(class))，如果您找到完全匹配的内容，则可以将新条目作为左 child 插入。

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

如果完全匹配已经有左 child ，它本身就是完全匹配怎么办？如果允许重复，代码会不会变得太复杂？

Answer 1

在附加节点之前，您需要尽可能地向左移动。遵循新节点到左子树的常规插入逻辑。例如，如果您要插入

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

结果树看起来像这样:

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

请注意 3 和 5 在这棵树中是如何不在一起的，因为第一个 3 当时已经有一个左 child 我们插入一个副本，5 也是如此。

当然，这并不理想，因为搜索并没有在找到所需元素时结束。更好的方法是扩充树结构，方法是在树中放置每个节点的重复项计数，或者如果树用于关联存储，则将数据列表附加到每个单独的节点。

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