1. Árbol Rojo-Negro
1.1. Concepto
1.1.1. 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.
1.1.2. Es un tipo especial de árbol binario usado en informática para organizar información compuesta por datos comparables (como por ejemplo números).
1.2. Carcateristicas
1.2.1. 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
1.2.2. 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.
1.2.3. 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,
1.2.3.1. 1.-Todo nodo es o bien rojo o bien negro. 2.-La raíz es negra. 3.-Todas las hojas son negras (las hojas son los hijos nulos). 4.-Los hijos de todo nodo rojo son negros (también llamada "Propiedad del rojo").
1.2.4. 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.
1.2.5. 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
1.2.6. 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
1.3. Operaciones
1.3.1. Rotación
1.3.1.1. 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 padre hijo tío nieto.
1.3.2. Búsqueda
1.3.2.1. 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
1.3.3. Inserción
1.3.3.1. 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.
1.3.3.1.1. 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.
1.3.4. Eliminación
1.3.4.1. 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.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.
2. Árbol MULTICAMINO
2.1. Características
2.1.1. 1.-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. 2.-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,Enlace 0 ,Clave 1 ,...,Clave nClaves ,Enlace nClaves •nClaves es el número de valores de clave de un nodo, pudiendo ser: 0 <= nClaves g 1 Enlace i son los enlaces a los subárboles de A pudiendo ser: 0 <= i <= nClaves Clave i , son los valores de clave, pudiendo ser: 1 <= i <= nClaves Clave i Clave i+1 •Cada valor de clave en el subárbol Enlace i es menor que el valor de Clave i+1 •Los subárboles Enlace i donde 0 i nClaves, son también árboles m caminos.
2.2. Ventaja
2.2.1. 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.
2.3. Desventaja
2.3.1. 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.
3. Árbol -B
3.1. Concepto
3.1.1. 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,
3.2. Propiedades
3.2.1. 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:
3.2.1.1. •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 ( ···, 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
4. Árbol AA
4.1. Concepto
4.1.1. 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.
4.2. Carcaterísticas
4.2.1. •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.
4.3. Operaciones
4.3.1. 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.
5. Binario
5.1. Almacenamiento
5.1.1. Los árboles binarios son construidos típica-mente 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.
5.1.2. 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
5.2. Concepto
5.2.1. 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).
5.3. Tipos de a´boles binarios
5.3.1. Arboles binarios de búsqueda, los montículos binarios y Codificación de Huffman
5.4. Características
5.4.1. Nodo externo es aquel que no almacena ningún dato En el caso contrario el hijo es llamado un nodo interno
5.4.2. 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")
6. Árbol AVL
6.1. Operaciones
6.1.1. ROTACIÓN SIMPLE A LA DERECHA.
6.1.1.1. Rota a la raiz lo que hara será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo,y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol,el hijo derecho de la raiz izquierda sera el hijo izquierdo y el hijo derecho será el hijo derecho del árbol
6.1.2. ROTACIÓN SIMPLE A LA IZQUIERDA.
6.1.2.1. 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 (
6.1.3. ROTACIÓN DOBLE A LA DERECHA.
6.1.4. ROTACIÓN DOBLE A LA IZQUIERDA.
6.1.5. INTERCESION
6.1.5.1. 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.
6.1.5.1.1. 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)
6.1.5.1.2. 2.Insertar el nuevo nodo con factor de equilibrio “Equilibrado"
6.1.5.1.3. 3.Desandar el camino de búsqueda, verificando el equilibrio de los nodos, y re equilibrando si es necesario
6.1.6. EXTRACCIÓN
6.1.6.1. 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.
6.1.6.1.1. 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.
6.2. Factor de Equilibrio
6.2.1. •El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo
6.2.2. •F.E = 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.
6.3. Características
6.3.1. 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
6.3.2. 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.
7. Árbol -B+
7.1. Concepto
7.1.1. 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.
7.2. Características
7.2.1. •El número máximo de claves en un registro es llamado el orden del árbol B+. •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: n h •Número mínimo de claves es: 2( n 2) h − 1