Manejo de llaves duplicadas dentro de un árbol AVL

Question

Quiero hacer duplicados de las llaves de mi apoyo avl-tree pero hay un problema con el comportamiento por defecto de la binary search tree con duplicados que la rotación podría hacer que los nodos con la misma llave está a la izquierda y la derecha de la matriz.

Por ejemplo, cuando la adición de tres nodos todos con la tecla A hará que el árbol para hacer una rotación a ser algo como esto:

   A
  /  \ 
 A    A

Por eso, conseguir todas las entradas con esa clave será un problema ... y buscando en ambas direcciones, no es bueno.

La solución que he pensado está haciendo cada nodo almacena una matriz de duplicados por lo que cuando se añade un nuevo elemento que ya existe se acaba de añadir un nuevo elemento a la matriz, Eliminación del artículo con llave borrará todo el nodo, mientras que el encontrar todos los artículos con llave devolverá esa matriz.

¿Hay algún otro método para manejar duplicados?

El elemento de inserción tiene una clave y un valor .. por eso es necesario para almacenar los valores finde para devolverlos por el findAll con cierto método clave.

Answer 1

Otro enfoque general consiste en hacer que la parte interna valor de la clave para que realmente no tiene duplicados de las llaves más. Usted necesitará la clave y el valor de todos modos con el fin de eliminar una entrada de un árbol que permite duplicados.

Para buscar una clave sin conocer el valor, que sería luego hacer algo como (pseudo-código):

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

Answer 2

Tener cada nodo contener un recuento: adición de duplicados incrementará el recuento, el traslado disminuirá el recuento a menos que sea 1, en cuyo caso se eliminará todo el nodo

.