A Eje biselado o entonces Eje abocinado [1] es un árbol de búsqueda binario autoequilibrado, con la propiedad adicional de que se accederá más rápido a los elementos vistos recientemente en visitas posteriores. Realiza operaciones básicas como inserción, búsqueda y borrado en un tiempo del orden de O (log n). Para muchas secuencias de operaciones no uniformes, el bisel árbol funciona mejor que otros árboles de investigación, incluso cuando se desconoce el patrón específico de la secuencia. Esta estructura de datos fue inventada por Robert tarjan y Daniel Sleator .

Todas las operaciones normales de un árbol de búsqueda binaria se combinan con una operación básica, denominada achaflanado. Esta operación consiste en reordenar el árbol para un determinado elemento, colocándolo en el raíz . Una forma de hacerlo es hacer primero una búsqueda binaria en el árbol para encontrar el elemento en cuestión y luego usar las rotaciones del eje de una manera específica para llevar el elemento a la parte superior. Alternativamente, un algoritmo “de arriba hacia abajo” puede combinar la búsqueda y reorganización del árbol en un solo paso.

resumen

[ hide ]

  • 1 Ventajas y desventajas
  • 2 Operaciones
    • 1 Investigación
    • 2 Inserción
    • 3 Eliminación
  • 3 Operación de achaflanado
    • 1 bisel hacia arriba
    • 2 bisel hacia abajo
  • 4 teoremas de rendimiento
    • 1 teorema del equilibrio
    • 2 Conjetura de optimalidad dinámica
  • 5 referencias
  • 6 fuentes

Ventajas y desventajas

El buen agarre de un bisel árbol [2] depende de si se autoequilibra y también se optimiza automáticamente. Más consultados nudos se acercará a la raíz donde se puede acceder a ellos más rápidamente. Este es un beneficio para casi cualquier aplicación y es particularmente útil para implementar cachés y algoritmos de recolección de basura; sin embargo, es importante tener en cuenta que para un acceso uniforme, el rendimiento de un eje biselado será considerablemente peor que una simple búsqueda binaria equilibrada. árbol .

Los árboles de bisel también tienen la ventaja de ser considerablemente más sencillos de implementar que otros árboles de búsqueda binarios autoequilibrados, como los árboles rojo-negro o los árboles AVL, mientras que su rendimiento en el medio de la caja es igual de efectivo. Además, los árboles de bisel no necesitan almacenar información adicional que no sean los datos en sí, lo que minimiza los requisitos de memoria. Sin embargo, estas estructuras de datos adicionales brindan garantías en el peor de los casos y pueden ser más eficientes en la práctica para un acceso uniforme.

Uno de los peores casos para el algoritmoLa base del eje biselado es el acceso secuencial a todos los elementos del eje de forma ordenada. Esto deja el árbol completamente desequilibrado (son necesarios n accesos, cada uno del orden de O (log n) operaciones). Acceder al primer elemento vuelve a desencadenar una operación que toma el orden de O (n) operaciones para reequilibrar el árbol antes de devolver este primer elemento. Este es un retraso significativo para esta operación final, incluso si el rendimiento vale la pena si consideramos la secuencia completa, que es del orden de O (log n). Sin embargo, una investigación reciente muestra que si reequilibramos el árbol de forma aleatoria, podemos evitar este efecto de desequilibrio y ofrecer un rendimiento similar a otros algoritmos de equilibrio automático.

A diferencia de otros tipos de ejes autoequilibrados, los ejes biselados funcionan bien con nodos que contienen llaves idénticas. Incluso con claves idénticas, el rendimiento permanece amortiguado en el orden de O (log n). Todas las operaciones del árbol conservan el orden de los nodos idénticos en el árbol, que es una propiedad similar a la estabilidad de los algoritmos de clasificación.

Operaciones

Buscar

En búsqueda de [3] a llave El valor en un árbol biselado tiene la particularidad de modificar la estructura del árbol . El descenso se realiza de la misma manera que un árbol de búsqueda binario, pero si se encuentra un nodo cuyo valor clave coincide con el buscado, se realiza un bisel de este nodo. Si no se encuentra, el nodo de bisel será el que visitamos por última vez antes de abandonar la búsqueda. Por lo tanto, la raíz contendrá un sucesor o un predecesor de la buscado nodo .

Inserción

Es lo mismo que en la búsqueda binaria. árbol excepto que se hace un bisel en el inserto nodo . Además, si el llave el valor a insertar ya existe en el árbol , la nodo el contenedor está biselado.

Eliminación

Esta operación requiere dos chaflanes. Primero el nodo que contiene el valor clave a extraer. Si no se encuentra, el árbol está biselado al final nodo examinado y no se toman más medidas. Si se encuentra, el nodo está biselado y eliminado. Con esto, el árbol se divide en dos mitades, por lo que debe seleccionar un nodo actuar como la raíz. Dado que se trata de un árbol de búsqueda binario y todos los valores clave están ordenados, podemos elegir el valor más alto del subárbol izquierdo o el valor clave más bajo de la derecha como raíz.

Operación de biselado

Esta operación mueve un nodo x, que es el nodo al que se accede, en raíz . Para hacer esto, necesitamos rotar el árbol de modo que en cada rotación el nodo x está más cerca del raíz . Cada bisel hecho en el nodo interés mantenerlo árbol parcialmente equilibrado y también el recientemente accedido nudos se encuentran en las inmediaciones de raíz . De esta forma amortizamos el tiempo empleado en realizar el chaflán. Podríamos distinguir 3 casos generales:

  • Caso 1: x es el hijo izquierdo o derecho del raíz, pag.
  • Caso 2: x es el hijo izquierdo de py este a su vez es el hijo izquierdo de q o ambos son hijos derechos.
  • Caso 3: x es el hijo izquierdo de py este a su vez es el hijo derecho de q o viceversa.

