Árbol del chivo expiatorio

En informática , un árbol chivo expiatorio es un árbol de búsqueda binaria autoequilibrado , inventado por Arne Andersson ^{[ 2 ]} en 1989 y nuevamente por Igal Galperin y Ronald L. Rivest en 1993. ^{[ 1 ]} Proporciona el peor caso ${\color {Blue}O(\log n)}$ tiempo de búsqueda (con $n$ como el número de entradas) y $O(\log n)$ tiempo amortizado de inserción y eliminación.

A diferencia de la mayoría de los demás árboles de búsqueda binaria autoequilibrados que también proporcionan el peor caso $O(\log n)$ En cuanto al tiempo de búsqueda, los árboles de chivo expiatorio no tienen un consumo de memoria adicional por nodo en comparación con un árbol de búsqueda binaria convencional : además de la clave y el valor, un nodo almacena solo dos punteros a los nodos hijos. Esto facilita la implementación de los árboles de chivo expiatorio y, gracias a la alineación de la estructura de datos , puede reducir el consumo de memoria de los nodos hasta en un tercio.

En lugar de las pequeñas operaciones de reequilibrio incremental utilizadas por la mayoría de los algoritmos de árboles equilibrados, los árboles de chivo expiatorio rara vez, pero de forma costosa, eligen un "chivo expiatorio" y reconstruyen completamente 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 binaria está equilibrado en peso si la mitad de los nodos se encuentran a la izquierda de la raíz y la otra mitad a la derecha. Un nodo α-equilibrado en peso se define como aquel 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 recursivamente como:

función tamaño(nodo) es si nodo = nil entonces devolver 0 sino devolver tamaño(nodo->izquierdo) + tamaño(nodo->derecho) + 1 fin si fin 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 binaria que está α-equilibrado en peso también debe estar α-equilibrado en altura , es decir

