En informática , un árbol izquierdista o montón izquierdista 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 con raíz en x. [1] A diferencia de un montón binario , un árbol izquierdista intenta ser muy desequilibrado. Además de la propiedad del montón , los árboles izquierdistas se mantienen de modo que el descendiente derecho de cada nodo tenga el valor s más bajo.
El árbol izquierdista con sesgo de altura 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 izquierdista 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 lo reemplaza fusionando sus subárboles izquierdo y derecho. Ambas operaciones toman un tiempo de O(log n ). Para las inserciones, esto es más lento que los montones de Fibonacci , que admiten la inserción en un tiempo amortizado O(1) (constante) y O(log n ) en el peor de los casos.
Los árboles izquierdistas son ventajosos debido a su capacidad de fusionarse rápidamente, en comparación con los montículos binarios que toman Θ( n ). En casi todos los casos, la fusión de montículos sesgados tiene un mejor rendimiento. Sin embargo, la fusión de montículos izquierdistas tiene una complejidad O(log n ) en el peor de los casos, mientras que la fusión de montículos sesgados solo ha amortizado la complejidad O(log n ).
El árbol izquierdista habitual es un árbol izquierdista sesgado por la altura . [2] Sin embargo, pueden existir otros sesgos, como en el árbol izquierdista sesgado por el peso . [3]
El valor s (o rango ) de un nodo es la distancia desde ese nodo hasta la posición vacía más cercana en el subárbol con raíz en ese nodo. Dicho de otra manera, el valor s de un nullhijo 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 faltante 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 con raíz en x es exactamente s ( x ), cada nodo con una profundidad s ( x )−1 o menor tiene exactamente 2 hijos ya que s ( x ) habría sido menor si no lo fuera. Lo que significa que el tamaño del árbol con raíz en x es al menos . Por lo tanto, s ( x ) es como máximo , siendo m el número de nodos del subárbol con raíz en x . [1]
La mayoría de las operaciones en un árbol izquierdista con sesgo de altura se realizan mediante la operación de fusión. [1]
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 uno de A o B está vacío, la fusión devuelve el otro.
En el caso de Min HBLT, supongamos que tenemos dos árboles con raíces en A y B, donde A.key es B.key. De lo contrario, podemos intercambiar A y B para que se cumpla la condición anterior.
La fusión se realiza de forma recursiva fusionando B con el subárbol derecho de A. Esto puede cambiar el valor S del subárbol derecho de A. Para mantener la propiedad del árbol izquierdista, después de cada fusión, verificamos si el valor S del subárbol derecho se volvió 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 hijo, debería ser el derecho).
Como asumimos que la raíz de A es mayor que la de B, la propiedad del montón también se mantiene.
MERGE(A, B) si A = nulo devuelve B si B = nulo devuelve A si A.key > B.key devuelve MERGE(B, A) A.derecha := MERGE (A.derecha, B) // el resultado no puede ser nulo ya que B no es nulo si A.izquierda = nulo 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_valor := A.derecho.s_valor + 1 devolver A
public Nodo merge ( Nodo x , Nodo y ) { si ( x == null ) devuelve y ; si ( y == null ) devuelve x ; // si esto fuera un montón máximo, entonces la siguiente línea sería: if (x.element < y.element) if ( x . element . compareTo ( y . element ) > 0 ) // x.element > y.element return merge ( y , x ); x . rightChild = merge ( x . rightChild , y ); if ( x . leftChild == null ) { // el hijo izquierdo no existe, por lo que mueve el hijo derecho al lado izquierdo x . leftChild = x . rightChild ; x . rightChild = null ; // xs era, y sigue siendo, 1 } else { // el hijo izquierdo existe, por lo que compara los valores s if ( x . leftChild . s < x . rightChild . s ) { Nodo temp = x . leftChild ; x . leftChild = x . rightChild ; x . rightChild = temp ; } // como sabemos que el hijo derecho tiene el valor s más bajo, podemos simplemente // sumar uno a su valor s x . s = x . rightChild . s + 1 ; } return x ; } datos LHeap a = Hoja | Nodo a ( LHeap a ) ( LHeap a ) rango :: LHeap a -> Entero rango Hoja = 0 rango ( Nodo _ _ r ) = rango r + 1 fusionar :: Ord a => LHeap a -> LHeap a -> LHeap a fusionar Hoja h = h fusionar h Hoja = h fusionar h @ ( Nodo a l r ) h' @ ( Nodo a' _ _ ) | a > a' = fusionar h' h | rango r' > rango l = Nodo a r' l | de lo contrario = Nodo a l r' donde r' = fusionar r h' Se muestra un ejemplo de cómo funciona la operación de fusión en un árbol de izquierdas. Los cuadros representan cada llamada de fusión.
Cuando se desenrolla la recursión, 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 con raíz en los nodos con claves 7 y 10.
La inserción se realiza mediante la operación de fusión. La inserción de un nodo en un nodo ya existente
Min HBLT, crea un árbol HBLT de tamaño uno con ese nodo y lo fusiona con el árbol existente.
INSERTAR ( A , x ) B := CREAR_ARBOL( x ) devolver FUSIONAR( A , B )
El elemento Min de un HBLT Min es la raíz. Por lo tanto, para eliminar el Min, se elimina la raíz y se fusionan sus subárboles para formar el nuevo HBLT Min.
DELETE_MIN( A ) x := A .key A := MERGE ( A .right, A .left) devolver x
La inicialización de un árbol izquierdista con sesgo de altura se realiza principalmente de una de dos maneras. La primera es fusionar cada nodo de a uno por vez en un HBLT. Este proceso es ineficiente y lleva un tiempo de O( nlogn ). El otro enfoque es utilizar una cola para almacenar cada nodo y el árbol resultante. Los dos primeros elementos de la cola se eliminan, se fusionan y se vuelven a colocar en la cola. Esto puede inicializar un HBLT en un tiempo de O( n ). Este enfoque se detalla en los tres diagramas proporcionados. Se muestra un árbol izquierdista con sesgo de altura mínima.
Para inicializar un HBLT min, coloque cada elemento que se agregará al árbol en una cola. En el ejemplo (consulte 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 muestra 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, se produce la primera ocurrencia de un valor s mayor que 1. El sexto paso muestra dos árboles fusionados entre sí, con resultados predecibles.
En la segunda parte se produce 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 a la fusión nuevamente en el subárbol cuya raíz es 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 se deben intercambiar. El valor s del nodo raíz 4 también es ahora 2.
La parte 3 es la más compleja. Aquí, llamamos a merge de forma recursiva dos veces (cada vez con el subárbol del hijo correcto que no está en gris). Esto utiliza el mismo proceso descrito para la parte 2.
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 izquierdista.
El recorrido ascendente continúa hasta que llegamos a la raíz o el valor s no cambia. Dado que estamos eliminando un elemento, los valores s en la ruta recorrida no se pueden aumentar. Todos los nodos que ya son hijos derechos de su padre y hacen que el valor s de su padre disminuya, permanecerán a la derecha. Todos los nodos que son hijos izquierdos de su padre y hacen que el valor s de su padre disminuya deben intercambiarse con su hermano derecho si el valor s se vuelve menor que el valor s actual del hijo derecho.
Cada nodo debe tener un puntero a su padre, para 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 con raíz 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 con raíz en y. Por lo tanto, esta operación también requiere O(lg m) para realizarse.
Los árboles izquierdistas también pueden tener sesgo de ponderación. En este caso, en lugar de almacenar valores s en el nodo x, almacenamos un atributo w( x ) que denota la cantidad de nodos en el subárbol con raíz en x :
w( x ) = w( x .derecha) + w( x .izquierda) + 1
Las WBLT garantizan que w(x.left) ≥ w(x.right) para todos los nodos internos x. Las operaciones WBLT garantizan esta invariancia intercambiando los hijos de un nodo cuando el subárbol derecho supera al izquierdo, tal como en las operaciones HBLT.
La operación de fusión en WBLT se puede realizar mediante un único recorrido de arriba a abajo, ya que el número de nodos en los subárboles se conoce antes de la llamada recursiva para la fusión. Por lo tanto, podemos intercambiar los subárboles izquierdo y derecho si el número total de nodos en el subárbol derecho y el árbol que se va a fusionar es mayor que el número de nodos en el subárbol izquierdo. Esto permite que las operaciones se completen en una única ruta y, por lo tanto, mejora la complejidad temporal de las operaciones en un factor constante.
La operación de fusión se representa en el gráfico siguiente.
Las inserciones y eliminaciones del elemento min se pueden realizar de la misma manera que para los HBLT utilizando la operación de fusión.
Aunque los WBLT superan a los HBLT en la fusión, inserción y eliminación de la clave Min por un factor constante, el límite O (log n ) no está garantizado al eliminar un elemento arbitrario de los WBLT, ya que se deben atravesar θ( n ) nodos.
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 hasta la raíz, lo que toma O ( n ) en el peor de los casos.
Existen varias variaciones del árbol izquierdista básico, que solo realizan cambios menores en el algoritmo básico:
