BST有重复

Question

我知道,BST不允许重复.例如,如果我有一个单词"RABSAB".

上述字符串的二进制搜索树是:

    R
    /\
   A  S
    \
     B

如果我们想在树中包含重复项,该怎么办？树怎么会改变？我在接受采访时被问到这个问题.

他们让我画画:

1. 二叉树
2. 不平衡的二进制搜索树
3. 没有重复的二叉搜索树
4. 带有重复项的二叉搜索树

任何帮助表示赞赏!

PS:通过绘制相关树帮助我

Answer 1

在不重复的二进制搜索树中插入的规则是:

1. 如果元素小于root,则向左移动
2. 如果元素大于root,则向右移动.

要允许重复输入,您必须修改规则,如下所示:

1. 如果元素小于或等于root,则向左移动
2. 如果元素大于root,则向右移动.

要么

1. 如果元素小于root,则向左移动
2. 如果元素大于或等于root,则向右移动.

要么

1. 如果元素小于root,则向左移动
2. 如果元素大于root,则向右移动.
3. 如果元素等于根,则增加计数.

所以你BST的单词"RABSAB",重复可以像:

     R
    / \
   A   S
  / \
 A   B
    /
   B

要么,

     R
    / \
   A   S
    \
     A
      \
       B
        \
         B

要么

    R(1)
   /  \
  /    \
 A(2)  S(1)
  \
   \
   B(2)

在前两种情况下,插入和搜索都变得有点复杂!你会在这里找到很多解释!

第三种情况更容易维护.

所有这些都成功用于允许重复,现在选择是你的!