Árbol Zip

El árbol zip fue introducido como una variante del árbol de búsqueda binaria aleatoria por Robert Tarjan , Caleb Levy y Stephen Timmel. ^{[ 1 ]} Los árboles zip son similares a los árboles max treap, excepto que los rangos se generan a través de una distribución geométrica y mantienen su propiedad de montículo máximo durante las inserciones y eliminaciones mediante descompresión y compresión en lugar de rotaciones del árbol. Los nodos del árbol contienen una clave distinta y comparable, y un rango numérico. El árbol está ordenado por montículo máximo con respecto a los rangos, y los empates se resuelven a favor de las claves más pequeñas. Los nodos del árbol deben contener claves distintas, pero permiten rangos duplicados. El criterio de desempate que favorece las claves más pequeñas crea un sesgo en el árbol que favorece a los nodos más pequeños. Una variante ligeramente modificada del árbol zip, los árboles zip-zip, abordan este sesgo introduciendo un criterio de desempate diferente con un segundo rango. ^{[ 2 ]}

Operaciones

Los árboles zip admiten las operaciones de un árbol de búsqueda binaria . Las principales diferencias de implementación radican en cómo el árbol zip implementa las operaciones de inserción y eliminación mediante la descompresión y compresión de rutas para mantener el orden del montón del árbol.

El tiempo que se tarda en insertar o eliminar un nodo u es igual al tiempo de búsqueda de u más el tiempo de descompresión o compresión. El tiempo que se tarda en descomprimir o comprimir es proporcional a uno más el número de nodos en la(s) ruta(s) que se están descomprimiendo/comprimiendo. La profundidad esperada de cualquier nodo en un árbol zip es como máximo 1,5 log n , lo que hace que el tiempo de ejecución esperado de las operaciones de inserción, eliminación y búsqueda sea O( log n) . ^{[ 1 ]}

Inserción

Al insertar un nodo x en un árbol zip, primero genere un nuevo rango a partir de una distribución geométrica con una probabilidad de éxito de 1/2. Sea x.key la clave del nodo x , y sea x.rank el rango del nodo x .

Luego, siga la ruta de búsqueda de x en el árbol hasta encontrar un nodo u tal que u.rank <= x.rank y u.key < x.key . Continúe la búsqueda de x , "descomprimiendo" cada nodo v encontrado, colocándolo en la ruta P si v.key < x.key , o en la ruta Q si v.key > x.key . Las claves deben ser únicas, por lo que si en algún momento v.key = x.key , la búsqueda se detiene y no se inserta ningún nodo nuevo.

Una vez completada la búsqueda de x , este se inserta en lugar del nodo u. El nodo superior del camino P se convierte en el hijo izquierdo de x , y el nodo superior de Q se convierte en el hijo derecho. Los punteros padre e hijo entre u y u.parent se actualizan según corresponda con x , y si u era previamente el nodo raíz, x se convierte en la nueva raíz.

Supresión

Al eliminar un nodo x , primero se busca en el árbol para encontrarlo. Si no se encuentra ningún nodo con la misma clave que x.key , no se realiza ninguna eliminación.

Una vez encontrado x , se realizan dos búsquedas descendentes en los subárboles izquierdo y derecho de x , combinando la rama derecha del subárbol izquierdo y la rama izquierda del subárbol derecho en una ruta R en orden descendente según su rango. Al crear esta ruta de arriba hacia abajo, los nodos se agregan como hijos izquierdo y derecho de su padre según sus claves.

Una vez que se completa la ruta R , la raíz de la ruta reemplazará a x . Los punteros padre e hijo entre x y x.padre se actualizan en consecuencia, y si x era anteriormente el nodo raíz, el nodo superior de R es la nueva raíz.

Referencias

1 2 Tarjan, Robert E.; Levy, Caleb C.; Timmel, Stephen (31-10-2021). "Árboles Zip". ACM Transactions on Algorithms . 17 (4): 1– 12. arXiv : 1806.06726 . doi : 10.1145/3476830 . ISSN 1549-6325 .
↑ Gila, Ofek; Goodrich, Michael T.; Tarjan, Robert E. (2023). "Árboles Zip-Zip: Cómo hacer que los árboles Zip sean más equilibrados, sesgados, compactos o persistentes". En Morin, Pat; Suri, Subhash (eds.). Algoritmos y estructuras de datos . Notas de clase en ciencias de la computación. Vol. 14079. Cham: Springer Nature Suiza. pp. 474–492 . arXiv : 2307.07660 . doi : 10.1007/978-3-031-38906-1_31 . ISBN 978-3-031-38906-1.

[:0-1] 1 2 Tarjan, Robert E.; Levy, Caleb C.; Timmel, Stephen (31-10-2021). "Árboles Zip". ACM Transactions on Algorithms . 17 (4): 1– 12. arXiv : 1806.06726 . doi : 10.1145/3476830 . ISSN 1549-6325 .

[2] Gila, Ofek; Goodrich, Michael T.; Tarjan, Robert E. (2023). "Árboles Zip-Zip: Cómo hacer que los árboles Zip sean más equilibrados, sesgados, compactos o persistentes". En Morin, Pat; Suri, Subhash (eds.). Algoritmos y estructuras de datos . Notas de clase en ciencias de la computación. Vol. 14079. Cham: Springer Nature Suiza. pp. 474–492 . arXiv : 2307.07660 . doi : 10.1007/978-3-031-38906-1_31 . ISBN 978-3-031-38906-1.

[ 2 ]