Download Diapositiva 1

Estructura de Datos
Unidad 6:
ARBOLES
A. CONCEPTO DE ARBOL
B. TIPOS DE ARBOL
C. ARBOL BINARIO
D. IMPLEMENTACION DE UN ARBOL BINARIO
E. PROYECTO
M.C. Gustavo A. Gutiérrez Carreón
may-10
Introducción
 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.
M.C. Gustavo A. Gutiérrez Carreón
may-10
Introducción - Tipos de Árboles
 Árboles Binarios
 Árbol de búsqueda binario auto-balanceable (intenta mantener su
altura, o el número de niveles de nodos bajo la raíz, tan pequeños
como sea posible )
 Árboles AVL
 Árboles Rojo-Negro
 Árbol AA
 Árboles B (Los árboles B mantienen los datos ordenados y las
inserciones y eliminaciones se realizan en tiempo logarítmico
amortizado)
 Árbol-B+
 Árbol-B*
 Árboles Multicamino (posee un grado g mayor a dos, donde cada
nodo de información del árbol tiene un máximo de g hijos)
M.C. Gustavo A. Gutiérrez Carreón
may-10
Árbol Binario
 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.
M.C. Gustavo A. Gutiérrez Carreón
may-10
Á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.
M.C. Gustavo A. Gutiérrez Carreón
may-10
Recorridos sobre árboles binarios
 Recorrido en 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.
 En el árbol de la figura el
recorrido en preorden
sería: 2, 7, 2, 6, 5, 11, 5, 9
y 4.
M.C. Gustavo A. Gutiérrez Carreón
 Un árbol binario sencillo
de tamaño 9 y altura 3, con
un nodo raíz cuyo valor es
2.
may-10
Recorridos sobre árboles binarios
 Recorrido en
postorden
 En este caso se trata
primero el subárbol
izquierdo, después el
derecho y por último el
nodo actual.
 En el árbol de la figura el
recorrido en postorden
sería: 2, 5, 11, 6, 7, 4, 9, 5
y 2.
M.C. Gustavo A. Gutiérrez Carreón
 Un árbol binario sencillo
de tamaño 9 y altura 3, con
un nodo raíz cuyo valor es
2.
may-10
Recorridos sobre árboles binarios
 Recorrido en 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.
 En el árbol de la figura el
recorrido en inorden sería: 2,
7, 5, 6, 11, 2, 5, 4 y 9.
M.C. Gustavo A. Gutiérrez Carreón
 Un árbol binario sencillo de
tamaño 9 y altura 3, con un
nodo raíz cuyo valor es 2.
may-10
Árbol Binario de Búsqueda
 Un árbol binario de búsqueda (ABB) es un árbol binario




definido de la siguiente forma:
Todo árbol vacío es un árbol binario de búsqueda.
Un árbol binario no vacío, de raíz R, es un árbol binario de
búsqueda si:
En caso de tener subárbol izquierdo, la raíz R debe ser mayor
que el valor máximo almacenado en el subárbol izquierdo, y
que el subárbol izquierdo sea un árbol binario de búsqueda.
En caso de tener subárbol derecho, la raíz R debe ser menor
que el valor mínimo almacenado en el subárbol derecho, y
que el subárbol derecho sea un árbol binario de búsqueda
M.C. Gustavo A. Gutiérrez Carreón
may-10
Implementación (ABB – enteros)
may-10
Implementación (ABB – enteros)
may-10
Implementación (ABB – enteros)
M.C. Gustavo A. Gutiérrez Carreón
may-10
Implementación (ABB – enteros)
M.C. Gustavo A. Gutiérrez Carreón
may-10
Implementación (ABB – enteros)
M.C. Gustavo A. Gutiérrez Carreón
may-10
Implementación (ABB – enteros)
M.C. Gustavo A. Gutiérrez Carreón
may-10
Implementación (ABB – enteros)
M.C. Gustavo A. Gutiérrez Carreón
may-10
Implementación (ABB – enteros)
M.C. Gustavo A. Gutiérrez Carreón
may-10
Implementación (ABB – enteros)
M.C. Gustavo A. Gutiérrez Carreón
may-10
Tarea
 Haga un programa utilizando su implementación de enteros,
pero con String.
 Almacene varias palabras y haga el recorrido inorden para
verificar que lo ordena alfabéticamente.
M.C. Gustavo A. Gutiérrez Carreón
may-10
Altura de un árbol
 Es la máxima cantidad de nodos que se recorrerán desde el
último nivel de nodo hasta la raíz.
M.C. Gustavo A. Gutiérrez Carreón
may-10
Hojas de un árbol
 Son aquellos nodos del árbol que no tienen hijos.
M.C. Gustavo A. Gutiérrez Carreón
may-10
Ancestros de un nodo
 Son aquellos nodos que preceden a partir de la raíz a un
determinado valor de nodo.
M.C. Gustavo A. Gutiérrez Carreón
may-10