Chaves duplicadas são permitidas na definição de árvores de pesquisa binária?

Estou tentando encontrar a definição de uma árvore de pesquisa binária e continuo encontrando definições diferentes em todos os lugares.

Alguns dizem que, para qualquer subárvore, a chave filha esquerda é menor ou igual à raiz.

Alguns dizem que, para qualquer subárvore, a chave filha correta é maior ou igual à raiz.

E meu antigo livro de estruturas de dados da faculdade diz que "todo elemento tem uma chave e não dois elementos têm a mesma chave".

Existe uma definição universal de bst? Particularmente em relação ao que fazer com árvores com várias instâncias da mesma chave.

EDIT: Talvez eu não estivesse claro, as definições que estou vendo são

1) esquerda <= raiz <direita

2) esquerda <raiz <= direita

3) esquerda <raiz <direita, de modo que não haja chaves duplicadas.

Muitos algoritmos especificarão que duplicatas são excluídas. Por exemplo, os algoritmos de exemplo no livro MIT Algorithms geralmente apresentam exemplos sem duplicatas. É bastante trivial implementar duplicatas (como uma lista no nó ou em uma direção específica).

A maioria (que eu vi) especifica filhos à esquerda como <= e filhos à direita como>. Na prática, um BST que permita que os filhos da direita ou da esquerda sejam iguais ao nó raiz, exigirá etapas computacionais extras para concluir uma pesquisa em que nós duplicados são permitidos.

É melhor utilizar uma lista no nó para armazenar duplicatas, pois inserir um valor '=' em um lado de um nó exige reescrever a árvore desse lado para colocar o nó como filho ou o nó é colocado como um grande -child, em algum momento abaixo, o que elimina parte da eficiência da pesquisa.

Você deve se lembrar, a maioria dos exemplos em sala de aula é simplificada para retratar e entregar o conceito. Eles não valem agachamento em muitas situações do mundo real. Mas a declaração "cada elemento tem uma chave e não dois elementos têm a mesma chave" não é violada pelo uso de uma lista no nó do elemento.

Então siga o que o seu livro de estruturas de dados disse!

Editar:

A definição universal de uma árvore de pesquisa binária envolve o armazenamento e a pesquisa de uma chave com base no deslocamento de uma estrutura de dados em uma das duas direções. No sentido pragmático, isso significa que, se o valor for <>, você percorre a estrutura de dados em uma das duas 'direções'. Portanto, nesse sentido, valores duplicados não fazem nenhum sentido.

Isso é diferente do BSP, ou partição de pesquisa binária, mas não tão diferente assim. O algoritmo a ser pesquisado tem uma das duas direções para 'viajar', ou está pronto (com êxito ou não). Portanto, peço desculpas por minha resposta original não ter abordado o conceito de 'definição universal', pois duplicatas são realmente distintas tópico (algo com o qual você lida após uma pesquisa bem-sucedida, não como parte da pesquisa binária.)

Se sua árvore de pesquisa binária for uma árvore vermelha e preta, ou você pretender qualquer tipo de operação de "rotação de árvore", nós duplicados causarão problemas. Imagine sua regra de árvore:

esquerda <raiz <= direita

Agora imagine uma árvore simples cuja raiz seja 5, o filho esquerdo seja nulo e o filho direito seja 5. Se você fizer uma rotação esquerda na raiz, você terminará com 5 no filho esquerdo e 5 na raiz com filho direito sendo nulo. Agora, algo na árvore esquerda é igual à raiz, mas sua regra acima assumiu a esquerda <raiz.

Passei horas tentando descobrir por que minhas árvores vermelhas / pretas ocasionalmente atravessavam fora de ordem, o problema foi o que descrevi acima. Espero que alguém leia isso e economize horas de depuração no futuro!

Todas as três definições são aceitáveis ​​e corretas. Eles definem diferentes variações de um BST.

O livro da estrutura de dados da sua faculdade não conseguiu esclarecer que sua definição não era a única possível.

Certamente, permitir duplicatas aumenta a complexidade. Se você usar a definição "left <= root <right" e tiver uma árvore como:

      3
    /   \
  2       4

