En informática , un árbol de chivo expiatorio es un árbol de búsqueda binario autoequilibrado , inventado por Arne Andersson [1] y nuevamente por Igal Galperin y Ronald L. Rivest . [2] que proporciona peor caso O (log n ) tiempo de búsqueda, y O (log n ) amortizados tiempo de inserción y deleción.
Árbol de chivo expiatorio | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | árbol | ||||||||||||||||||||
Inventado por | Arne Andersson , Igal Galperin y Ronald L. Rivest | ||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||
|
A diferencia de la mayoría de los otros árboles de búsqueda binarios autoequilibrados que proporcionan el peor tiempo de búsqueda de O (log n ), los árboles chivos expiatorios no tienen una sobrecarga adicional de memoria por nodo en comparación con un árbol de búsqueda binario normal : un nodo almacena solo una clave y dos punteros al nodos secundarios. Esto hace que los árboles de chivos expiatorios sean más fáciles de implementar y, debido a la alineación de la estructura de datos , puede reducir la sobrecarga del nodo hasta en un tercio.
En lugar de las pequeñas operaciones de reequilibrio incremental utilizadas por la mayoría de los algoritmos de árbol equilibrado, los árboles chivos expiatorios rara vez, pero de forma costosa, eligen un "chivo expiatorio" y reconstruyen por completo el subárbol enraizado en el chivo expiatorio en un árbol binario completo. Por lo tanto, los árboles de chivo expiatorio tienen O ( n ) rendimiento de actualización en el peor de los casos.
Teoría
Se dice que un árbol de búsqueda binario está equilibrado por peso si la mitad de los nodos están a la izquierda de la raíz y la mitad a la derecha. Un nodo con equilibrio de peso α se define como el que cumple un criterio de equilibrio de peso relajado:
tamaño (izquierda) ≤ α * tamaño (nodo)tamaño (derecha) ≤ α * tamaño (nodo)
Donde el tamaño se puede definir de forma recursiva como:
el tamaño de la función (nodo) es si nodo = nil, luego devuelve 0; de lo contrario, devuelve el tamaño (nodo-> izquierda) + tamaño (nodo-> derecha) + 1 fin si finaliza la función
Incluso un árbol degenerado (lista enlazada) satisface esta condición si α = 1, mientras que un α = 0.5 solo coincidiría con árboles binarios casi completos .
Un árbol de búsqueda binario con equilibrio de peso α también debe tener equilibrio de altura α , es decir
altura (árbol) ≤ ⌊log 1 / α (tamaño (árbol)) ⌋
Por contraposición , un árbol que no está equilibrado en altura α no está equilibrado en peso α.
No se garantiza que los árboles de chivo expiatorio mantengan el equilibrio de peso α en todo momento, pero siempre tienen un equilibrio de altura α débil en ese sentido.
altura (árbol de chivo expiatorio) ≤ ⌊log 1 / α (tamaño (árbol)) ⌋ + 1.
Las infracciones de esta condición de equilibrio de altura se pueden detectar en el momento de la inserción e implican que debe existir una infracción de la condición de equilibrio de peso.
Esto hace que los árboles chivos expiatorios sean similares a los árboles rojo-negros en el sentido de que ambos tienen restricciones en su altura. Sin embargo, difieren mucho en sus implementaciones para determinar dónde tienen lugar las rotaciones (o en el caso de los árboles chivos expiatorios, los reequilibrios). Mientras que los árboles rojo-negro almacenan información de 'color' adicional en cada nodo para determinar la ubicación, los árboles chivos expiatorios encuentran un chivo expiatorio que no tiene un equilibrio de peso α para realizar la operación de reequilibrio. Esto es ligeramente similar a los árboles AVL , en el sentido de que las rotaciones reales dependen de los "saldos" de los nodos, pero los medios para determinar el equilibrio difieren mucho. Dado que los árboles AVL verifican el valor del saldo en cada inserción / eliminación, generalmente se almacena en cada nodo; Los árboles de chivos expiatorios pueden calcularlo solo según sea necesario, que es solo cuando es necesario encontrar un chivo expiatorio.
A diferencia de la mayoría de los otros árboles de búsqueda de autoequilibrio, los árboles de chivos expiatorios son completamente flexibles en cuanto a su equilibrio. Admiten cualquier α tal que 0.5 <α <1. Un valor α alto da como resultado menos saldos, lo que hace que la inserción sea más rápida pero las búsquedas y eliminaciones más lentas, y viceversa para un α bajo. Por lo tanto, en aplicaciones prácticas, se puede elegir un α dependiendo de la frecuencia con la que se deben realizar estas acciones.
Operaciones
Buscar
La búsqueda no se modifica a partir de un árbol de búsqueda binario estándar y tiene un tiempo en el peor de los casos de O (log n ). Esto contrasta con los árboles esparcidos que tienen un tiempo de O ( n ) en el peor de los casos . La sobrecarga de memoria de nodo reducida en comparación con otros árboles de búsqueda binarios de autoequilibrio puede mejorar aún más la localidad de referencia y almacenamiento en caché.
Inserción
La inserción se implementa con las mismas ideas básicas que un árbol de búsqueda binario no balanceado , pero con algunos cambios significativos.
Al encontrar el punto de inserción, también se debe registrar la profundidad del nuevo nodo. Esto se implementa a través de un contador simple que se incrementa durante cada iteración de la búsqueda, contando efectivamente el número de bordes entre la raíz y el nodo insertado. Si este nodo viola la propiedad de equilibrio de altura α (definida anteriormente), se requiere un reequilibrio.
Para reequilibrar, todo un subárbol enraizado en un chivo expiatorio se somete a una operación de equilibrio. El chivo expiatorio se define como un antepasado del nodo insertado que no tiene un equilibrio de peso α. Siempre habrá al menos uno de esos antepasados. Reequilibrar cualquiera de ellos restaurará la propiedad de equilibrio de altura α.
Una forma de encontrar un chivo expiatorio es escalar desde el nuevo nodo hasta la raíz y seleccionar el primer nodo que no tiene un equilibrio de peso α.
Volver a subir a la raíz requiere O (log n ) espacio de almacenamiento, generalmente asignado en la pila, o punteros principales. En realidad, esto se puede evitar señalando a cada niño a su padre a medida que baja y reparando en la caminata de regreso.
Para determinar si un nodo potencial es un chivo expiatorio viable, debemos verificar su propiedad de equilibrio de peso α. Para hacer esto podemos volver a la definición:
tamaño (izquierda) ≤ α * tamaño (nodo)tamaño (derecha) ≤ α * tamaño (nodo)
Sin embargo, se puede hacer una gran optimización al darse cuenta de que ya conocemos dos de los tres tamaños, dejando solo el tercero por calcular.
Considere el siguiente ejemplo para demostrarlo. Suponiendo que volvemos a subir a la raíz:
tamaño (padre) = tamaño (nodo) + tamaño (hermano) + 1
Pero como:
tamaño (nodo insertado) = 1.
El caso se trivializa hasta:
tamaño [x + 1] = tamaño [x] + tamaño (hermano) + 1
Donde x = este nodo, x + 1 = padre y tamaño (hermano) es la única llamada de función realmente necesaria.
Una vez que se encuentra el chivo expiatorio, el subárbol enraizado en el chivo expiatorio se reconstruye por completo para que esté perfectamente equilibrado. [2] Esto se puede hacer en O ( n ) tiempo atravesando los nodos del subárbol para encontrar sus valores en orden ordenado y eligiendo recursivamente la mediana como la raíz del subárbol.
Como las operaciones de reequilibrio toman O ( n ) tiempo (dependiendo del número de nodos del subárbol), la inserción tiene un desempeño en el peor de los casos de O ( n ) tiempo. Sin embargo, debido a que estos escenarios del peor de los casos están dispersos, la inserción lleva O (log n ) tiempo de amortización.
Boceto de prueba para costo de inserción
Defina el desequilibrio de un nodo v como el valor absoluto de la diferencia de tamaño entre su nodo izquierdo y el nodo derecho menos 1, o 0, el que sea mayor. En otras palabras:
Inmediatamente después de reconstruir un subárbol con raíz en v , I ( v ) = 0.
Lema: Inmediatamente antes de reconstruir el subárbol con raíz en v ,
(es la gran notación Omega ).
Prueba de lema:
Dejar ser la raíz de un subárbol inmediatamente después de la reconstrucción. . Si hay inserciones degeneradas (es decir, donde cada nodo insertado aumenta la altura en 1), luego
,
y
.
Desde antes de la reconstrucción, hubo inserciones en el subárbol enraizado en eso no resultó en la reconstrucción. Cada una de estas inserciones se puede realizar enhora. La inserción final que genera costos de reconstrucción.. Al usar el análisis agregado , queda claro que el costo amortizado de una inserción es:
Supresión
Los árboles de chivo expiatorio son inusuales en el sentido de que la eliminación es más fácil que la inserción. Para habilitar la eliminación, los árboles de chivos expiatorios deben almacenar un valor adicional con la estructura de datos del árbol. Esta propiedad, que llamaremos MaxNodeCount simplemente representa el NodeCount más alto alcanzado. Se establece en NodeCount siempre que se reequilibra todo el árbol y, después de la inserción, se establece en max (MaxNodeCount, NodeCount).
Para realizar una eliminación, simplemente eliminamos el nodo como lo haría en un árbol de búsqueda binario simple, pero si
NodeCount ≤ α * MaxNodeCount
luego reequilibramos todo el árbol sobre la raíz, recordando establecer MaxNodeCount en NodeCount.
Esto le da a la eliminación su desempeño en el peor de los casos de O ( n ) tiempo; sin embargo, se amortiza al tiempo promedio O (log n ).
Bosquejo de la prueba del costo de eliminación
Suponga que el árbol del chivo expiatorio tiene elementos y acaba de ser reconstruido (en otras palabras, es un árbol binario completo). A lo sumose pueden realizar eliminaciones antes de que se deba reconstruir el árbol. Cada una de estas eliminaciones tomatime (la cantidad de tiempo para buscar el elemento y marcarlo como eliminado). La la eliminación hace que el árbol sea reconstruido y toma (o solo ) hora. Al usar el análisis agregado, queda claro que el costo amortizado de una eliminación es:
Etimología
El nombre árbol del chivo expiatorio "[...] se basa en la sabiduría común de que, cuando algo sale mal, lo primero que la gente tiende a hacer es encontrar a alguien a quien culpar (el chivo expiatorio)". [3] En la Biblia , un chivo expiatorio es un animal que se carga ritualmente con los pecados de otros y luego se aleja.
Ver también
Referencias
- ^ Andersson, Arne (1989). Mejora de la reconstrucción parcial mediante el uso de criterios de equilibrio simples . Proc. Taller de Algoritmos y Estructuras de Datos. Revista de algoritmos . Springer-Verlag. págs. 393–402. CiteSeerX 10.1.1.138.4859 . doi : 10.1007 / 3-540-51542-9_33 .
- ^ a b Galperin, Igal; Rivest, Ronald L. (1993). Árboles de chivo expiatorio (PDF) . Actas del cuarto Simposio anual ACM-SIAM sobre algoritmos discretos . Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas . págs. 165-174. CiteSeerX 10.1.1.309.9376 . ISBN 0-89871-313-7.
- ^ Morin, Pat . "Capítulo 8 - Árboles de chivo expiatorio" . Estructuras de datos abiertas (en pseudocódigo) (0.1G β ed.) . Consultado el 16 de septiembre de 2017 .
enlaces externos
- Galpern, Igal (septiembre de 1996). Sobre la consulta de un conjunto de expertos y la búsqueda (PDF) (tesis doctoral). MIT .
- Morin, Pat. "Capítulo 8 - Árboles de chivo expiatorio" . Estructuras de datos abiertas (en pseudocódigo) (0.1G β ed.) . Consultado el 16 de septiembre de 2017 .