java - 有重复的 BST

Question

我知道，BST 不允许重复。例如，如果我有一个词“RAABSAB”。

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

    R
    /\
   A  S
    \
     B

如果我们想在树中包含重复项怎么办。树会怎么变？我在采访中被问到这个问题。

他们让我画:

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

感谢任何帮助!

PS:帮我画出相关的树

Answer 1

在没有重复的情况下插入二叉搜索树的规则是:

1. 如果元素小于根则向左走
2. 如果元素大于根，则向右走。

要允许重复条目，您必须像下面这样修改规则:

1. 如果元素小于或等于根则向左走
2. 如果元素大于根，则向右走。

或

1. 如果元素小于root则向左走
2. 如果元素大于或等于根，则向右走。

或

1. 如果元素小于root则向左走
2. 如果元素大于根，则向右走。
3. 如果元素等于根，则增加计数。

所以你的 BST 单词 "RABSAB" 可以像这样:

     R
    / \
   A   S
  / \
 A   B
    /
   B

或者，

     R
    / \
   A   S
    \
     A
      \
       B
        \
         B

或

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

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

第三种情况更容易维护。

所有这些都已成功使用以允许重复，现在选择权在你!