adicionar uma chave duplicada "3" a esta árvore resultará em:

      3
    /   \
  2       4
    \
     3

Observe que as duplicatas não estão em níveis contíguos.

Esse é um grande problema ao permitir duplicados em uma representação BST como a acima: os duplicados podem ser separados por qualquer número de níveis; portanto, verificar a existência de duplicados não é tão simples como verificar apenas os filhos imediatos de um nó.

Uma opção para evitar esse problema é não representar duplicatas estruturalmente (como nós separados), mas usar um contador que conte o número de ocorrências da chave. O exemplo anterior teria então uma árvore como:

      3(1)
    /     \
  2(1)     4(1)

e após a inserção da chave "3" duplicada, ela se tornará:

      3(2)
    /     \
  2(1)     4(1)

Isso simplifica as operações de pesquisa, remoção e inserção, às custas de alguns bytes extras e operações de contador.

Em uma BST, todos os valores que descem no lado esquerdo de um nó são menores que (ou iguais a, veja mais adiante) o próprio nó. Da mesma forma, todos os valores que descem no lado direito de um nó são maiores que (ou iguais a) o valor dos nós ^(a) .

Alguns BSTs podem optar por permitir valores duplicados, daí os qualificadores "ou iguais a" acima.

O exemplo a seguir pode esclarecer:

            |
      +--- 14 ---+
      |          |
+--- 13    +--- 22 ---+
|          |          |
1         16    +--- 29 ---+
                |          |
               28         29

Isso mostra uma BST que permite duplicatas - você pode ver que, para encontrar um valor, inicia no nó raiz e desce a subárvore esquerda ou direita, dependendo de o valor da pesquisa ser menor ou maior que o valor do nó.

Isso pode ser feito recursivamente com algo como:

def hasVal (node, srchval):
    if node == NULL:
         return false
    if node.val == srchval:
        return true
    if node.val > srchval:
        return hasVal (node.left, srchval)
    return hasVal (node.right, srchval)

e chamando-o com:

foundIt = hasVal (rootNode, valToLookFor)

As duplicatas adicionam um pouco de complexidade, pois talvez você precise continuar pesquisando depois de encontrar seu valor para outros nós do mesmo valor.

^(a) Na verdade, você pode classificá-los na direção oposta, se desejar, desde que ajuste a forma como procura por uma chave específica. Uma BST precisa apenas manter uma ordem classificada, seja ela ascendente ou descendente, não é relevante.

No livro "Introdução aos algoritmos", terceira edição, de Cormen, Leiserson, Rivest e Stein, uma árvore de pesquisa binária (BST) é explicitamente definida como permitindo duplicatas . Isso pode ser visto na figura 12.1 e no seguinte (página 287):

"As chaves em uma árvore de pesquisa binária são sempre armazenadas de maneira a satisfazer a propriedade da árvore de pesquisa binária: Seja xum nó em uma árvore de pesquisa binária. Se yé um nó na subárvore esquerda de x, então y:key <= x:key. If yis um nó na subárvore direita de x, então y:key >= x:key. "

Além disso, um vermelho-preto árvore é então definido na página 308 como:

"Uma árvore vermelho-preta é uma árvore de pesquisa binária com um bit extra de armazenamento por nó: sua cor"

Portanto, as árvores vermelho-preto definidas neste livro oferecem suporte a duplicatas.

Qualquer definição é válida. Contanto que você seja consistente em sua implementação (sempre coloque nós iguais à direita, sempre à esquerda ou nunca permita), estará bem. Eu acho que é mais comum não permitir, mas ainda é um BST se eles são permitidos e colocam à esquerda ou à direita.

Trabalhando em uma implementação de árvore vermelho-preto, eu estava tendo problemas para validar a árvore com várias chaves até perceber que, com a rotação da pastilha vermelho-preto, é necessário diminuir a restrição para

left <= root <= right

Como nenhuma documentação que eu estava olhando permitia chaves duplicadas e não queria reescrever os métodos de rotação para explicá-la, apenas decidi modificar meus nós para permitir vários valores dentro do nó e nenhuma chave duplicada em a árvore.

