Manejo duplica llaves dentro de un árbol AVL

Question

Quiero hacer que mi avl-tree soporte llaves duplicadas pero hay un problema con el comportamiento predeterminado del binary search tree con duplicados que la rotación podría hacer que los nodos con la misma clave estén a la izquierda ya la derecha de el padre.

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 

así que conseguir todas las entradas con esa clave será un problema ... y buscar en ambas direcciones no es bueno.

La solución que he pensado es hacer cada nodo almacena un conjunto de duplicados por lo que cuando la adición de un nuevo elemento que ya existe será sólo añadir un nuevo elemento a la matriz, Eliminación del artículo con llave eliminará la totalidad nodo mientras el hallazgo de todos los elementos con la clave devolverá esa matriz.

¿Existen otros métodos para manejar duplicados?

El elemento de inserción toma una clave y un valor ... así que necesito almacenar los valores en orden para devolverlos mediante findAll con cierto método de clave.

Answer 1

Otro enfoque general es hacer que el valor forme parte de la clave internamente para que ya no tenga claves duplicadas. De todos modos, necesitará la clave y el valor para eliminar una entrada de un árbol que permita duplicados.

Para buscar una clave sin conocer el valor, usted entonces hacer algo como (pseudo-código):

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

Answer 2

Haga que cada nodo contenga un recuento: la adición de duplicados incrementará el recuento, las eliminaciones disminuirán el recuento a menos que sea 1, en cuyo caso se eliminará todo el nodo.