Arboles

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

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.

Preorden o orden previo

Consiste en recorrer en primer lugar la raíz y luego el nodo hijo izquierdo y por ultimo el nodo hijo derecho

Inorden o orden simétrico

Consiste en recorrer en primer lugar el nodo hijo izquierdo y luego la raíz el nodo y por ultimo el nodo hijo derecho

Postorden o orden posterior

Consiste en recorrer en primer lugar el nodo hijo izquierdo y luego el nodo hijo derecho el nodo y por ultimo la raíz

Árbol General

Los arboles representan las estructuras no lineales y dinámicas de datos más importantes en computación .

Terminoligia

Hijo.

X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.

Padre

X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.

Hermano

Dos nodos serán hermanos si son descendientes directos de un mismo nodo.

Hoja

Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).

Nodo interno

Es un nodo que no es raíz ni terminal.

Grado

Es el número de descendientes directos de un determinado nodo.

Grado del arbol

Es el máximo grado de todos los nodos del árbol.

Nivel

Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.

Altura

Es el máximo número de niveles de todos los nodos del árbol.

Peso

Es el número de nodos del árbol sin contar la raíz.

Longitud de camino

Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X.

Árboles Binarios

Un árbol binario es una estructura de datos en la cual cada nodo

No tiene hijos (hoja).

Tiene un hijo izquierdo y un hijo derecho.

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles

Tipos de arboles binarios

árbol binario lleno

es un árbol en el que cada nodo tiene cero o dos hijos.

árbol binario perfecto

es un árbol binario lleno en el que todas las hojas están a la misma profundidad

árbol binario completo

Recorrido

Preorden

Posorden

Inorden

Recorridos en amplitud (o por niveles)

el recorrido se realiza en orden por los distintos niveles del árbol.

Árbol de búsqueda binario auto-balanceable

Es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente.

Árboles Rojo-Negro

Un árbol rojo-negro es un tipo especial de árbol binario usado en informática para organizar información compuesta por datos comparables

Operaciones

Rotación

Búsqueda

Inserción

Eliminación

Propiedades

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").

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 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.

Árboles AVL

Es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis.

Factor de equilibrio

Es la diferencia entre las alturas del árbol derecho y el izquierdo

FE = altura subárbol derecho - altura subárbol izquierdo

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.

Operaciones

Rotaciones

El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio.

Rotacion 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).

Rotacion 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).

Rotacion doble a la derecha

Rotacion doble a la izquierda

Inserción

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 nodoque pueda haberse desequilibrado durante la inserción.

Proceso de inserción:

buscar hasta encontrar la posición de inserción o modificación.

insertar el nuevo nodo con factor de equilibrio “equilibrado”

desandar el camino de búsqueda, verificando el equilibrio de los nodos, y re-equilibrando si es necesario

Extracción

Una extracción trae consigo una disminución de laaltura 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.

Búsqueda

Las búsquedas se realizan de la misma manera que en los ABB, pero al estar el árbol equilibrado la complejidad de la búsqueda nunca excederá de O (log n).

Árboles B

son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos.

Operaciones

Búsqueda

Se empieza en la raíz, y se recorre el árbol hacia abajo, escogiendo el sub-nodo de acuerdo a la posición relativa del valor buscado respecto a los valores de cada nodo.

Prosedimiento

1. . Situarse en el nodo raíz. 2. (*). Comprobar si contiene la clave a buscar. 1. . Encontrada fin de procedimiento . 2. . No encontrada: 1. Si es hoja no existe la clave. 2. En otro caso el nodo actual es el hijo que corresponde: 1. . La clave a buscar k < k1 :hijo izquierdo. 2. . La clave a buscar k > ki y k < ki+1 hijo iesimo. 3. . Volver a paso 2(*).

Inserción

Todas las inserciones se hacen en los nodos hoja.

Prosedimiento

1. Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento. 2. Si el nodo hoja tiene menos elementos que el máximo número de elementos legales, entonces hay lugar para uno más. Inserte el nuevo elemento en el nodo, respetando el orden de los elementos. 3. De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera: 1. Se escoge el valor medio entre los elementos del nodo y el nuevo elemento. 2. Los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores que el valor medio se colocan en el nuevo nodo derecho; el valor medio actúa como valor separador. 3. El valor separador se debe colocar en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente.

Eliminacion

La eliminación de un elemento es directa si no se requiere corrección para garantizar sus propiedades

Tipos

Eliminación en un nodo hoja

Eliminación en un nodo interno

Rebalanceo después de la eliminación

Árbol-B+

Representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos.

Propiedades

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.

El número de claves que pueden ser indexadas usando un árbol-B+ está en función del orden del árbol y su altura.

Árbol-B*

es una estructura de datos de árbol, una variante de Árbol-B utilizado en los sistemas de ficheros HFS y Reiser4, que requiere que los nodos no raíz estén por lo menos a 2/3 de ocupación en lugar de 1/2.

Árboles Multicamino

Tambien llamados árboles multirrama son estructuras de datos de tipo árbol usadas en computación.

Poseen un grado g mayor a dos, donde cada nodo de información del árbol tiene un máximo de g hijos.

Arboles degenerados o Arboles de columna vertebral