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

139

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.

Tim Merrifield
fonte

Respostas:

78

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.)

Chris
fonte
1
Quais são as desvantagens de usar uma lista no nó?
Pacerier
1
@ Pacerier Acho que, em vez de manter uma lista, podemos manter uma contagem de referência em cada nó e atualizar a contagem quando ocorrer duplicação. Esse algoritmo seria muito mais fácil e eficiente na pesquisa e armazenamento. Além disso, exigiria alterações mínimas no algoritmo existente que não suporta duplicatas.
SimpleGuy
50

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!

Rico
fonte
18
Não gire quando você tiver nós iguais! Desça para o próximo nível e gire isso.
19612 Rich
2
Outras soluções são alterar a regra da árvore left <= node <= rightou inserir apenas antes da primeira ocorrência de um valor.
paxdiablo
Que problemas isso pode causar na prática? Parece-me que, se você estiver bem com a esquerda <= node <= right, todas as operações da árvore vermelho-preto funcionarão de qualquer maneira.
Björn Lindqvist
39

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.

duilio
fonte
Estou muito surpreso que isso nunca tenha sido mencionado no livro que estou usando. O prof também não mencionou, nem o fato de que chaves duplicadas são até um problema smh ...
Oloff Biermann 17/07/1919
22

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.

paxdiablo
fonte
Para o caso duplicado, você pode apenas verificar se o filho certo é o mesmo que o nó atual na cláusula node.val == srchval: e, em seguida, se estiver certo?
bneil
9

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.

Laurent Martin
fonte
4

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.

SoapBox
fonte
1
se você tiver um conjunto de dados que contenha chaves duplicadas, todos esses itens deverão ser armazenados no nó 1 da árvore por um método diferente (lista vinculada, etc.). a árvore deve conter apenas chaves exclusivas.
nickf
1
Observe também no wiki que a subárvore direita contém valores "maiores que ou iguais a" a raiz. Portanto, a definição da wiki é auto-contraditória.
SoapBox 19/11/2008
1
+1: pessoas diferentes usam definições diferentes. Se você implementar uma nova BST, precisará ter certeza de que está explícito sobre quais suposições está fazendo sobre entradas duplicadas.
Sr. Fooz
1
Parece que o consenso é (esquerda <= raiz <= direita) ao permitir duplicatas. Mas que algumas pessoas definem um BST não permitem dups. Ou talvez algumas pessoas o ensinem dessa maneira para evitar a complexidade adicional.
Tim Merrifield
1
incorreta! É ou esquerda <= root <direita ou esquerda <raiz <= direita, ou à esquerda> root> = direita ou esquerda> = root> direito
Mitch Wheat
3

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.

Jherico
fonte
2

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.

nickf
fonte
1

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).

Robert Paulson
fonte
Você poderia explicar por que a esquerda <= root <= right não é o ideal?
Helin Wang
Dê uma olhada na resposta aceita por @paxdiablo - Você pode ver que o valor duplicado pode existir >=. O ideal depende de seus requisitos, mas se você possui muitos valores duplicados e permite que os duplicados existam na estrutura, seu bst pode acabar sendo linear - isto é, O (n).
Robert Paulson
1

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.

mszlazak
fonte
1

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 .

Lazy Ren
fonte
0

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!

Alberto
fonte