En informática , un árbol de izquierda o un montón de izquierdas es una cola de prioridad implementada con una variante de un montón binario . Cada nodo x tiene un valor s que es la distancia a la hoja más cercana en el subárbol enraizado en x. [1] En contraste con un montón binario , un árbol de izquierda intenta estar muy desequilibrado. Además de la propiedad del montón , los árboles de la izquierda se mantienen para que el descendiente derecho de cada nodo tenga el valor s más bajo.
El árbol izquierdista de altura sesgada fue inventado por Clark Allan Crane . [2] El nombre proviene del hecho de que el subárbol izquierdo suele ser más alto que el subárbol derecho.
Un árbol de izquierda es un montón fusionable . Al insertar un nuevo nodo en un árbol, se crea un nuevo árbol de un nodo y se fusiona con el árbol existente. Para eliminar un elemento, se reemplaza por la combinación de sus subárboles izquierdo y derecho. Ambas operaciones toman O (log n ) tiempo. Para las inserciones, esto es más lento que los montones de Fibonacci , que admiten la inserción en el tiempo amortizado O (1) (constante) y O (log n ) en el peor de los casos.
Los árboles de izquierda son ventajosos debido a su capacidad para fusionarse rápidamente, en comparación con los montones binarios que toman Θ ( n ). En casi todos los casos, la combinación de montones sesgados tiene un mejor rendimiento. Sin embargo, fusionar montones izquierdistas tiene una complejidad O (log n ) en el peor de los casos, mientras que fusionar montones sesgados solo ha amortizado la complejidad O (log n ).
Parcialidad
El árbol de izquierda habitual es un árbol de izquierda sesgado por la altura . [2] Sin embargo, pueden existir otros sesgos, como en el árbol izquierdista sesgado por el peso . [3]
Valor S
El valor s (o rango ) de un nodo es la distancia desde ese nodo hasta la hoja más cercana en el subárbol enraizado en ese nodo. Dicho de otra manera, el valor s de un null
niño es implícitamente cero. Otros nodos tienen un valor s igual a uno más el mínimo de los valores s de sus hijos. Por lo tanto, en el ejemplo de la derecha, todos los nodos con al menos un hijo perdido tienen un valor s de 1, mientras que el nodo 4 tiene un valor s de 2, ya que su hijo derecho (8) tiene un valor s de 1. (En algunas descripciones, se supone que el valor s de los hijos nulos es -1. [4] )
Sabiendo que el camino más corto a la hoja faltante más cercana en el subárbol enraizado en x es exactamente de s ( x ), cada nodo a la profundidad s ( x ) −1 o menos tiene exactamente 2 hijos ya que s ( x ) habría sido menor si no . Lo que significa que el tamaño del árbol enraizado en x es al menos. Por lo tanto, s ( x ) es como máximo, siendo m el número de nodos del subárbol enraizados en x . [1]
Operaciones en un árbol izquierdista con sesgo de altura [1]
La mayoría de las operaciones en un árbol izquierdista con sesgo de altura se realizan mediante la operación de combinación.
Fusión de dos HBLT mínimos
La operación de fusión toma dos Min HBLT como entrada y devuelve un Min HBLT que contiene todos los nodos en los Min HBLT originales juntos.
Si cualquiera de A o B está vacío, la combinación devuelve el otro.
En el caso de Min HBLT, suponga que tenemos dos árboles enraizados en A y B donde A. clave B.key. De lo contrario, podemos intercambiar A y B para que se mantenga la condición anterior.
La fusión se realiza de forma recursiva fusionando B con el subárbol derecho de A. Esto podría cambiar el valor S del subárbol derecho de A. Para mantener la propiedad del árbol de la izquierda, después de que se realiza cada fusión, verificamos si el valor S del subárbol derecho se hizo más grande que el valor S del subárbol izquierdo durante las llamadas de fusión recursivas. Si es así, intercambiamos los subárboles derecho e izquierdo (si falta un niño, debería ser el derecho).
Dado que asumimos que la raíz de A es mayor que la de B, la propiedad del montón también se mantiene.
Pseudocódigo para fusionar dos árboles izquierdistas con sesgo de altura mínima
MERGE (A, B) si A = nulo devuelve B si B = nulo devuelve A si A.key> B.key entonces INTERCAMBIAR (A, B) A.right: = MERGE (A.right, B) // el resultado no puede ser nulo ya que B no es nulo si A.left = null entonces SWAP (A. izquierda, A. derecha) A.s_value: = 1 // dado que el subárbol derecho es nulo, la ruta más corta a una hoja descendiente del nodo A es 1 devuelve A si A.right.s_value> A.left.s_value entonces SWAP (A. derecha, A. izquierda) A.s_value: = A.right.s_value + 1 volver A
Código Java para fusionar dos árboles izquierdistas con sesgo de altura mínima
fusión de nodo público ( nodo x , nodo y ) { if ( x == null ) return y ; si ( y == nulo ) devuelve x ; // si este fuera un montón máximo, entonces la // siguiente línea sería: if (x.element )> if ( x . element . compareTo ( y . element ) > 0 ) { // x.element > y.element Node temp = x ; x = y ; y = temp ; } x . niño derecho = fusionar ( x . niño derecho , y ); if ( x . leftChild == null ) { // el hijo izquierdo no existe, así que mueva el hijo derecho al lado izquierdo x . leftChild = x . rightChild ; x . niño derecho = nulo ; // xs era, y sigue siendo, 1 } else { // el hijo izquierdo existe, así que compare los valores s if ( x . hijo izquierdo . s < x . hijo derecho . s ) { Node temp = x . leftChild ; x . leftChild = x . rightChild ; x . rightChild = temp ; } // ya que sabemos que el hijo correcto tiene el valor s más bajo, podemos simplemente // agregar uno a su valor s x . s = x . rightChild . s + 1 ; } return x ; }
Ejemplo
Se representa un ejemplo de cómo funciona la operación de fusión en un árbol de izquierda. Los cuadros representan cada llamada de combinación.
Cuando la recursividad se desenvuelve, intercambiamos los hijos izquierdo y derecho si x.right.s_value> x.left.s_value para cada nodo x. En este caso, intercambiamos los subárboles arraigados en los nodos con las claves 7 y 10.
Inserción en un Min HBLT
La inserción se realiza mediante la operación de combinación. Una inserción de un nodo en un ya existente
Min HBLT, crea un árbol HBLT de tamaño uno con ese nodo y lo fusiona con el árbol existente.
INSERT ( A , x ) B : = CREATE_TREE ( x ) return FUSION ( A , B )
Eliminación del elemento Min de Min HBLT
El elemento Min en un Min HBLT es la raíz. Por lo tanto, para eliminar el Min, se elimina la raíz y sus subárboles se fusionan para formar el nuevo Min HBLT.
DELETE_MIN ( A ) x : = A .key A : = FUSION ( A .derecha, A .izquierda) return x
Inicializando un árbol izquierdista con sesgo de altura
La inicialización de un árbol de izquierda con sesgo de altura se realiza principalmente de dos maneras. El primero es fusionar cada nodo de uno en uno en un HBLT. Este proceso es ineficaz y lleva O ( nlogn ) tiempo. El otro enfoque es utilizar una cola para almacenar cada nodo y el árbol resultante. Los dos primeros elementos de la cola se eliminan, combinan y vuelven a colocar en la cola. Esto puede inicializar un HBLT en tiempo O ( n ). Este enfoque se detalla en los tres diagramas suministrados. Se muestra un árbol izquierdista sesgado de altura mínima.
Para inicializar un HBLT mínimo, coloque cada elemento que se agregará al árbol en una cola. En el ejemplo (vea la Parte 1 a la izquierda), se inicializa el conjunto de números [4, 8, 10, 9, 1, 3, 5, 6, 11]. Cada línea del diagrama representa otro ciclo del algoritmo, que describe el contenido de la cola. Los primeros cinco pasos son fáciles de seguir. Observe que el HBLT recién creado se agrega al final de la cola. En el quinto paso, ocurre la primera aparición de un valor s mayor que 1. El sexto paso muestra dos árboles fusionados entre sí, con resultados predecibles.
En la parte 2 ocurre una fusión un poco más compleja. El árbol con el valor más bajo (árbol x) tiene un hijo derecho, por lo que se debe llamar nuevamente a la combinación en el subárbol enraizado por el hijo derecho del árbol x y el otro árbol. Después de la fusión con el subárbol, el árbol resultante se vuelve a colocar en el árbol x. El valor s del hijo derecho (s = 2) ahora es mayor que el valor s del hijo izquierdo (s = 1), por lo que deben intercambiarse. El valor s del nodo raíz 4 también es ahora 2.
La tercera parte es la más compleja. Aquí, llamamos recursivamente a merge dos veces (cada vez con el subárbol del niño correcto que no está atenuado). Esto usa el mismo proceso descrito para la parte 2.
Eliminación de un elemento arbitrario de un Min HBLT
Si tenemos un puntero a un nodo x en un Min HBLT, podemos eliminarlo de la siguiente manera: Reemplazar el nodo x con el resultado de fusionar sus dos subárboles y actualizar los valores s de los nodos en la ruta de x a la raíz. , intercambiando los subárboles derecho e izquierdo si es necesario para mantener la propiedad del árbol de izquierda.
El recorrido ascendente continúa hasta que llegamos a la raíz o los valores de s no cambian. Dado que estamos eliminando un elemento, los valores S en la ruta recorrida no se pueden aumentar. Cada nodo que ya sea el hijo correcto de su padre y haga que el valor s de su padre disminuya, permanecerá a la derecha. Cada nodo que es el hijo izquierdo de su padre y hace que el valor s del padre disminuya debe intercambiarse con su hermano derecho si el valor s se vuelve más bajo que el valor s actual del hijo derecho.
Cada nodo debe tener un puntero a su padre, de modo que podamos recorrer la ruta a la raíz actualizando los valores s.
Cuando el recorrido termina en algún nodo y, todos los nodos atravesados se encuentran en el camino más a la derecha enraizado en el nodo y. A continuación se muestra un ejemplo. De ello se deduce que el número de nodos atravesados es como máximo log (m), siendo m el tamaño del subárbol enraizado en y. Por lo tanto, esta operación también requiere O (lg m) para realizarse.
Árbol izquierdista con sesgo de peso [5]
Los árboles de izquierda también pueden estar sesgados por el peso. En este caso, en lugar de almacenar valores de s en el nodo x, almacenamos un atributo w ( x ) que denota el número de nodos en el subárbol enraizado en x :
w ( x ) = w ( x .derecha) + w ( x .izquierda) + 1
Los WBLT garantizan w (x.left) ≥ w (x.right) para todos los nodos internos x. Las operaciones WBLT aseguran este invariante intercambiando los hijos de un nodo cuando el subárbol derecho supera al izquierdo, al igual que en las operaciones HBLT.
Fusión de dos WBLT mín.
La operación de fusión en WBLT se puede realizar utilizando un solo recorrido de arriba a abajo, ya que el número de nodos en los subárboles se conoce antes de la llamada recursiva para fusionar. Por lo tanto, podemos intercambiar subárboles izquierdo y derecho si el número total de nodos en el subárbol derecho y el árbol que se fusionará es mayor que el número de nodos en el subárbol izquierdo. Esto permite que las operaciones se completen en una sola ruta y así mejora la complejidad temporal de las operaciones en un factor constante.
La operación de combinación se muestra en el gráfico siguiente.
Otras operaciones en WBLT
Las inserciones y la eliminación del elemento min se pueden realizar de la misma manera que para los HBLT utilizando la operación de combinación.
Aunque los WBLT superan a los HBLT en combinación, inserción y eliminación de la clave Min por un factor constante, el límite O (log n ) no está garantizado cuando se elimina un elemento arbitrario de los WBLT, ya que θ ( n ) nodos deben atravesarse.
Si esto fuera un HBLT, entonces eliminar el nodo hoja con la clave 60 tomaría O (1) tiempo y no es necesario actualizar los valores s, ya que la longitud de la ruta más a la derecha para todos los nodos no cambia.
Pero en un árbol WBLT, tenemos que actualizar el peso de cada nodo a la raíz, lo que toma O ( n ) en el peor de los casos.
Variantes
Existen varias variaciones en el árbol izquierdista básico, que hacen solo cambios menores al algoritmo básico:
- La elección del niño izquierdo como el más alto es arbitraria; un "árbol de derecha" funcionaría igual de bien.
- Es posible evitar intercambiar hijos, pero en su lugar registrar qué hijo es el más alto (en, por ejemplo, el bit menos significativo del valor s) y usarlo en la operación de combinación.
- El valor s usado para decidir con qué lado fusionarse podría usar una métrica diferente a la altura. Por ejemplo, se podría usar el peso (número de nodos).
Referencias
- ^ a b c "Árboles de izquierda" (PDF) . www.google.com . Consultado el 31 de mayo de 2019 .
- ^ a b Crane, Clark A. (1972), Listas lineales y colas de prioridad como árboles binarios equilibrados (tesis doctoral), Departamento de Ciencias de la Computación, Universidad de Stanford, ISBN 0-8240-4407-X, STAN-CS-72-259
- ^ Seonghun Cho; Sartaj Sahni (1996), "Árboles izquierdistas con sesgo de peso y listas de omisión modificadas" (PDF) , Journal of Experimental Algorithmics , 3 , CiteSeerX 10.1.1.13.2962 , doi : 10.1145 / 297096.297111
- ^ Stewart, James (25 de septiembre de 1988). "ÁRBOLES IZQUIERDOS" . Proyecto de gráficos dinámicos de la Universidad de Toronto . Consultado el 31 de mayo de 2019 .
- ^ Cho, Seonghun; Sahni, Sartaj (septiembre de 1998). "Árboles izquierdistas con sesgo de peso y listas de omisión modificadas" . J. Exp. Algoritmos . 3 . doi : 10.1145 / 297096.297111 . ISSN 1084-6654 .
Otras lecturas
- Robert E. Tarjan (1983). Estructuras de datos y algoritmos de red . SIAM. págs. 38–42. ISBN 978-0-89871-187-5.
- Dinesh P. Mehta; Sartaj Sahni (28 de octubre de 2004). "Capítulo 5: árboles de izquierda" . Manual de estructuras y aplicaciones de datos . Prensa CRC. ISBN 978-1-4200-3517-9.
enlaces externos
- Árboles de izquierda , Sartaj Sahni