Árbol 2-3


Árbol 2-3

En las ciencias de la computación, los árboles-2-3 son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Los árboles 2-3 mantienen los datos ordenados y las inserciones y eliminaciones se realizan en tiempo logarítmico amortizado.

Contenido

Definición

Son un tipo de árbol balanceado por altura (height balanced). Se define como un árbol en dónde todos los nodos no-terminales tienen 2 ó 3 descendientes y todos los nodos hoja tienen la misma longitud (path length) o distancia desde la raíz.

Fueran introducidos con el objeto de mejorar el tiempo de acceso en estructuras de datos manejadas en memoria secundaria, en las cuales el número de consultas a un registro influye de manera determinante en el tiempo de respuesta de la operación.

La estructura de árbol 2-3 exige que el crecimiento no se haga a nivel de las hojas (aunque la inserción sigue siendo en las hojas), sino que a nivel de la raíz, ya que todas las hojas se deben mantener siempre en el mismo nivel. El proceso global de inserción comienza por localizar la hoja en la cual se debe agregar el elemento.

Propiedades

Un árbol 2-3 permite que un nodo tenga dos o tres hijos. Esta característica le permite conservar el balanceo tras insertar o borrar elementos, por lo que el algoritmo de búsqueda es casi tan rápido como en un árbol de búsqueda de altura mínima. Por otro lado, es mucho más fácil de mantenerlo.

En un árbol 2-3, los nodos internos han de tener 2 ò 3 hijos y todas las hojas han de estar al mismo nivel. De forma recursiva se pueden definir como:

A es un árbol 2-3 de altura h si:

  • A es un árbol vacío (un árbol 2-3 de altura 0), o
  • A es de la forma (r, I, D), donde r es un nodo e I y D son árboles 2-3 de altura h − 1, o
  • A es de la forma (r, I, C, D), donde r es un nodo e I, C y D son árboles 2-3 de altura h-1.

Para usar estos árboles de forma eficiente en las búsquedas, hay que introducir un orden entre los elementos por lo que un árbol A es un árbol 2-3 de búsqueda de altura h si:

  • Todos los elementos de I son menores que r y todos los elementos de D son mayores que r.
  • A es de la forma (r1, r2,I, C, D), donde r1 _ r2, I, Ac y D son árboles 2-3 de búsqueda de altura h-1 y todos los elementos de I son menores que r1, todos los elementos de C son mayores que r1 y menores que r2 y todos los elementos de D son mayores que r2.

Esta definición implica que el número de hijos de un nodo es siempre uno más que el número de elementos que contiene ese nodo. En el caso de las hojas se permiten uno o dos elementos en el nodo. Desde ahora nos referiremos a los árboles 2-3 de búsqueda simplemente como árboles 2-3.

1ejemplo.jpg

La especificación del tipo ARBOL23 es muy similar a la de otros árboles con una diferencia que es la definición de tres operaciones generadoras en lugar de dos. arbolVacìo es la operación que genera un árbol sin elementos, como en los otros tipos y hay una operación, consArbol, que genera un árbol 2-3 cuya raíz tiene un solo elemento y dos hijos y otra, cons3Arbol, que genera un árbol 2-3 cuya raíz tiene dos elementos y tres hijos. Estas dos últimas operaciones son los generadores que se mantienen ocultos al usuario.

Inserción

A la hora de insertar un nuevo dato en un árbol 2-3 se hace de forma que se mantenga el equilibrio en el árbol. La capacidad de tener uno o dos elementos en cada nodo ayuda a conseguirlo.

Pseudo código de inserción en un árbol 2-3

Si el árbol esta vació
  Entonces crea un nuevo nodo y colocar el en el lado izquierdo del nodo.
    Si ya hay un elemento y existe espacio en el nodo hacer 
      Si r1 es menos que el elemento 
      Entonces el elemento 0 se coloca a la derecha.
    Sino 
      Si r1 es mayor que el elemento 
      Entonces el elemento se coloca del lado izquierdo y r1 del lado derecho.
      Sino 
         Si el nodo esta lleno se parte en dos nodos del mismo nivel, se crea un nuevo nodo
y se reparten los tres elementos (dos elementos del nodo y el nuevo elemento)

Ejemplos

A continuación se ofrecen ejemplos concretos para ilustrar el mecanismo de inserción:

Insertar39.jpgInsertar38.jpg

Insertar 37-36.jpgInsertar 36.jpg

Especificación en C tipos

   tipo_elmto = registro
        clave:tipo_clave; 
        {los demás campos necesarios} 
    freg; 
tipos_nodo = (hoja, interior); 
nodo_dos_tres = 
     registro
       clase:tipos_nodo; 
       selección
          clase=hoja:(elmto:tipo_elmto); 
          clase=interior:(primer_hijo,segundo_hijo, tercer_hijo: diccionario; 
                                   menor_de_segundo, menor_de_tercero:tipo_clave) 
       fsel
     freg
diccionario = ↑nodo_dos_tres 

Inserción

algoritmo inserta1(e/s nodo:diccionario; 
              ent x:tipo_elmto; {x se insertará en el  subárbol de nodo} 
              sal pt_nuevo:diccionario; 
                 {puntero al nodo recién creado a la derecha de nodo} 
sal menor:tipo_clave) {elmto más pequeño del subárbol al que apunta pt_nuevo} 

programa principal :

principal
     pt_nuevo:=nil; 
     si nodo es una hoja entonces
        si x no es el elmto que está en nodo entonces
            crea un nodo nuevo apuntado por pt_nuevo; 
            pone x en el nodo nuevo; 
            menor:=x.clave 
        fsi
     sino {nodo es un nodo interno} 
        sea w el hijo de nodo a cuyo subárbol pertenece x; 
        inserta1(w, x,pt_atrás,menor_atrás); 
        si pt_atrás≠nil entonces
           inserta el puntero pt_atrás entre los hijos  de nodo justo a la  derecha de w; 
           si nodo tiene cuatro hijos entonces
               crea un nodo nuevo apuntado por pt_nuevo; 
               da al nuevo nodo los hijos 3º y 4º de nodo; 
               ajusta menor_de_segundo y menor_de_tercero en nodo y el  nodo nuevo; 
               coloca menor como la menor clave entre los hijos del nodo nuevo  
           fsi
        fsi
     fsi
fin

Código en Maude :

eq insertar (E, arbolVacio) = consArbol (E, arbolVacio, arbolVacio) .
eq insertar (E, consArbol(E2, arbolVacio, arbolVacio)) =
      if E < E2 then
         cons3Arbol(E, E2, arbolVacio, arbolVacio, arbolVacio)
      else
         cons3Arbol(E2, E, arbolVacio, arbolVacio, arbolVacio)
      fi .
eq insertar (E, cons3Arbol(E2, E3, arbolVacio, arbolVacio, arbolVacio)) =
         consArbol (medio(E, E2, E3), consArbol (mínimo(E, E2), arbolVacio, arbolVacio),
         consArbol (máximo(E, E3), arbolVacio, arbolVacio)) .
eq insertar (E, consArbol(E2, I, D)) =
      if E < E2 then
         equilibrar (consArbol(E2, insertar (E, I), D))
     else
         equilibrar (consArbol(E2, I, insertar (E, D)))
     fi .
eq insertar (E, cons3Arbol(E2, E3, I, C, D)) =
     if E < E2 then
         equilibrar(cons3Arbol(E2, E3, insertar (E, I), C, D))
     else
         if E < E3 then
            equilibrar(cons3Arbol(E2, E3, I, insertar (E, C), D))
         else
            equilibrar(cons3Arbol(E2, E3, I, C, insertar (E, D)))
         fi
   fi .

Ejemplo de eliminar :

Vamos a eliminar 65 de este árbol,65es un nodo interno.

Eliminar65.jpg

65 se encuentra ahora en una ubicación no válida, lo vamos a eliminar

Eliminar65nov.jpg

Ahora haremos lo mismo para eliminar 70 que es un nodo interno

Eliminado65.jpg

70 se encuentra ahora en una ubicación no válida, porque vamos a eliminarlo

70rojo.jpg

La eliminación de la hoja nos deja con un 2-3 árbol no valido

-rojo.jpg

Combinar para fijar los nodos del árbol

Eliminado70.jpg

ahora eliminamos,100 es hoja ya se puede quitar

Eliminar100.jpg Eliminar100-2.jpg Eliminar100-3.jpg

Árbol 2-3-4

