Árbol AA

Árbol AA

En informática un árbol AA es un tipo de árbol binario de búsqueda auto-balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente. Los árboles AA reciben el nombre de su inventor, Arne Andersson.

Los árboles AA son una variación del árbol rojo-negro, que a su vez es una mejora del árbol binario de búsqueda. A diferencia de los árboles rojo-negro, los nodos rojos en un árbol AA sólo pueden añadirse como un hijo derecho. En otras palabras, ningún nodo rojo puede ser un hijo izquierdo. De esta manera se simula un árbol 2-3 en lugar de un árbol 2-3-4, lo que simplifica las operaciones de mantenimiento. Los algoritmos de mantenimiento para un árbol rojo-negro necesitan considerar siete diferentes formas para balancear adecuadamente el árbol:

Red Black Shape Cases.svg

En un árbol AA, al cumplirse el estricto requisito de que sólo los enlaces derechos pueden ser rojos, sólo es necesario considerar dos formas:

AA Tree Shape Cases.svg

Contenido

Rotaciones de balanceo

En general, los árboles AA se implementan con la idea de un nivel en lugar de la de un color, a diferencia de los árboles rojo-negro. Cada nodo tiene un campo nivel y se deben cumplir las siguientes condiciones para que el árbol sea válido:

  1. El nivel de un nodo hoja es uno.
  2. El nivel de un hijo izquierdo es estrictamente menor que el de su padre.
  3. El nivel de un hijo derecho es menor o igual que el de su padre.
  4. El nivel de un nieto derecho es estrictamente menor que el de su abuelo.
  5. Cada nodo de nivel mayor que uno debe tener dos hijos.

Sólo se necesitan dos operaciones para mantener el equilibrio en un árbol AA. Estas operaciones se llaman torsión (skew) y división (split). La torsión es una rotación derecha que se realiza cuando una inserción o un borrado genera un enlace horizontal izquierdo, puede pensarse como un enlace rojo izquierdo en el contexto del árbol rojo-negro. La división es una rotación izquierda condicional que tiene lugar cuando una inserción o un borrado crea dos enlaces horizontales derechos, lo que de nuevo se corresponde con dos enlaces rojos consecutivos en el contexto de los árboles rojo-negro.

function skew is
    input: T, a node representing an AA tree that needs to be rebalanced.
    output: Another node representing the rebalanced AA tree.

    if nil(T) then
        return Nil
    else if level(left(T)) == level(T) then
        Swap the pointers of horizontal left links.
        L = left(T)
        left(T) := right(L)
        right(L) := T
        return L
    else
        return T
    end if
end function

Torsión: AA Tree Skew2.svg

function split is
    input: T, a node representing an AA tree that needs to be rebalanced.
    output: Another node representing the rebalanced AA tree.

    if nil(T) then
        return Nil
    else if level(T) == level(right(right(T))) then
        We have two horizontal right links.  Take the middle node, elevate it, and return it.
        R = right(T)
        right(T) := left(R)
        left(R) := T
        level(R) := level(R) + 1
        return R
    else
        return T
    end if
end function

División: AA Tree Split2.svg

Inserción

La inserción comienza con la búsqueda normal en un árbol binario y su procedimiento de inserción. Después, a medida que se desenrolla la pila de llamadas, es fácil comprobar la validez del árbol y realizar las rotaciones que se precisen. Si aparece un enlace horizontal izquierdo, se realiza una torsión, y si aparecen dos enlaces horizontales derechos, se realiza una división, posiblemente incrementando el nivel del nuevo nodo raíz del subárbol correspondiente. Observe que el código de muestra realiza un incremento de nivel(T). Lo que hace necesario continuar comprobando la validez del árbol a medida que las modificaciones suben desde las hojas.

function insert is
    input: X, the value to be inserted, and T, the root of the tree to insert it into.
    output: A balanced version T including X.

    Do the normal binary tree insertion procedure.  Set the result of the
    recursive call to the correct child in case a new node was created or the
    root of the subtree changes.
    if nil(T) then
        Create a new leaf node with X.
        return node(X, 1, Nil, Nil)
    else if X < value(T) then
        left(T) := insert(X, left(T))
    else if X > value(T) then
        right(T) := insert(X, right(T))
    end if
    Note that the case of X == value(T) is unspecified.  As given, an insert
    will have no effect.  The implementor may desire different behavior.

    Perform skew and then split.  The conditionals that determine whether or
    not a rotation will occur or not are inside of the procedures, as given
    above.
    T := skew(T)
    T := split(T)

    return T
end function

Borrado

Como en la mayoría de árboles binarios balanceados, el borrado de un nodo interno puede convertirse en el borrado de un nodo hoja al intercambiar el nodo interno bien con su predecesor o sucesor más próximo, dependiendo del que esté en el árbol o de los deseos del implementador. Para recuperar un predecesor símplemente se debe seguir un enlace izquierdo y después todos los enlaces derechos restantes. De forma similar, el sucesor se puede encontrar al ir una vez a la derecha una vez y a la izquierda hasta que se encuentre un puntero nulo. Dada la propiedad de los árboles AA de que todos los nodos de un nivel superior a uno tienen dos hijos, el nodo sucesor o predecesor tendrá nivel 1, haciendo que su eliminado sea trivial.

