Lidar com as chaves duplicadas em uma árvore AVL

Question

Eu quero fazer meu avl-tree Apoie as teclas duplicadas, mas há um problema com o comportamento padrão do binary search tree Com duplicatas que a rotação possa fazer nós com a mesma chave estar à esquerda e à direita do pai.

Por exemplo, ao adicionar três nós, todos com a chave A farão com que a árvore faça uma rotação para ser algo assim:

   A
  /  \ 
 A    A

Portanto, obter todas as entradas com essa chave será um problema ... e pesquisar em ambas as direção não é bom.

A solução que pensei é fazer com que cada nó armazena uma variedade de duplicatas, portanto, ao adicionar um novo item que já existe, apenas adicionará um novo item à matriz, remover o item com a chave excluirá o nó inteiro enquanto o encontro de todos os itens com a chave retornará essa matriz.

Existem outros métodos para lidar com duplicatas?

O item de inserção pega uma chave e um valor. Portanto, preciso armazenar os valores inometaques para devolvê -los pelo Findall com um determinado método de chave.

Answer 1

Outra abordagem geral é tornar internamente o valor parte da chave para que você não tenha mais teclas duplicadas. De qualquer forma, você precisará da chave e do valor para excluir uma entrada de uma árvore que permita duplicatas.

Para procurar uma chave sem saber o valor, você faria algo como (pseudo-código):

searchResult = myTree.SearchGreaterOrEqual(Key);
found = (searchResult != null) && (searchResult.Key == Key);

Answer 2

Peça a cada nó que contenha uma contagem: a adição de duplicatas aumentará a contagem, as remoções diminuirão a contagem, a menos que seja 1, caso em que todo o nó será removido.