具有重复项的BST

Question

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

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

    R
    /\
   A  S
    \
     B

如果我们想在树中包含重复项呢。这棵树将如何改变？我在一次采访中被问到这个问题。

他们让我画：

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

感谢您的帮助！

PS：帮我画相关的树

Answer 1

在正常的BST中，插入和搜索都是基于小于(

您可以尝试在小于等于的位置插入(

或者，可以在每个节点中包含一个数组，以容纳重复的元素。

Answer 2

一个选项是修改树，以便一个分支将包含重复的节点，例如，让左分支保留小于或等于父节点的节点，或者让右分支保留大于或等于父节点的节点

另一种选择是将所有重复项存储在一个节点中，因此

class Node {
    Node left, right;
    Object data;
}

你反而会

class Node {
    Node left, right;
    List data;
}

或

class Node {
    Node left, right;
    Object data;
    int count;
}

Answer 3

在没有重复的二进制搜索树中插入的规则是：

1. 如果元素小于根，则向左移动

要允许重复条目，您必须修改如下规则：

1. 如果元素的根小于或等于

或

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

或

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

所以你的单词“RABSAB”的BST可以是这样的：

     R
    / \
   A   S
  / \
 A   B
    /
   B

或

     R
    / \
   A   S
    \
     A
      \
       B
        \
         B

或

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

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

第三种情况更容易维持。

所有这些都被成功地用于允许复制，现在你可以选择了！