UNIVERSIDAD PARA EL
DESARROLLO ANDINO -
UDEA
SEMANA 14:
DEFINICION DE ARBOLES, CARACTERISTICAS,
PROPIEDADES, REPRESENTACION EN LA MEMORIA Y
RECORRIDOS EN ARBOLES BINARIOS DE BUSQUEDA
ING. JHAN CARLO ALVARADO PEREZ
ARBOLES
Un árbol es una estructura de datos que consiste en nodos conectados por aristas.
Cada árbol tiene un nodo raíz y puede tener cero o más nodos hijos. Los árboles son
utilizados para representar datos jerárquicos, como la estructura de un sistema de
archivos, la organización de una empresa, o las relaciones entre objetos en
programación.
El árbol es una estructura de datos fundamental en informática, muy utilizada en
todos sus campos, porque se adapta a la representación natural de informaciones
homogéneas organizadas y de una gran comodidad y rapidez de manipulación. Esta
estructura se encuentra en todo los dominios (campos) de la informática, desde la
pura algorítmica (métodos de clasificación y búsqueda) a la compilación (arboles
sintácticos para representar la expresiones o producciones posibles de un lenguaje) o
incluso los dominios de la inteligencia artificial (arboles de juegos, arboles de
decisiones, de resolución, etc.)
Características de los Árboles
1. Nodo Raíz: Es el nodo superior del árbol. Un árbol tiene un solo nodo raíz.
2. Nodos: Cada elemento del árbol se llama nodo. Un nodo puede tener cero o
más nodos hijos.
3. Hijos y Padres: Cada nodo (excepto la raíz) tiene un nodo padre y puede tener
varios nodos hijos.
4. Hoja: Un nodo que no tiene hijos se llama nodo hoja.
5. Altura del Árbol: La altura de un árbol es la longitud del camino más largo
desde la raíz hasta una hoja.
6. Profundidad de un Nodo: La profundidad de un nodo es el número de aristas
desde la raíz hasta ese nodo.
Propiedades de los Árboles
1. Número de Nodos: Un árbol con ( n ) nodos tiene ( n - 1 ) aristas.
2. Altura: Un árbol binario de búsqueda con ( n ) nodos tiene una
altura máxima de ( n ) (en el peor caso, cuando es degenerado) y
una altura mínima de ( \log(n) ) (en el caso más equilibrado).
3. Grado de un Nodo: El grado de un nodo es el número de hijos
que tiene. En un árbol binario, el grado de cada nodo es como
máximo 2.
4. Propiedad de los Árboles Binarios de Búsqueda:
1. Para cada nodo, todos los nodos en su subárbol izquierdo tienen valores
menores y todos los nodos en su subárbol derecho tienen valores
mayores.
Representación en la
Memoria
Los árboles se pueden representar en memoria de varias maneras, pero las
más comunes son:
1. Representación de Nodo: Cada nodo se representa como un objeto que
contiene un valor y referencias a sus nodos hijos. En un árbol binario, cada
nodo tiene dos referencias: una al hijo izquierdo y otra al hijo derecho.
2. Array: En algunos casos, los árboles
completos o completos se pueden
representar mediante un array, donde
el nodo en la posición ( i ) tiene su
hijo izquierdo en ( 2i + 1 ) y su hijo
derecho en ( 2i + 2 ).
Recorridos en Árboles
Binarios de Búsqueda
Los recorridos de árboles son métodos
utilizados para visitar todos los nodos de
un árbol en un orden específico. Los tres
tipos principales de recorridos son:
1. Recorrido Inorden (In-order Traversal):
1. Visita el subárbol izquierdo.
El recorrido inorden sería: 1, 2, 3, 4, 5, 6, 7.
2. Visita el nodo raíz.
3. Visita el subárbol derecho.
Ejemplo: Para el siguiente árbol binario de
búsqueda:
2. Recorrido Preorden (Pre-order Traversal):
• Visita el nodo raíz.
• Visita el subárbol izquierdo.
• Visita el subárbol derecho.
Ejemplo: Para el mismo árbol binario de búsqueda, el recorrido preorden
sería: 4, 2, 1, 3, 6, 5, 7.
TERMINOLOGIA Y REPRESENTACION
DE UN ARBOL GENERAL
Un árbol general es una estructura de datos que consiste en un conjunto de
nodos conectados de manera jerárquica, donde cada nodo puede tener un
número variable de hijos. A diferencia de los árboles binarios, donde cada
nodo tiene como máximo dos hijos, en un árbol general no hay un límite en el
número de hijos que un nodo puede tener.
Terminología de un Árbol
General
1. Nodo: Cada elemento del árbol se llama
nodo. Puede contener datos y referencias a
sus nodos hijos.
2. Raíz: El nodo superior del árbol. Un árbol
tiene un solo nodo raíz.
3. Hijos: Los nodos que están directamente
conectados a un nodo dado que se
encuentran en el nivel inmediatamente
inferior.
4. Padre: Un nodo que tiene uno o más nodos
hijos. Cada nodo (excepto la raíz) tiene un
único nodo padre.
5. Hoja: Un nodo que no tiene hijos. Es el nodo
más bajo en la jerarquía del árbol.
Terminología de un Árbol
General
6. Grado de un nodo: El número de hijos que tiene un
nodo. En un árbol general, un nodo puede tener un grado
variable.
7. Altura de un árbol: La longitud del camino más largo
desde la raíz hasta una hoja. También se puede definir como
el número máximo de nodos en cualquier camino desde la
raíz hasta una hoja.
8. Profundidad de un nodo: El número de aristas desde la
raíz hasta ese nodo.
9. Subárbol: Cualquier nodo y todos sus descendientes
forman un subárbol.
10. Nivel: La distancia de un nodo a la raíz. La raíz está en el
nivel 0, sus hijos están en el nivel 1, y así sucesivamente.
Representación de un Árbol
General
Los árboles generales se pueden
representar en memoria de varias
maneras. A continuación, se
presentan las dos representaciones
más comunes:
1. Representación con Listas Enlazadas
Cada nodo puede ser representado
como un objeto que contiene un
valor y una lista o un puntero a sus
nodos hijos. Esta representación es
flexible y permite un número
variable de hijos.
Ejemplo de uso:
2. Representación con Arrays
En algunos casos, especialmente si se trata
de un árbol completo o casi completo, se
puede usar un array para representar el
árbol. En este caso, se utiliza una
estructura de índice para determinar la
relación entre los nodos.
• Si un nodo está en la posición ( i ) del
array:
La representación en un array podría ser:
• Su primer hijo está en la posición ( 2i + 1 ).
• Su segundo hijo está en la posición ( 2i + 2
).
• Su padre está en la posición ( \left\lfloor
\frac{i - 1}{2} \right\rfloor ).
Ejemplo:
Supongamos que tenemos el siguiente
árbol:
Ventajas y Desventajas de las
Representaciones
• Listas Enlazadas:
• Ventajas: Flexibilidad en el número de hijos, fácil de modificar (agregar o eliminar
nodos).
• Desventajas: Mayor uso de memoria debido a punteros adicionales y puede ser
más lento en el acceso a elementos.
• Arrays:
• Ventajas: Acceso rápido a los nodos y uso eficiente de memoria si el árbol es
completo.
• Desventajas: Dificultad para manejar árboles no completos o desequilibrados, ya
que puede haber espacios vacíos en el array.
ARBOL BINARIO
Un árbol binario es una estructura de datos jerárquica en la que cada nodo
tiene, como máximo, dos hijos, denominados "hijo izquierdo" y "hijo
derecho". Esta estructura es fundamental en la informática y se utiliza en
diversas aplicaciones, como la representación de expresiones matemáticas, la
organización de datos en bases de datos, y la implementación de algoritmos
de búsqueda y ordenamiento.
Terminología de un Árbol
Binario
1. Nodo: Cada elemento del árbol que contiene un valor y referencias a sus
nodos hijos.
2. Raíz: El nodo superior del árbol. Un árbol binario tiene un solo nodo raíz.
3. Hijos: Los nodos que están directamente conectados a un nodo dado en el
nivel inmediatamente inferior. Cada nodo puede tener hasta dos hijos.
4. Padre: Un nodo que tiene uno o más nodos hijos. Cada nodo (excepto la raíz)
tiene un único nodo padre.
5. Hoja: Un nodo que no tiene hijos. Es un nodo terminal en el árbol.
Terminología de un Árbol
Binario
6. Grado de un nodo: El número de hijos que tiene un nodo. En un árbol binario,
el grado de cada nodo es como máximo 2.
7. Altura del árbol: La longitud del camino más largo desde la raíz hasta una
hoja. También se puede definir como el número máximo de nodos en cualquier
camino desde la raíz hasta una hoja.
8. Profundidad de un nodo: El número de aristas desde la raíz hasta ese nodo.
9. Subárbol: Cualquier nodo y todos sus descendientes forman un subárbol.
10. Nivel: La distancia de un nodo a la raíz. La raíz está en el nivel 0, sus hijos
están en el nivel 1, y así sucesivamente.
Propiedades de un Árbol
Binario
1. Número de Nodos: Un árbol binario con ( n ) nodos tiene ( n - 1 ) aristas.
2. Altura: Un árbol binario con ( n ) nodos tiene una altura máxima de ( n ) (en el
peor caso, cuando es degenerado) y una altura mínima de ( \log(n) ) (en el
caso más equilibrado).
3. Número Máximo de Nodos: Un árbol binario de altura ( h ) puede tener un
máximo de ( 2^{h+1} - 1 ) nodos.
4. Nodos en Niveles: En un árbol binario completo, el número de nodos en el
nivel ( l ) es ( 2^l ).
GRACIAS…
