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

Question

我不是在寻找代码,只是概念.

根据加州大学伯克利分校的jonathan Shewchuck教授(在线CS61b课程),如果您找到完全匹配,您可以将您的新条目作为左孩子插入.

假设您总是选择完全匹配的左侧节点并在那里插入新条目,如果您发现的完全匹配已经有一个左子,会发生什么？你是否将它拆开并在其位置强制使用新的条目并将旧的左孩子重新连接为这个新节点的孩子？

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

Answer 1

在连接节点之前,您需要尽可能地向左移动.按照新节点的常规插入逻辑进入左子树.例如,如果要插入

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

结果树看起来像这样:

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

注意3s和5s在这个树中是如何不在一起的,因为第3一个在我们插入副本时已经有一个左子,同样如此5.

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

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