CASO 1: Si x es un niño a la izquierda de p, entonces realizaremos una rotación derecha simple. En el caso de que x sea la derecha, la rotación que tenemos que hacer es simple hacia la izquierda.

CASO 2: Si x es el hijo y el nieto izquierdos de pyq, respectivamente. Luego necesitamos hacer una doble rotación hacia la derecha, en el caso de que x sea el hijo y nieto derecho de pyq, la rotación será el doble hacia la izquierda.

CASO 3: En el caso de que x sea el hijo izquierdo de py el nieto derecho de q, realizaremos una rotación simple a la derecha en el borde entre x y py otra simple a la izquierda entre x y q. De lo contrario, x es el hijo derecho y el nieto izquierdo de q, las rotaciones individuales serán a la izquierda y luego a la derecha.

biselar

Operaciones de orden de compra [4] están realizado de manera similar a un árbol de búsqueda binario. A continuación, se realiza una operación de chaflán en un nodo . En una búsqueda, el nodo que contiene el valor buscado, o se devuelve el padre del hoja si no se puede encontrar. En un inserto, el nodo sobre el que se aplica la operación de bisel es el que tiene el mismo valor que el buscado, si ya existía; o el nuevo nodo si no estaba en el árbol . En bisel ascendente, es necesario descender desde raíz a nodo al que se aplicará la operación de bisel. Entonces las rotaciones se hacen como tú subir.

En otras palabras, el árbol se atraviesa dos veces. A partir de nodo , al que se le aplicará la operación, se le asciende hasta encontrar al abuelo, y se realiza la doble rotación correspondiente; si no hay abuelo, pero hay padre, se realiza una rotación simple.

biselar hacia abajo

Consiste en dividir el árbol en dos subárboles, uno con claves más pequeñas que el buscado y el otro con llaves superior al buscado, ya medida que desciende se realizan las rotaciones. Cuando el nodo se encuentra en raíz del subárbol central, los subárboles se unen, dejando el nodo como el raíz . Cada vez que desciende de un nodo x, por un enlace izquierdo, entonces xy su subárbol derecho serán mayores que el nodo (que se insertará o que se buscará). De esta manera se puede formar un subárbol, con xy su subárbol derecho, siendo este subárbol DER.

El caso simétrico, que ocurre cuando se sigue un enlace derecho, identifica el subárbol izquierdo del nuevo raíz , o este subárbol llamado IZQUIERDA. Como solo se recorre una vez, toma la mitad del tiempo del ascendente. Los punteros se mantienen IZQUIERDA y DERECHA, y los punteros en los puntos de inserción de los nuevos nodos IZQUIERDA y DERECHA; son los hijos correctos del elemento IZQUIERDO más alto; y el hijo izquierdo del más mínimo elemento de DER. Estas variables evitan tener que cruzar IZQUIERDA y DERECHA; los nodos y subárboles que se agregan a IZQUIERDA o DERECHA, no cambian sus posiciones a IZQUIERDA o DERECHA. A partir de raíz, bajamos hasta encontrar un posible nieto, la operación se realiza pasando al abuelo y al padre a los subárboles IZQUIERDA y DERECHA; el nieto se queda en raízde la central árbol . Si la nodo se encuentra, se realiza una unión final.

Teoremas de rendimiento

Teorema del equilibrio

El coste de realizar la secuencia de acceso S es del orden de O (m (logn + 1) + nlogn). En otras palabras, biselado árboles realizando así árboles de búsqueda binarios equilibrados estáticamente en secuencias de al menos n accesos.

Conjetura de optimalidad dinámica

Además de las garantías comprobadas de rendimiento del eje biselado, el artículo original de Sleator y Tarjan contiene una suposición no comprobada de gran interés. Esta conjetura se conoce como conjetura de optimización dinámica, y básicamente sostiene que los árboles de bisel se comportan tan bien como cualquier otra búsqueda de árbol binario. algoritmo hasta un factor constante.

Sea A cualquier árbol de búsqueda binario algoritmo que accede a un elemento x cruzando el camino desde el raíz ax, a costa de d (x) + 1, y que entre los accesos puede hacer cualquier rotación en el árbol al precio de 1 por rotación. Sea A (S) el costo de A para realizar la secuencia de acceso S. Entonces, el costo de hacer los mismos accesos para un bisel árbol es del orden O (n + A (S)).

Hay varios corolarios de la conjetura de la optimización dinámica que quedan por probar:

Conjetura cruzada: Sean T1 y T2 dos biseles árboles que contienen los mismos elementos. Sea S la secuencia obtenida después de haber visitado los elementos de T2 en preorden. El costo total para realizar la secuencia de acceso S en T1 es del orden de O (n). Conjetura de Deque: Sea S una secuencia de m operaciones de cola de dos extremos (empujar, hacer estallar, inyectar, expulsar). Entonces el costo de realizar esta secuencia de operaciones S en bisel árbol es del orden de O (m + n).

Dividir conjetura: Sea S cualquier permutación de los elementos de la biselado árbol . Entonces, el costo de eliminar elementos en el orden S es del orden de O (n).

Por F. Tips

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *