Download TIPOS DE ARBOLES

TIPOS DE
ARBOLES
Integrantes:
Liliana Xitlali Martinez Lovera
Octavio Catarino Aguilar
∗En ciencias de la informática, un
árbol es una estructura de
datos ampliamente usada que
imita la forma de un árbol (un
conjunto de nodos conectados).
∗Un nodo es la unidad sobre la
que se construye el árbol y
puede tener cero o más nodos
hijos conectados a él. Se dice
que un nodo a es padre de un
nodo b si existe un enlace desde
a hasta b (en ese caso, también
decimos que b es hijo de a).
∗Sólo puede haber un único nodo
sin padres, que llamaremos raíz.
Un nodo que no tiene hijos se
conoce como hoja. Los demás
nodos (tienen padre y uno o
varios hijos) se les conoce como
rama.
∗Ejemplo de un arbol
A
C
B
padre
hijos
Caso base: un árbol con sólo un nodo (es a la vez raíz
del árbol y hoja).
∗ Un nuevo árbol a partir de un nodo nr y
k árboles de raíces con elementos cada
uno, puede construirse estableciendo
una relación padre-hijo entre nr y cada
una de las raíces de los k árboles. El
árbol resultante de nodos tiene como
raíz el nodo nr, los nodos son los hijos
de nr y el conjunto de nodos hoja está
formado por la unión de los k conjuntos
hojas iniciales. A cada uno de los árboles
Ai se les denota ahora subárboles de la
raíz.
∗ Una sucesión de nodos del árbol, de
forma que entre cada dos nodos
consecutivos de la sucesión haya
una relación de parentesco,
decimos que es un recorrido árbol.
∗ Recorrido profundidad: En el primer
caso, se listan los nodos expandiendo el
hijo actual de cada nodo hasta llegar a
una hoja, donde se vuelve al nodo
anterior probando por el siguiente hijo y
así sucesivamente.
∗ Recorrido en anchura: En el segundo,
por su parte, antes de listar los nodos de
nivel n + 1 (a distancia n + 1 aristas de la
raíz), se deben haber listado todos los
de nivel n.
∗ El recorrido en preorden: también
llamado orden previo consiste en
recorrer en primer lugar la raíz y luego
cada uno de los hijos en orden previo.
∗ El recorrido en inorden: también
llamado orden simétrico (aunque este
nombre sólo cobra significado en los
árboles binarios) consiste en recorrer en
primer lugar A1, luego la raíz y luego
cada uno de los hijos en orden
simétrico.
∗ El recorrido en postorden: también
llamado orden posterior consiste en
recorrer en primer lugar cada uno de los
hijos en orden posterior y por último la
raíz.
∗ Las operaciones comunes en árboles
son:
∗
∗
∗
∗
∗
∗
∗
Enumerar todos los elementos.
Buscar un elemento.
Dado un nodo, listar los hijos (si los hay).
Borrar un elemento.
Eliminar un subárbol (algunas veces llamada podar).
Añadir un subárbol (algunas veces llamada injertar).
Encontrar la raíz de cualquier nodo.
∗ Por su parte, la representación puede
realizarse de diferentes formas. Las más
utilizadas son:
∗ Representar cada nodo como una
variable en el heap, con punteros a sus
hijos y a su padre.
∗ Representar el árbol con un array donde
cada elemento es un nodo y las
relaciones padre-hijo vienen dadas por
la posición del nodo en el array.
Tipos de arboles
∗ un árbol binario es una estructura de datos en
la cual cada nodo siempre tiene un hijo
izquierdo y un hijo derecho. No pueden tener
más de dos hijos (de ahí el nombre "binario").
Si algún hijo tiene como referencia a null, es
decir que no almacena ningún dato, entonces
este es llamado un nodo externo. En el caso
contrario el hijo es llamado un nodo interno.
Usos comunes de los árboles binarios son los
árboles binarios de búsqueda, los montículos
binarios y Codificación de Huffman.
∗ En teoría de grafos, se usa la siguiente
definición: «Un árbol binario es un grafo
conexo, acíclico y no dirigido tal que el
grado de cada vértice no es mayor a 3».
De esta forma sólo existe un camino
entre un par de nodos.
∗ Un árbol binario con enraizado es como
un grafo que tiene uno de sus vértices,
llamado raíz, de grado no mayor a 2.
Con la raíz escogida, cada vértice tendrá
un único padre, y nunca más de dos
hijos. Si rehusamos el requerimiento de
la conectividad, permitiendo múltiples
componentes conectados en el grafo,
llamaremos a esta última estructura un
bosque.
TIPOS DE ÁRBOL BINARIO
∗ • Un árbol binario es un árbol con raíz en el que
cada nodo tiene como máximo dos hijos.
∗ • Un árbol binario lleno es un árbol en el que cada
nodo tiene cero o dos hijos.
∗ • Un árbol binario perfecto es un árbol binario
lleno en el que todas las hojas (vértices con cero
hijos) están a la misma profundidad (distancia desde
la raíz, también llamada altura).
∗ • A veces un árbol binario perfecto es denominado
árbol binario completo. Otros definen un árbol
binario completo como un árbol binario lleno en el
que todas las hojas están a profundidad n o n-1, para
alguna n.
ALMACENAMIENTO
∗ Los árboles binarios pueden ser construidos a
partir de lenguajes de programación de varias
formas. En un lenguaje con registros y
referencias, los árboles binarios son
construidos típicamente con una estructura
de nodos y punteros en la cual se almacenan
datos, cada uno de estos nodos tiene una
referencia o puntero a un nodo izquierdo y a
un nodo derecho denominados hijos.
∗ En ocasiones, también contiene un puntero a un
único nodo. Si un nodo tiene menos de dos hijos,
algunos de los punteros de los hijos pueden ser
definidos como nulos para indicar que no dispone de
dicho nodo. En la figura adjunta se puede observar la
estructura de dicha implementación.
ÁRBOL AVL
∗ Árbol AVL es un tipo especial de árbol
binario ideado por los matemáticos
rusos Adelson-Velskii y Landis. Fue el
primer árbol de búsqueda binario autobalanceable que se ideó
∗ El árbol AVL toma su nombre de las iniciales
de los apellidos de sus inventores, AdelsonVelskii y Landis. Lo dieron a conocer en la
publicación de un artículo en 1962: "An
algorithm for the organization of information"
("Un algoritmo para la organización de la
información").
∗ Los árboles AVL están siempre equilibrados de tal modo
que para todos los nodos, la altura de la rama izquierda no
difiere en más de una unidad de la altura de la rama
derecha. Gracias a esta forma de equilibrio (o balanceo), la
complejidad de una búsqueda en uno de estos árboles se
mantiene siempre en orden de complejidad O(log n). El
factor de equilibrio puede ser almacenado directamente en
cada nodo o ser computado a partir de las alturas de los
subárboles.
∗ Para conseguir esta propiedad de equilibrio, la inserción y
el borrado de los nodos se ha de realizar de una forma
especial. Si al realizar una operación de inserción o borrado
se rompe la condición de equilibrio, hay que realizar una
serie de rotaciones de los nodos.
Definición de la altura de un árbol
∗ Sea T un árbol binario de búsqueda y sean Ti y Td sus
subárboles, su altura H(T), es:
∗ 0 si el árbol T contiene solo la raíz
∗ 1 + max(H(Ti),H(Td)) si contiene más nodos
Definición de árbol AVL
∗ Un árbol vacío es un árbol AVL
∗ Si T es un árbol no vacío y Ti y Td sus subárboles, entonces
T es AVL si y solo si:
∗ Ti es AVL
∗ Td es AVL
∗ | H(Ti) − H(Td) | < = 1
Factor de equilibrio
∗ Cada nodo, además de la información que se
pretende almacenar, debe tener los dos punteros a
los árboles derecho e izquierdo, igual que los árboles
binarios de búsqueda (ABB), y además el dato que
controla el factor de equilibrio.
∗ El factor de equilibrio es la diferencia entre las alturas
del árbol derecho y el izquierdo:
∗ FE = altura subárbol derecho - altura subárbol
izquierdo; Por definición, para un árbol AVL, este valor
debe ser -1, 0 ó 1. Si el factor de equilibrio de un nodo
es:
∗ 0 -> el nodo está equilibrado y sus subárboles tienen
exactamente la misma altura. 1 -> el nodo está
equilibrado y su subárbol derecho es un nivel más
alto. -1 -> el nodo está equilibrado y su subárbol
izquierdo es un nivel más alto. Si el factor de
equilibrio Fe≥2 o Fe≤-2 es necesario reequilibrar.
Operaciones
∗ Las operaciones básicas de un árbol AVL implican
generalmente el realizar los mismos algoritmos que
serían realizados en un árbol binario de búsqueda
desequilibrado, pero precedido o seguido por una o
más de las lla
∗ El reequilibrado se produce de abajo hacia arriba
sobre los nodos en los que se produce el
desequilibrio. Pueden darse dos casos: rotación
simple o rotación doble; a su vez ambos casos pueden
ser hacia la derecha o hacia la izquierda.madas
"rotaciones AVL".
ROTACIÓN SIMPLE A LA DERECHA.
∗ De un árbol de raíz (r) y de hijos izquierdo (i) y
derecho (d), lo que haremos será formar un nuevo
árbol cuya raíz sea la raíz del hijo izquierdo, como hijo
izquierdo colocamos el hijo izquierdo de i (nuestro i’)
y como hijo derecho construimos un nuevo árbol que
tendrá como raíz, la raíz del árbol (r), el hijo derecho
de i (d’) será el hijo izquierdo y el hijo derecho será el
hijo derecho del árbol (d).
ROTACIÓN SIMPLE A LA IZQUIERDA.
∗ De un árbol de raíz (r) y de hijos izquierdo (i) y
derecho (d), consiste en formar un nuevo árbol cuya
raíz sea la raíz del hijo derecho, como hijo derecho
colocamos el hijo derecho de d (nuestro d’) y como
hijo izquierdo construimos un nuevo árbol que tendrá
como raíz la raíz del árbol (r), el hijo izquierdo de d
será el hijo derecho (i’) y el hijo izquierdo será el hijo
izquierdo del árbol (i).
∗ Precondición : Tiene que tener hijo derecho no vacío.
ROTACIÓN DOBLE A LA DERECHA.
ROTACIÓN DOBLE A LA IZQUIERDA.
intercesión
∗ La inserción en un árbol de AVL puede ser realizada insertando el
valor dado en el árbol como si fuera un árbol de búsqueda
binario desequilibrado y después retrocediendo hacia la raíz,
rotando sobre cualquier nodo que pueda haberse desequilibrado
durante la inserción.
∗ Proceso de inserción:
∗ 1.buscar hasta encontrar la posición de inserción o modificación
(proceso idéntico a inserción en árbol binario de búsqueda)
∗ 2.insertar el nuevo nodo con factor de equilibrio “equilibrado”
∗ 3.desandar el camino de búsqueda, verificando el equilibrio de
los nodos, y re-equilibrando si es necesario
Extracción
∗ El procedimiento de borrado es el mismo que en el
caso de árbol binario de búsqueda.La diferencia se
encuentra en el proceso de reequilibrado posterior. El
problema de la extracción puede resolverse en O
(log n) pasos. Una extracción trae consigo una
disminución de la altura de la rama donde se extrajo y
tendrá como efecto un cambio en el factor de
equilibrio del nodo padre de la rama en cuestión,
pudiendo necesitarse una rotación.
∗ Esta disminución de la altura y la corrección de los
factores de equilibrio con sus posibles rotaciones
asociadas pueden propagarse hasta la raíz.
ÁRBOL ROJO-NEGRO
∗ Un árbol rojo negro es un tipo abstracto de
datos, concretamente es un árbol binario de
búsqueda equilibrado, una estructura de
datos utilizada en informática y ciencias de la
computación. La estructura original fue
creada por Rudolf Bayer en 1972, que le dio el
nombre de “árboles-B binarios simétricos”,
pero tomó su nombre moderno en un trabajo
de Leo J. Guibas y Robert Sedgewick realizado
en 1978.
∗ Es complejo, pero tiene un buen peor
caso de tiempo de ejecución para sus
operaciones y es eficiente en la práctica.
Puede buscar, insertar y borrar en un
tiempo O(log n), donde n es el número
de elementos del árbol.
∗ Un árbol rojo-negro es un tipo especial
de árbol binario usado en informática
para organizar información compuesta
por datos comparables (como por
ejemplo números).
∗ En los árboles rojo-negro las hojas no son relevantes y
no contienen datos. A la hora de implementarlo en un
lenguaje de programación, para ahorrar memoria, un
único nodo (nodo-centinela) hace de nodo hoja para
todas las ramas. Así,todas las referencias de los nodos
internos a las hojas van a para
∗ En los árboles rojo-negro, como en todos los árboles
binarios de búsqueda, es posible moverse
ordenadamente a través de los elementos de forma
eficiente si hay forma de localizar el padre de
cualquier nodo. r al nodo centinela.
∗ Un árbol rojo-negro es un árbol binario de búsqueda
en el que cada nodo tiene un atributo de color cuyo
valor es o bien rojo o bien negro. Además de los
requisitos impuestos a los árboles binarios de
búsqueda convencionales, se deben satisfacer los
siguientes para tener un árbol rojo-negro válido:
∗ Todo nodo es o bien rojo o bien negro.
∗ La raíz es negra.
∗ Todas las hojas son negras (las hojas son los hijos
nulos).
∗ Los hijos de todo nodo rojo son negros (también
llamada "Propiedad del rojo").
∗ 5. Cada camino simple desde un nodo a una hoja
descendiente contiene el mismo número de nodos
negros, ya sea contando siempre los nodos negros
nulos, o bien no contándolos nunca (el resultado es
equivalente). También es llamada "Propiedad del
camino", y al número de nodos negros de cada
camino, que es constante para todos los caminos, se
le denomina "Altura negra del árbol", y por tanto el
cámino no puede tener dos rojos seguidos.
∗ 6. El camino más largo desde la raíz hasta una hoja
no es más largo que 2 veces el camino más corto
desde la raíz del árbol a una hoja en dicho árbol. El
resultado es que dicho árbol está aproximadamente
equilibrado.
∗ Los árboles rojo-negro ofrecen un peor caso
con tiempo garantizado para la inserción, el
borrado y la búsqueda. No es esto únicamente
lo que los hace valiosos en aplicaciones
sensibles al tiempo como las aplicaciones en
tiempo real, sino que además son apreciados
para la construcción de bloques en otras
estructuras de datos que garantizan un peor
caso. Por ejemplo, muchas estructuras de
datos usadas en geometría computacional
pueden basarse en árboles rojo-negro.
Rotación
∗ Para conservar las propiedades que debe
cumplir todo árbol rojo-negro, en ciertos
casos de la inserción y la eliminación será
necesario reestructurar el árbol, si bien no
debe perderse la ordenación relativa de los
nodos. Para ello, se llevan a cabo una o varias
rotaciones, que no son más que
reestructuraciones en las relaciones padrehijo-tío-nieto.
Búsqueda
∗ La búsqueda consiste acceder a la raíz del árbol, si el
elemento a localizar coincide con éste la búsqueda ha
concluido con éxito, si el elemento es menor se busca
en el subárbol izquierdo y si es mayor en el derecho.
Si se alcanza un nodo hoja y el elemento no ha sido
encontrado se supone que no existe en el árbol. Cabe
destacar que la búsqueda en este tipo de árboles es
muy eficiente, representa una función logarítmica. La
búsqueda de un elemento en un ABB (Árbol Binario
de Búsqueda) en general, y en un árbol rojo negro en
particular, se puede realizar de dos formas, iterativa o
recursiva.
Inserción
∗ La inserción comienza añadiendo el
nodo como lo haríamos en un árbol
binario de búsqueda convencional y
pintándolo de rojo. Lo que sucede
después depende del color de otros
nodos cercanos. El término tío nodo
será usado para referenciar al hermano
del padre de un nodo, como en los
árboles familiares humanos.
∗ . Conviene notar que:
∗ • La propiedad 3 (Todas las hojas, incluyendo las
nulas, son negras) siempre se cumple.
∗ • La propiedad 4 (Ambos hijos de cada nodo rojo
son negros) está amenazada solo por añadir un nodo
rojo, por repintar un nodo negro de color rojo o por
una rotación.
∗ • La propiedad 5 (Todos los caminos desde un
nodo dado hasta sus nodos hojas contiene el mismo
número de nodos negros) está amenazada solo por
añadir un nodo rojo, por repintar un nodo negro de
color rojo o por una rotación.
casos
∗ Caso 1: El nuevo nodo N es la raíz de del árbol. En este
caso, es repintado a color negro para satisfacer la
propiedad 2 (la raíz es negra). Como esto añade un
nodo negro a cada camino, la propiedad 5 (todos los
caminos desde un nodo dado a sus hojas contiene el
mismo número de nodos negros) se mantiene.
∗ Caso 2: El padre del nuevo nodo (esto es, el nodo P) es negro, así
que la propiedad 4 (ambos hijos de cada nodo rojo son negros)
se mantiene. En este caso, el árbol es aun válido. La propiedad 5
(todos los caminos desde cualquier nodo dado a sus hojas
contiene igual número de nodos negros) se mantiene, porque el
nuevo nodo N tiene dos hojas negras como hijos, pero como N
es rojo, los caminos a través de cada uno de sus hijos tienen el
mismo número de nodos negros que el camino hasta la hoja que
reemplazó, que era negra, y así esta propiedad se mantiene
satisfecha.
∗ Caso 3: Si el padre P y el tío U son rojos, entonces ambos nodos pueden
ser repintados de negro y el abuelo G se convierte en rojo para
mantener la propiedad 5 (todos los caminos desde cualquier nodo dado
hasta sus hojas contiene el mismo número de nodos negros). Ahora, el
nuevo nodo rojo N tiene un padre negro. Como cualquier camino a
través del padre o el tío debe pasar a través del abuelo, el número de
nodos negros en esos caminos no ha cambiado. Sin embargo, el abuelo
G podría ahora violar la propiedad 2 (la raíz es negra) o la 4 (ambos hijos
de cada nodo rojo son negros), en el caso de la 4 porque G podría tener
un padre rojo. Para solucionar este problema, el procedimiento
completo se realizará de forma recursiva hacia arriba hasta alcanzar el
caso 1
∗ Caso 4: El nodo padre P es rojo pero el tío U es negro; también, el nuevo
nodo N es el hijo derecho de P, y P es el hijo izquierdo de su padre G. En
este caso, una rotación a la izquierda que cambia los roles del nuevo
nodo N y su padre P puede ser realizada; entonces, el primer nodo
padre P se ve implicado al usar el caso 5 de inserción (reetiquetando N y
P ) debido a que la propiedad 4 (ambos hijos de cada nodo rojo son
negros) se mantiene aún incumplida. La rotación causa que algunos
caminos (en el sub-árbol etiquetado como “1”) pasen a través del nuevo
nodo donde no lo hacían antes, pero ambos nodos son rojos, así que la
propiedad 5 (todos los caminos desde cualquier nodo dado a sus hojas
contiene el mismo número de nodos negros) no es violada por la
rotación.
∗ Caso 5: El padre P es rojo pero el tío U es negro, el nuevo
nodo N es el hijo izquierdo de P, y P es el hijo izquierdo de su
padre G. En este caso, se realiza una rotación a la derecha
sobre el padre P; el resultado es un árbol donde el padre P es
ahora el padre del nuevo nodo N y del inicial abuelo G. Este
nodo G ha de ser negro, así como su hijo P rojo. Se
intercambian los colores de ambos y el resultado satisface la
propiedad 4 (ambos hijos de un nodo rojo son negros). La
propiedad 5 (todos los caminos desde un nodo dado hasta
sus hojas contienen el mismo número de nodos negros)
también se mantiene satisfecha, ya que todos los caminos
que iban a través de esos tres nodos entraban por G antes, y
ahora entran por P. En cada caso, este es el único nodo negro
de los tres.
ELIMINACIÓN
∗ En un árbol binario de búsqueda normal, cuando se borra
un nodo con dos nodos internos como hijos, tomamos el
máximo elemento del subárbol izquierdo o el mínimo del
subárbol derecho, y movemos su valor al nodo que es
borrado (como se muestra aquí). Borramos entonces el
nodo del que copiábamos el valor que debe tener menos
de dos nodos no hojas por hijos. Copiar un valor no viola
ninguna de las propiedades rojo-negro y reduce el
problema de borrar en general al de borrar un nodo con
como mucho un hijo no hoja. No importa si este nodo es
el nodo que queríamos originalmente borrar o el nodo del
que copiamos el valor.
∗ Si N y su padre original son negros, entonces borrar
este padre original causa caminos que pasan por N y
tienen un nodo negro menos que los caminos que no.
Como esto viola la propiedad 5 (todos los caminos
desde un nodo dado hasta su nodos hojas deben
contener el mismo número de nodos negros), el árbol
debe ser reequilibrado. Hay varios casos a considerar.
∗ Caso 1: N es la nueva raíz. En este caso, hemos
acabado. Borramos un nodo negro de cada camino y
la nueva raíz es negra, así las propiedades se cumplen.
∗ Caso 2: S es rojo. En este caso invertimos los colores de P y S,
por lo que rotamos a la izquierda P, pasando S a ser el abuelo
de N. Nótese que P tiene que ser negro al tener un hijo rojo.
Aunque todos los caminos tienen todavía el mismo número
de nodos negros, ahora N tiene un hermano negro y un padre
rojo, así que podemos proceder a al paso 4, 5 o 6 (este nuevo
hermano es negro porque éste era uno de los hijos de S, que
es rojo). En casos posteriores, reetiquetaremos el nuevo
hermano de N como S.
∗ Caso 3: P, S y los hijos de S son negros. En este caso, simplemente
cambiamos S a rojo. El resultado es que todos los caminos a través de S,
precisamente aquellos que no pasan por N, tienen un nodo negro menos.
El hecho de borrar el padre original de N haciendo que todos los caminos
que pasan por N tengan un nodo negro menos nivela el árbol. Sin
embargo, todos los caminos a través de P tienen ahora un nodo negro
menos que los caminos que no pasan por P, así que la propiedad 5 aún no
se cumple (todos los caminos desde cualquier nodo a su nodo hijo
contienen el mismo número de nodos negros). Para corregir esto,
hacemos el proceso de reequilibrio en P, empezando en el caso 1.
∗ Caso 4: S y los hijos de éste son negros, pero P es rojo. En
este caso, simplemente intercambiamos los colores de S y
P. Esto no afecta al número de nodos negros en los
caminos que no van a través de S, pero añade uno al
número de nodos negros a los caminos que van a través
de N, compensando así el borrado del nodo negro en
dichos caminos.
∗ Caso 5: S es negro, su hijo izquierdo es rojo, el derecho es
negro, y N es el hijo izquierdo de su padre. En este caso
rotamos a la derecha S, así su hijo izquierdo se convierte en su
padre y en el hermano de N. Entonces intercambiamos los
colores de S y su nuevo padre. Todos los caminos tienen aún el
mismo número de nodos negros, pero ahora N tiene un
hermano negro cuyo hijo derecho es rojo, así que caemos en el
caso 6. Ni N ni su padre son afectados por esta transformación
(de nuevo, por el caso 6, reetiquetamos el nuevo hermano de
N como S).
∗ Caso 6: S es negro, su hijo derecho es rojo, y N es el
hijo izquierdo de P, su padre. En este caso rotamos a
la izquierda P, así que S se convierte en el padre de P
y éste en el hijo derecho de S. Entonces
intercambiamos los colores de P y S, y ponemos el
hijo derecho de S en negro. El subárbol aún tiene el
mismo color que su raíz, así que las propiedades 4 (los
hijos de todo nodo rojo son negros) y 5 (todos los
caminos desde cualquier nodo a sus nodos hoja
contienen el mismo número de nodos negros) se
verifican. Sin embargo, N tiene ahora un antecesor
negro mas: o bien P se ha convertido en negro, o bien
era negro y S se ha añadido como un abuelo negro.
De este modo, los caminos que pasan por N pasan por
un nodo negro mas.
∗ Éste pasa a través del nuevo hermano de N. Entonces, éste debe
pasar por S y P, al igual que antes, y tienen sólo que intercambiar
los colores. Así los caminos contienen el mismo número de
nodos negros.
∗ Éste pasa por el nuevo tío de N, el hijo derecho de S. Éste
anteriormente pasaba por S, su padre y su hijo derecho, pero
ahora sólo pasa por S, el cual ha tomado el color de su anterior
padre, y por su hijo derecho, el cual ha cambiado de rojo a negro.
El efecto final es que este camino va por el mismo número de
nodos negros.
ARBOL MULTICAMINO
∗ Un árbol multicamino posee un grado g mayor a dos, donde cada nodo de
información del árbol tiene un máximo de g hijos.
∗
Sea un árbol de m-caminos A, es un árbol m-caminos si y solo si:
∗ A está vacío
∗ Cada nodo de A muestra la siguiente estructura:
[nClaves,Enlace0,Clave1,...,ClavenClaves,EnlacenClaves]
∗ nClaves es el número de valores de clave de un nodo, pudiendo ser: 0 <=
nClaves <= g-1 Enlacei, son los enlaces a los subárboles de A, pudiendo ser:
0 <= i <= nClaves Clavei, son los valores de clave, pudiendo ser: 1 <= i <=
nClaves Clavei < Clavei+1
∗ Cada valor de clave en el subárbol Enlacei es menor que el valor de Clavei+1
∗ Los subárboles Enlacei, donde 0 <= i <= nClaves, son también árboles mcaminos.
∗ La principal ventaja de este tipo de árboles consiste
en que existen más nodos en un mismo nivel que en
los árboles binarios con lo que se consigue que, si el
árbol es de búsqueda, los accesos a los nodos sean
más rápidos.
∗ El inconveniente más importante que tienen es la
mayor ocupación de memoria, pudiendo ocurrir que
en ocasiones la mayoría de los nodos no tengan
descendientes o al menos no todos los que podrían
tener desaprovechándose por tanto gran cantidad de
memoria. Cuando esto ocurre lo más frecuente es
transformar el árbol multicamino en su binario de
búsqueda equivalente.
ÁRBOL AA
∗ 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:
∗ 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:
∗ Cada nodo tiene un campo nivel y se deben cumplir
las siguientes condiciones para que el árbol sea
válido:
∗ El nivel de un nodo hoja es uno.
∗ El nivel de un hijo izquierdo es estrictamente menor
que el de su padre.
∗ El nivel de un hijo derecho es menor o igual que el de
su padre.
∗ El nivel de un nieto derecho es estrictamente menor
que el de su abuelo.
∗ Cada nodo de nivel mayor que uno debe tener dos
hijos.
∗ 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 rojonegro. 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.
ÁRBOL –B+
∗ Un árbol-B+ es una variación de un árbol-B. En un árbol-B+, en contraste
respecto un árbol-B, toda la información se guarda en las hojas. Los
nodos internos sólo contienen claves y punteros. Todas las hojas se
encuentran en el mismo, más bajo nivel. Los nodos hoja se encuentran
unidos entre sí como una lista enlazada para permitir búsqueda
secuencial.
∗ El número máximo de claves en un registro es llamado el orden del árbolB+.
∗ El mínimo número de claves por registro es la mitad del máximo número
de claves. Por ejemplo, si el orden de un árbol-B+ es n, cada nodo
(exceptuando la raíz) debe tener entre n/2 y n claves.
∗ El número de claves que pueden ser indexadas usando un árbol-B+ está
en función del orden del árbol y su altura.
∗ Para un árbol-B+ de orden n, con una altura h:
∗ Número máximo de claves es: nh
∗ Número mínimo de claves es: 2(n / 2)h − 1
Árbol-B
∗ B-árbol es un árbol de búsqueda que puede estar
vacío o aquel cuyos nodos pueden tener varios hijos,
existiendo una relación de orden entre ellos, tal como
muestra el dibujo.
∗ Un árbol-B de orden M (el máximo número de hijos
que puede tener cada nodo) es un árbol que satisface
las siguientes propiedades:
∗ Cada nodo tiene como máximo M hijos.
∗ Cada nodo (excepto raíz y hojas) tiene como mínimo
M/2 hijos.
La raíz tiene al menos 2 hijos si no es un nodo hoja.
∗ Todos los nodos hoja aparecen al mismo nivel.
∗ Un nodo no hoja con k hijos contiene k-1 elementos
almacenados.
∗ Los hijos que cuelgan de la raíz (r1, ···, rm) tienen que
cumplir ciertas condiciones:
∗ El primero tiene valor menor que r1.
∗ El segundo tiene valor mayor que r1 y menor que r2, etc.
∗ El último hijo tiene valor mayor que