Essas três coisas que você disse são verdadeiras.

• Chaves são únicas
• À esquerda estão as teclas menos que esta
• À direita estão as chaves maiores que esta

Suponho que você poderia reverter sua árvore e colocar as chaves menores à direita, mas realmente o conceito "esquerda" e "direita" é apenas isso: um conceito visual para nos ajudar a pensar em uma estrutura de dados que realmente não tem esquerda ou certo, então isso realmente não importa.

1.) esquerda <= raiz <direita

2.) esquerda <raiz <= direita

3.) esquerda <raiz <direita, de modo que não exista nenhuma chave duplicada.

Talvez eu precise cavar meus livros de algoritmos, mas em cima da minha cabeça (3) está a forma canônica.

(1) ou (2) só ocorrem quando você começa a permitir nós duplicados e coloca nós duplicados na própria árvore (em vez do nó que contém uma lista).

Chaves duplicadas • O que acontece se houver mais de um item de dados com a mesma chave? - Isso apresenta um pequeno problema em árvores vermelho-pretas. - É importante que os nós com a mesma chave sejam distribuídos nos dois lados de outros nós com a mesma chave. - Ou seja, se as chaves chegarem na ordem 50, 50, 50, • você deseja que o segundo 50 vá para a direita do primeiro e o terceiro 50 vá para a esquerda do primeiro. • Caso contrário, a árvore fica desequilibrada. • Isso pode ser tratado por algum tipo de processo aleatório no algoritmo de inserção. - No entanto, o processo de pesquisa fica mais complicado se todos os itens com a mesma chave tiverem que ser encontrados. • É mais fácil proibir itens com a mesma chave. - Nesta discussão, assumiremos que duplicatas não são permitidas

Pode-se criar uma lista vinculada para cada nó da árvore que contém chaves duplicadas e armazenar dados na lista.

Eu só quero adicionar mais algumas informações ao que o Robert Paulson respondeu.

Vamos supor que o nó contenha chave e dados. Portanto, nós com a mesma chave podem conter dados diferentes.
(Portanto, a pesquisa deve encontrar todos os nós com a mesma chave)

1) esquerda <= cur <direita

2) esquerda <cur <= direita

3) esquerda <= cur <= direita

4) left <cur <right && cur contém nós irmãos com a mesma chave.

5) esquerda <cur <direita, de modo que não haja chaves duplicadas.

1) e 2) funciona bem se a árvore não possui nenhuma função relacionada à rotação para evitar assimetria.
Mas esse formulário não funciona com a árvore AVL ou a árvore Vermelho-Preto , porque a rotação quebrará o principal.
E mesmo que search () encontre o nó com a chave, ele deve passar para o nó folha para os nós com chave duplicada.
Tornando a complexidade do tempo para a pesquisa = theta (logN)

3) funcionará bem com qualquer forma de BST com funções relacionadas à rotação.
Mas a pesquisa terá O (n) , arruinando o propósito de usar o BST.
Digamos que temos a árvore como abaixo, com 3) principal.

         12
       /    \
     10     20
    /  \    /
   9   11  12 
      /      \
    10       12

Se pesquisarmos (12) nessa árvore, mesmo que encontremos 12 na raiz, devemos continuar pesquisando o filho esquerdo e direito para procurar a chave duplicada.
Isso leva O (n) tempo como eu disse.

4) é o meu favorito. Digamos que irmão significa o nó com a mesma chave.
Podemos mudar acima da árvore para abaixo.

         12 - 12 - 12
       /    \
10 - 10     20
    /  \    /
   9   11  12

Agora, qualquer pesquisa terá O (logN) porque não precisamos atravessar filhos para a chave duplicada.
E esse principal também funciona bem com a árvore AVL ou RB .

Os elementos que ordenam a relação <= são uma ordem total, portanto a relação deve ser reflexiva, mas geralmente uma árvore de pesquisa binária (também conhecida como BST) é uma árvore sem duplicatas.

Caso contrário, se houver duplicatas, você precisará executar duas ou mais vezes a mesma função de exclusão!