Arboles

{draw:g}
{draw:g}
Tabla de Contenido
Conocer La Terminología Básica De Los Árboles
Los arboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.
Los arbolespueden ser construidos con estructuras estáticas y dinámicas.
Las estáticas son:
Arreglos
Registros
Conjuntos
Las dinámicas son:
Listas
Pueden ser utilizados para: Formulas Matemáticas, Organizar Información, Árbol Genealógico, Análisis de Circuitos Electicos.
El Árbol es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de loscuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor.
{draw:frame}
Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica del mismo.
La terminología para el manejo de arboles:
HIJO. X es hijo de Y, sí y solo sí elnodo 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).
NODOINTERIOR. 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 todoslos nodos del árbol.
10.PESO. Es el número de nodos del árbol sin contar la raíz.
11.LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.
Distinguir Los Diferentes Tipos De Arboles
Á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. Usos comunes de los árboles binarios sonlos árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.
Árbol 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 (como por ejemplo números). En los árboles rojo-negro las hojas no son relevantes y no contienen datos. A la hora deimplementarlo en un lenguaje de programación, para ahorrar memoria, un único nodo (nodo-centinela) hace de nodo hoja para todas las ramas. Así, todas las referencias de los nodos internos a las hojas van a parar al nodo centinela. En los árboles rojo-negro, como en todos los árboles binarios de búsqueda, es posible moverse ordenadamente a través de los elementos de forma eficiente si hay forma delocalizar el padre de cualquier nodo. El tiempo de desplazarse desde la raíz hasta una hoja a través de un árbol equilibrado que tiene la mínima altura posible es de O (log n).
Arboles Binarios
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...