Árbol 2-3

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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.

Definición[editar]

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.

Fueron introducidos con el objetivo de mejorar el tiempo de acceso en estructuras de datos manejados en memoria secundaria, donde 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[editar]

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[editar]

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[editar]

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[editar]

Definición[editar]

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[editar]

  • 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[editar]

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[editar]

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[editar]

  • 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[editar]