arboles b

UNIVERSIDAD DE GUADALAJARA
CENTRO UNIVERSITARIO DE CIENCIAS EXACTAS E INGENIERIAS
DIVISIÓN DE ELECTRÓNICA Y COMPUTACIÓN
DEPARTAMENTO DE CIENCIAS COMPUTACIONALES


ESTRUCTURA DE ARCHIVOS
“RESUMEN DE ÁRBOLES”
LUIS ALBERTO CRUZ MORA
206573452
SEC D01
ARBOLES
DEFINICIÓN
Un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol mediante un conjunto de nodosconectados. 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 (tienenpadre y uno o varios hijos) se les conoce como rama.
TIPOS DE ARBOLES
Árboles Binarios
Árbol de búsqueda binario auto-balanceable
Árboles AVL
Árboles Rojo-Negro
Árbol AA
Árboles Multicamino
Árboles B (Arboles de búsqueda multicamino auto-balanceados)
Árbol-B+
Árbol-B*
OPERACIONES DE LOS ARBOLES
Enumerar todos los elementos.
Buscar un elemento.
Dado un nodo, listar los hijos
Borrar unelemento.
Eliminar un subárbol
Añadir un subárbol
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 laposición del nodo en el Array.

USO DE LOS ARBOLES
Representación de datos jerárquicos
Como ayuda para realizar búsquedas en conjuntos de datos

ÁRBOLES BINARIOS
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. 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.
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 árbolbinario perfecto es un árbol binario lleno en el que todas las hojas están a la misma profundidad. 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.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En unárbol binario cada nodo puede tener cero, uno o dos hijos. Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

RECORRIDOS SOBRE EL ARBOL BINARIO
RECORRIDO PREORDEN
En este tipo de recorrido se realiza cierta acción sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma paraentender el recorrido con este método seria seguir el orden: nodo raíz, nodo izquierda, nodo derecha.

RECORRIDO INORDEN
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. Otra forma para entender el recorrido con este método seria seguir el orden: nodoizquierda, nodo raíz, nodo derecha.
RECORRIDO POSTORDEN
En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. Otra forma para entender el recorrido con este método seria seguir el orden: nodo izquierda, nodo derecha, nodo raíz.

ARBOLES BINARIO DE BUSUQEDA AUTO BALANCEABLE
Es un árbol binario de búsqueda que intenta mantener su altura, o el número de...