Definición

Como una forma de eliminarlas búsquedas exhaustivas de los árboles binarios existen los árboles 2-3-4. Estos son árboles en cuyos nodos se permite tener más de una clave al mismo tiempo. Los árboles binarios tienen máximo 2 hijos (derecho e izquierdo). Si se le permite al nodo tener 2 valores, este podrá tener 3 ligas a subárboles y uno con 3 valores podrá tener 4 ligas. Un árbol con estas características puede contener entonces nodos con 2, 3 o 4 ligas, de ahí que se les llama árboles 2-3-4. En los árboles 2-3-4 todos los subárboles tienen la misma altura y están siempre balanceados. Estos árboles son muy atractivos para el almacenamiento y recuperación de claves, sin embargo son un tanto complicados de implementar. Operaciones básicas:

  • Búsqueda (similar a los árboles multicamino de búsqueda)
  • Inserción (se realiza en las hojas. Se pueden producir reestructuraciones del árbol)
  • Borrado (se realiza en las hojas. Se pueden producir reestructuraciones del árbol)


Propiedades

  • En un árbol 2-3-4 de altura h tenemos:

2h - 1 elementos si todos los nodos son del tipo 2-nodo 4h - 1 elementos si todos los nodos son del tipo 4-nodo por lo que la altura de un árbol 2-3-4 con n elementos se encuentra entre los límites: log4 (n+1) y log2 (n+1)

  • Las reestructuraciones se realizan desde la raíz hacia las hojas

Inserción

Existen 3 situaciones en las que se puede encontrar un 4-nodo:

Es la raíz de un árbol 2-3-4:(DIVIDERAIZ (p))

Insertar234-1.jpg

Su padre (q) es un 2-nodo(DIVIDEHIJODE2 (p, q) )

Insertar234-2.jpg

Su padre (q) es un 3-nodo:(DIVIDEHIJODE3 (p, q) )

Insertar234-3.jpg

Algoritmo de inserción

ALGORITMO insertar (A: TArb234, y: item)
 VAR p, q: TNodo234*; noencontrado: Boolean; B: TArb234; FVAR
         p = A.farb; q = p;
         si EsVacío( A ) entonces A = ENRAIZAR (A, y, B)
         sino
            si p es 4-nodo entonces DIVIDERAIZ( A ) fsi
            noencontrado = VERDADERO;
            mientras noencontrado hacer
               si p es 4-nodo entonces
                   si q es 2-nodo entonces DIVIDEHIJODE2( p, q );
                   sino DIVIDEHIJODE3( p, q ); fsi
                   p = q;
               fsi
               caso de COMPARAR( y, p ):
                 0:// Clave de y coincide con clave en p
                    ERROR, ETIQUETA EXISTENTE;
                 1:// p apunta a un nodo hoja
                    PONER( y, p ); noencontrado = FALSO;
                 2:// clave( y ) < ItemIz.clave( p )
                    q = p; p = p -> HiIz;
                 3:// ItemIz.clave (p)<clave (y)<ItemMe.clave (p)
                    q = p; p = p -> HiMeIz;
                 4://ItemMe.clave (p)<clave (y)<ItemDe.clave (p)
                    q = p; p = p-> HiMeDe;
                 5:// clave (y) > ItemDe.clave (p)
                    q = p; p = p -> HiDe;
               fcaso
            fmientras
         fsi
fin

Ejemplo de insertar:

Insertar234-4.jpg

Borrar

  • Se reduce al borrado de un elemento en una hoja
  • En el movimiento de búsqueda, cuando pasemos a un nodo en el siguiente nivel, éste nodo debe ser 3-nodo ó 4-nodo; si no es así (es 2-nodo) hay que reestructurar.

p = nodo donde estamos q = siguiente nodo en la búsqueda r = uno de los nodos adyacentes a q (si hay dos adyacentes, escogemos r según criterio –hermano de la izquierda o hermano de la derecha–)

  • Casos:
    • . p es una hoja: p sólo puede ser 2-nodo si es la raíz
    • . q es 3-nodo ó 4-nodo: la búsqueda continúa en q sin reestructurar.
    • . q es 2-nodo y r es 2-nodo.

Boorar1.jpg

Boorar2.jpg

Enlaces de interés


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 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 …   Wikipedia Español