Para re-equilibrar un árbol existen diferentes aproximaciones. La que describió Andersson en su publicación original es la más simple, y se describirá aquí, aunque implementaciones reales pueden optar por un enfoque más optimizado. Tras un borrado, el primer paso para mantener la validez es reducir el nivel de todos los nodos cuyos hijos están dos niveles por debajo de ellos, o a los que les faltan hijos. Después, todo el nivel debe ser torsionado y dividido. Esta aproximación se ha visto favorecida por el hecho de que se basa en tres pasos independientes y fáciles de entender:

  1. Decrementar el nivel, si es necesario.
  2. Torsionar el nivel.
  3. Dividir el nivel.

Sin embargo, debemos torsionar y dividir todo el nivel en lugar de un solo nodo lo que complica nuestro código.

function delete is
    input: X, the value to delete, and T, the root of the tree from which it should be deleted.
    output: T, balanced, without the value X.

    if X > value(T) then
        right(T) := delete(X, right(T))
    else if X < value(T) then
        left(T) := delete(X, left(T))
    else
        If we're a leaf, easy, otherwise reduce to leaf case. 
        if leaf(T) then
            return Nil
        else if nil(left(T)) then
            L := successor(T)
            right(T) := delete(L, right(T))
            value(T) := L
        else
            L := predecessor(T)
            left(T) := delete(L, left(T))
            value(T) := L
        end if
    end if

    Rebalance the tree.  Decrease the level of all nodes in this level if
    necessary, and then skew and split all nodes in the new level.
    T := decrease_level(T)
    T := skew(T)
    right(T) := skew(right(T))
    right(right(T)) := skew(right(right(T)))
    T := split(T)
    right(T) := split(right(T))
    return T
end function
function decrease_level is
    input: T, a tree for which we want to remove links that skip levels.
    output: T with its level decreased.

    should_be = min(level(left(T)), level(right(T))) + 1
    if should_be < level(T) then
        level(T) := should_be
        if should_be < level(right(T)) then
            level(right(T)) := should_be
        end if
    end if
    return T
end function

Un buen ejemplo de borrado por este algoritmo está presente en la publicación de Andersson.

Rendimiento

El rendimiento de un árbol AA es equivalente al de un árbol rojo-negro. Un árbol AA realiza más rotaciones que un árbol red-black, pero la mayor sencillez de sus algoritmos tiende a hacerlos más rápidos, y estos factores se compensan resultando en un rendimiento similar. Un árbol rojo-negro es más constante en su rendimiento que un árbol AA, pero un árbol AA tiende a ser más llano lo que produce unos tiempos de búsqueda ligeramente más pequeños.[cita requerida]

Véase también

Referencias

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • árbol — (Del lat. arbor, ŏris). 1. m. Planta perenne, de tronco leñoso y elevado, que se ramifica a cierta altura del suelo. 2. Pieza de hierro en la parte superior del husillo de la prensa de imprimir. 3. En los órganos, eje que, movido a voluntad del… …   Diccionario de la lengua española

  • árbol — sustantivo masculino 1. Planta leñosa de tronco elevado que se ramifica a cierta altura del suelo: Han plantado muchos árboles. Este árbol da una sombra deliciosa. árbol del Paraíso Árbol de tronco gris, hojas blanquecinas, estrechas, y flores… …   Diccionario Salamanca de la Lengua Española

  • Arbol — is programming language, primarily developed to serve for Genetic Programming experiments. It is functional programming language inspired by the ideas of other small and esoteric languages. An Arbol program looks like: // Simple I/O ((Z a)b) =… …   Wikipedia

  • Arbol.bb — (Ассемини,Италия) Категория отеля: Адрес: Via Belli 6, 09032 Ассемини, Италия …   Каталог отелей

  • árbol — 1. (en anatomía) estructura anatómica con ramas que se extienden hacia fuera como las de un árbol, como el árbol bronquial. 2. patrón de búsqueda de información en una base de datos de un ordenador, siguiendo una serie de opciones ramificadas a… …   Diccionario médico

  • Árbol — (Del lat. arbor.) ► sustantivo masculino 1 BOTÁNICA Planta de tronco leñoso que se ramifica a mayor o menor altura del suelo, formando una copa. 2 NÁUTICA Madero redondo o cilíndrico fijo en una embarcación que sostiene las vergas a las que se… …   Enciclopedia Universal

  • Árbol-B — Ejemplo de árbol B. En las ciencias de la computación, los árboles B o B árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Son árboles binarios de búsqueda en… …   Wikipedia Español

  • Árbol — Para otros usos de este término, véase Árbol (desambiguación). Un roble en Dinamarca …   Wikipedia Español

  • Árbol kd — Un árbol kd tridimensional. La primera división (rojo) corta la celda raíz (blanco) en dos subceldas, que son divididas a su vez (verde) en dos subceldas. Finalmente, cada una de esas cuatro es dividida (azul) en dos subceldas. Dado que no hay… …   Wikipedia Español

  • Árbol 2-3 — Este artículo o sección sobre informática necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 2 de febrero de 2009. También puedes… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”