带有重复元素的二叉搜索树

Question

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

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

    R
    /\
   A  S
    \
     B

如果我们想在树中包含重复项，那么树会如何变化？我在面试中被问到了这个问题。

他们要求我画出：

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

任何帮助都将不胜感激！

附注：请通过绘制相关的树来帮助我。

- user

---

“BST”并不限制不允许重复，您可以保留重复项，详见：二叉搜索树中处理重复项的策略。 - Grijesh Chauhan

我是在一般情况下说的。我在维基百科上读到，一般情况下BST不允许重复。你能帮忙画出给定字符串的BST吗？ - user

可能是二叉搜索树的定义中允许重复键吗？的重复问题，因为对于该问题的任何好答案都必须考虑如何实现这样的BST。 - Ciro Santilli OurBigBook.com

Answer 1

二叉搜索树中插入无重复元素的规则为：

1. 如果元素小于根节点，则向左移动。
2. 如果元素大于根节点，则向右移动。

如果允许重复项，则需要修改规则如下：

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

或者

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

或者

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

因此，对于单词"RABSAB"，带有重复项的二叉搜索树可以是：

     R
    / \
   A   S
  / \
 A   B
    /
   B

或者，

     R
    / \
   A   S
    \
     A
      \
       B
        \
         B

或者

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

在前两种情况下，插入和搜索都变得有点复杂了！你可以在这里找到详细的解释！

而第三种情况则相对容易维护。

它们都被成功地用于允许重复项，现在选择权在于你！

- Sazzadur Rahaman

---

你已经向我提供了所有的情景。 - user

在重复的情况下，你总是向左移动吗？ - Songo

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;
}

- Zim-Zam O'Pootertoot

---

保留“List data”会增加遍历列表的开销，然后再将其添加到列表中，保留计数器更合适。 - Hussain Akhtar Wahid 'Ghouri'

Answer 3

针对您的输入RABPAB，您可以使用一个列表来存储所有相等的键，从而创建一个BST。所有相等的键都将使用能够存储它的数据结构放置在同一层级上。

BST将会看起来像这样：

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

存储整数值的二叉搜索树的Java代码可能如下所示：

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

这里的maxvalue是可能存在的最大相等键。

- Deepu

Answer 4

在普通的二叉搜索树中，插入和搜索都是基于大于(>)和小于(<)规则进行的。

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

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

- amitdonanand