árbol izquierdista
En informática , un árbol de izquierda o un montón de izquierda 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 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 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 de izquierda es un montón combinable . 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 tiempo O(log n ). Para las inserciones, esto es más lento que los montones de Fibonacci , que admiten la inserción en O(1) (constante) tiempo amortizado y O(log n ) en el peor de los casos.
Los árboles izquierdistas 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, la combinación de montones izquierdistas tiene una complejidad de O (log n ) en el peor de los casos, mientras que la combinación de montones sesgados solo ha amortizado la complejidad de 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 con sesgo de peso . [3]
El valor s (o rango ) de un nodo es la distancia desde ese nodo hasta la hoja más cercana en el subárbol con raíz en ese nodo. Dicho de otra manera, el valor s de un nullniñ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 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 niños nulos es −1. [4] )
