java - 有重复的 BST

Question

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

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

    R
    /\
   A  S
    \
     B

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

他们让我画：

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

任何帮助表示赞赏！

PS：帮我画相关的树

Answer 1

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

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

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

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

或者

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

或者

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

所以你的BSTfor word "RABSAB"，重复的可能是这样的：

     R
    / \
   A   S
  / \
 A   B
    /
   B

或者，

     R
    / \
   A   S
    \
     A
      \
       B
        \
         B

或者

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

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

第三种情况更容易维护。

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

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

对于您的输入RABPAB，您可以BST使用 LIST 创建一个来存储所有等值键。所有相等值的键都使用能够存储它的数据结构放置在同一级别。

BST 看起来像这样，

     R
    / \
A--A   P
    \
  B--B

您的 BST 存储整数值的 Java 代码可能是这样的，

class Node 
{
    Node left, right;
    int data[maxvalue];
}

这maxvalue是最大可能的等值键。

Answer 4

在正常的 BST 插入和搜索中，都基于小于 (>) 和大于 (<) 规则。

您可以改为尝试在小于等于 (>=) 或大于等于 (<=) 上插入，并尝试使用相同的规则进行搜索。

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