BST有重复 [英] BST with duplicates

问题描述

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

I know that, BST does not allow duplicates. For example, if I have a word "RABSAB".

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

The Binary search tree for the above string is:

    R
    /\
   A  S
    \
     B

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

What if we wanted to include the duplicates in the tree. How the tree gonna change? I was asked this question in an interview.

他们让我画画：

1. 二叉树


2. 不平衡的二进制搜索树


3. 没有重复的二进制搜索树


4. a具有重复的二元搜索树

1. a binary tree
2. an unbalanced Binary Search Tree
3. a binary search tree without duplicates
4. a binary search tree with duplicates

感谢任何帮助！

PS：通过绘制相关的树来帮助我

PS: Help me by drawing the related trees

推荐答案

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

Rule to insert in a binary Search tree without duplicate is:

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


2. 如果元素大于root，则向右移动。

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

And to allow duplicate entries you have to modify the rule like bellow:

1. 如果元素小于或等于root，则向左移动


2. 如果元素大于root，则向右移动。

或

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


2. 如果是的话，走吧元素大于或等于根。

或

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


2. 如果元素大于root，则向右移动。


3. 如果元素增加计数等于根。

所以你的 BST 代表 RABSAB，有重复项可以是：

So your BST for word "RABSAB", with duplicates can be like:

     R
    / \
   A   S
  / \
 A   B
    /
   B

或者，

     R
    / \
   A   S
    \
     A
      \
       B
        \
         B

或

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

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

In First two cases, both insertion and search becomes bit complex! You will find it here with great deal of explanation!

第三种情况更容易维护。

And the third case is somewhat easier to maintain.

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

All of them are used successfully to allow duplicates, now the choice is yours!

这篇关于BST有重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！