Arboles

Los arboles representan las estructuras no lineales y dinámicas de datos más importantes en computación . 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 Hoja

Dos nodos serán hermanos si son descendientes directos de un mismo nodo. 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.

Árbol General Terminoligia

Grado

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

Grado del arbol Nivel Altura Peso

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

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. Es el máximo número de niveles de todos los nodos del árbol. 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. No tiene hijos (hoja).

Un árbol binario es una estructura de datos en la cual cada nodo 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 árbol binario lleno Tipos de arboles binarios

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

Árboles Binarios árbol binario completo Preorden Posorden Recorrido Inorden Recorridos en amplitud (o por niveles)

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

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. Un árbol rojo-negro es un tipo especial de árbol binario usado en informática para organizar información compuesta por datos comparables Rotación Búsqueda Operaciones Inserción Eliminación Árboles Rojo-Negro

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). Propiedades 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. Es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis.

Es una estructura jerarquica de datos que imita la forma de un árbol Es la diferencia entre las alturas del árbol derecho y el izquierdo Es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. FE = altura subárbol derecho - altura subárbol izquierdo Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b Factor de equilibrio Sólo puede haber un único nodo sin padres, que llamaremos raíz.

0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura.

Nodo Si el factor de equilibrio de un nodo es

Arboles

Un nodo que no tiene hijos se conoce como hoja.

Tipos de arboles

1 -> el nodo está equilibrado y su subárbol derecho es un nivel más alto.

Árbol de búsqueda binario auto-balanceable -1 -> el nodo está equilibrado y su subárbol izquierdo es un nivel más alto.

Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

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

Rotacion simple a la derecha

Preorden o orden previo Inorden o orden simétrico

Recorridos

Postorden o orden posterior Rotaciones

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

Árboles AVL

Rotacion simple a la izquierda

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). 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 Operaciones Rotacion doble a la izquierda

Inserción

Extracción

Búsqueda

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.

buscar hasta encontrar la posición de inserción o modificación. Proceso de inserció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

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

son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. 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. 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(*).

Búsqueda Prosedimiento

Todas las inserciones se hacen en los nodos hoja. Operaciones

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.

Inserción Prosedimiento Árboles B

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

Eliminación en un nodo hoja Tipos Eliminación en un nodo interno

Rebalanceo después de la eliminación Representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. El número máximo de claves en un registro es llamado el orden del árbol-B+. Árbol-B+ Propiedades

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. Tambien llamados árboles multirrama son estructuras de datos de tipo árbol usadas en computación.

Árboles Multicamino 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