altura(árbol) ≤ piso(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 chivo expiatorios mantengan un equilibrio de peso α en todo momento, pero siempre están aproximadamente equilibrados en altura α en ese sentido.

altura(árbol chivo expiatorio) ≤ piso(log _1/α (tamaño(árbol))) + 1.

Las violaciones de esta condición de equilibrio de altura pueden detectarse en el momento de la inserción e implican que debe existir una violación de la condición de equilibrio de peso.

Esto hace que los árboles de chivo expiatorio sean similares a los árboles rojo-negro en el sentido de que ambos tienen restricciones en su altura. Sin embargo, difieren enormemente en sus implementaciones para determinar dónde tienen lugar las rotaciones (o, en el caso de los árboles de chivo expiatorio, los reequilibrios). Mientras que los árboles rojo-negro almacenan información adicional de "color" en cada nodo para determinar la ubicación, los árboles de chivo expiatorio encuentran un chivo expiatorio que no está equilibrado con peso α para realizar la operación de reequilibrio. Esto es vagamente similar a los árboles AVL , en el sentido de que las rotaciones reales dependen de los "equilibrios" de los nodos, pero los medios para determinar el equilibrio difieren enormemente. Dado que los árboles AVL comprueban el valor del equilibrio en cada inserción/eliminación, este se almacena normalmente en cada nodo; los árboles de chivo expiatorio pueden calcularlo solo cuando es necesario, es decir, solo cuando se necesita encontrar un chivo expiatorio.

A diferencia de la mayoría de los árboles de búsqueda autoequilibrados, los árboles de chivo expiatorio son totalmente flexibles en cuanto a su equilibrio. Admiten cualquier valor de α tal que 0,5 < α < 1. Un valor alto de α resulta en menos equilibrios, 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 valor bajo de α. Por lo tanto, en aplicaciones prácticas, se puede elegir un valor de α en función de la frecuencia con la que se deban realizar estas acciones.

Operaciones

Buscar

La búsqueda no se modifica a partir de un árbol de búsqueda binaria estándar y tiene un tiempo de caso peor de $O(\log n)$ Esto contrasta con los árboles splay , que tienen un tiempo de peor caso de $O(n)$ La menor sobrecarga de memoria de los nodos en comparación con otros árboles de búsqueda binaria autoequilibrados puede mejorar aún más la localidad de referencia y el almacenamiento en caché.

Inserción

La inserción se implementa con las mismas ideas básicas que un árbol de búsqueda binaria desequilibrado , 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 mediante un contador simple que se incrementa en cada iteración de la búsqueda, contando así el número de aristas entre la raíz y el nodo insertado. Si este nodo incumple la propiedad de equilibrio de altura α (definida anteriormente), se requiere un reequilibrio.

Para reequilibrar, todo un subárbol con raíz en un nodo chivo expiatorio se somete a una operación de equilibrio. El nodo chivo expiatorio se define como un ancestro del nodo insertado que no está equilibrado en peso α. Siempre habrá al menos un ancestro de este tipo. Reequilibrar cualquiera de ellos restaurará la propiedad de equilibrio en altura α.

Una forma de encontrar un chivo expiatorio es subir desde el nodo nuevo hasta la raíz y seleccionar el primer nodo que no esté equilibrado en peso α.

Volver a subir hasta la raíz requiere $O(\log n)$ Espacio de almacenamiento, generalmente asignado en la pila, o punteros al padre. Esto se puede evitar apuntando cada hijo a su padre al descender y reparándolo al ascender.

Para determinar si un nodo potencial es un chivo expiatorio viable, necesitamos verificar su propiedad de equilibrio de peso α. Para ello, podemos volver a la definición:

tamaño(izquierda) ≤ α*tamaño(nodo) tamaño(derecha) ≤ α*tamaño(nodo)

Sin embargo, se puede lograr una gran optimización al darnos cuenta de que ya conocemos dos de los tres tamaños, quedando solo por calcular el tercero.

Consideremos el siguiente ejemplo para demostrarlo. Suponiendo que estamos volviendo a subir hasta 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 llegar a:

tamaño[x+1] = tamaño[x] + tamaño(hermano) + 1

Donde x = este nodo, x + 1 = padre y size(hermano) es la única llamada a función realmente necesaria.

Una vez encontrado el chivo expiatorio, el subárbol enraizado en el chivo expiatorio se reconstruye por completo para que esté perfectamente equilibrado. ^{[ 1 ]} Esto se puede hacer en $O(n)$ El tiempo se calcula recorriendo los nodos del subárbol para encontrar sus valores en orden ascendente y eligiendo recursivamente la mediana como raíz del subárbol.

A medida que se llevan a cabo las operaciones de reequilibrio $O(n)$ tiempo (dependiendo del número de nodos del subárbol), la inserción tiene un rendimiento en el peor de los casos de $O(n)$ tiempo. Sin embargo, debido a que estos peores escenarios están espaciados, la inserción lleva $O(\log n)$ tiempo amortizado.

Bosquejo de demostración del costo de inserción

Los árboles chivo expiatorios tienen una altura ligeramente equilibrada, con una altura máxima de... $\lfloor \log _{1/\alpha }n\rfloor$ , que es $O(\log n)$ por 0,5 < α < 1. El costo de encontrar el punto de inserción y colocar el nodo está limitado por la altura, que es $O(\log n)$ . Tras la inserción, puede haber un reequilibrio que puede costar hasta $O(n)$ Ahora demostraremos que el costo del reequilibrio se amortiza. $O(\log n)$ por inserción.

Definimos el desequilibrio de un nodo v como el valor absoluto de la diferencia de tamaño entre su nodo izquierdo y su nodo derecho menos 1, o 0, lo que sea mayor. En otras palabras:

$I(v)=\operatorname {max} (|\operatorname {left} (v)-\operatorname {right} (v)|-1,0)$

Además, definimos el desequilibrio de un subárbol como la suma del desequilibrio de los nodos en el subárbol.

Lema 1: Inmediatamente antes de reconstruir el subárbol con raíz en $v$ , $I(v)\in \Omega (|v|)$ ( $\Omega$ es la notación Omega grande .)

Prueba:

Por definición, el nodo chivo expiatorio no está equilibrado en peso α, por lo tanto, un subárbol hijo tiene un tamaño al menos $\alpha |v|$ y el subárbol hermano tiene un tamaño como máximo $(1-\alpha )|v|$ . El desequilibrio del nodo $v$ es entonces $I(v)\geq |\alpha |v|-(1-\alpha )|v||-1=|2\alpha -1||v|-1$ y como $\alpha >0.5$ es una constante fija, $I(V)=\Omega (|V|)$ . Por lo tanto, el desequilibrio del subárbol enraizado en $v$ también lo es $\Omega (|V|)$ .

Lema 2: Inmediatamente después de reconstruir un subárbol con raíz en $v$ , $I(v)=0$ .

Prueba:

El árbol reconstruido está perfectamente equilibrado, de modo que el tamaño de los subárboles enraizados en el mismo nivel difiere como máximo en 1. Según la definición anterior de desequilibrio, el desequilibrio de todos los nodos en el subárbol es entonces 0.

Teorema 3: El costo amortizado de la inserción es $O(\log n)$ .

Prueba:

Como cualquier $O(|v|)$ La reconstrucción reduce $I(v)$ por $\Omega (|v|)-0=\Omega (|v|)$ Según los lemas 1 y 2, el costo de reparar cada unidad de desequilibrio es

${O(|v|) \over \Omega (|v|)}=O(1)$ .

Cada inserción puede introducir como máximo 1 unidad de desequilibrio en todos los subárboles que la contienen. El nodo insertado solo puede estar en como máximo 1 subárbol por nivel del árbol, lo que significa que el número de subárboles que lo incluyen está limitado por la altura del árbol, que es $O(\log n)$ . Como cada unidad de desequilibrio cuesta $O(1)$ para corregir, lo que resulta en un costo amortizado de reequilibrio por inserción inserción de

$O(\log n)O(1)=O(\log n)$ .

Al sumar los costos de la fase de búsqueda inicial y el reequilibrio, el costo amortizado de inserción es, por lo tanto,

$O(\log n)+O(\log n)=O(\log n)$ .

Este límite se cumple para todo 0,5 < α < 1.

Supresión

Los árboles de chivos expiatorios son inusuales porque su eliminación es más sencilla que su inserción. Para permitir la eliminación, los árboles de chivos expiatorios necesitan almacenar un valor adicional en la estructura de datos del árbol. Esta propiedad, que llamaremos MaxNodeCount, simplemente representa el NodeCount máximo alcanzado. Se establece en NodeCount cuando 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íamos en un árbol de búsqueda binaria simple, pero si

NodeCount ≤ α*MaxNodeCount

Luego reequilibramos todo el árbol alrededor de la raíz, recordando establecer MaxNodeCount en NodeCount.

Esto le da a la eliminación un rendimiento en el peor de los casos de $O(n)$ tiempo, mientras que el tiempo amortizado es $O(\log n)$ .

Bosquejo de prueba para el costo de eliminación

Supongamos que el árbol del chivo expiatorio tiene $n$ elementos y acaba de ser reconstruido (en otras palabras, es un árbol binario completo). Como máximo $n/2-1$ Las eliminaciones se pueden realizar antes de que sea necesario reconstruir el árbol. Cada una de estas eliminaciones toma $O(\log n)$ tiempo (el tiempo necesario para buscar el elemento y marcarlo como eliminado). $n/2$ La eliminación provoca que el árbol se reconstruya y toma $O(\log n)+O(n)$ (o simplemente $O(n)$ ) tiempo. Utilizando el análisis agregado, queda claro que el costo amortizado de una eliminación es $O(\log n)$ :

${\sum _{1}^{n/2}O(\log n)+O(n) \over n/2}={{n \over 2}O(\log n)+O(n) \over n/2}=O(\log n)\$

Etimología

El nombre Árbol del chivo expiatorio "[...] se basa en la sabiduría popular 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 es cargado ritualmente con los pecados de otros y luego expulsado.

Véase también

Referencias

1 2 3 4 5 6 7 Galperin, Igal; Rivest, Ronald L. (1993). Árboles de chivos expiatorios (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.
↑ Andersson, Arne (1989). Improving partial rebuilding by using simple balance criteria . Proc. Workshop on Algorithms and Data Structures. Journal of Algorithms . Springer-Verlag. pp. 393– 402. CiteSeerX 10.1.1.138.4859 . doi : 10.1007/3-540-51542-9_33 .
↑ Morin, Pat . "Capítulo 8 - Árboles de chivos expiatorios" . Estructuras de datos abiertos (en pseudocódigo) ( ed. β de 0,1 GB) . Consultado el 16 de septiembre de 2017 .

Enlaces externos

Galpern, Igal (septiembre de 1996). Sobre la consulta a un grupo de expertos y la búsqueda (PDF) (tesis doctoral). MIT .
Morin, Pat. "Capítulo 8 - Árboles de chivos expiatorios" . Estructuras de datos abiertas (en pseudocódigo) ( ed. β de 0,1 GB) . Consultado el 16 de septiembre de 2017 .

[galperin_rivest-1] 1 2 3 4 5 6 7 Galperin, Igal; Rivest, Ronald L. (1993). Árboles de chivos expiatorios (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.

[anderson1-2] Andersson, Arne (1989). Improving partial rebuilding by using simple balance criteria . Proc. Workshop on Algorithms and Data Structures. Journal of Algorithms . Springer-Verlag. pp. 393– 402. CiteSeerX 10.1.1.138.4859 . doi : 10.1007/3-540-51542-9_33 .

[opendatastructures-3] Morin, Pat . "Capítulo 8 - Árboles de chivos expiatorios" . Estructuras de datos abiertos (en pseudocódigo) ( ed. β de 0,1 GB) . Consultado el 16 de septiembre de 2017 .

[ 2 ]

[ 1 ]

[ 3 ]