Puntos Extra- ARBOLES Y GRAFOS

Los árboles y los grafos se refiere a estructuras de datos que permiten organizar y mantener información en un computador. Esta forma se inspira una forma de organizar información con lápiz y papel usando nodos y flechas entre los nodos (a esas flechas también se les llama arcos, a los nodos también se les llama vértices). Los grafos y árboles en papel son apropiados por ejemplo para capturar sólo una parte de la información de objetos, situaciones y otros tipos de información.

En un computador además de permitir organizar información, resultan estructuras útiles para resolver ciertos tipos de problema por ejemplo se pueden utilizar se pueden utilizar arboles AVL para mantener ordenada informacion de forma eficaz.

Para jugar, entender y emplear mejor grafos y árboles e.g Euler ha propuesto definiciones; a partir de estas definiciones y con ayuda de razonamientos lógicos ha demostrado propiedades.

Un ejemplo de arbol es el arbol binario el cual es una estructura de datos donde 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 son los arboles bianrios de busqueda, los monticulos binarios y codificacion de huffman.
Métodos para almacenar árboles binarios
Los árboles binarios pueden ser construidos a partir de lenguajes de programacion de varias formas. En un lenguaje con registros y referencias , los árboles binarios son construidos típicamente con una estructura de nodos y punteros en la cual se almacenan datos, cada uno de estos nodos tiene una referencia o puntero a un nodo izquierdo y a un nodo derecho denominados hijos. En ocasiones, también contiene un puntero a un único nodo. Si un nodo tiene menos de dos hijos, algunos de los punteros de los hijos pueden ser definidos como nulos para indicar que no dispone de dicho nodo. En la figura adjunta se puede observar la estructura de dicha implementación.

Los árboles binarios también pueden ser almacenados como una estructura de datos implicita en vectores, y si el árbol es un árbol binario completo, este método no desaprovecha el espacio en memoria. Tomaremos como notación la siguiente: si un nodo tiene un índice i, sus hijos se encuentran en índices 2i + 1 y 2i + 2, mientras que sus padres (si los tiene) se encuentra en el índice (partiendo de que la raíz tenga índice cero). Este método tiene como ventajas el tener almacenados los datos de forma más compacta y por tener una forma más rápida y eficiente de localizar los datos en particular durante un preoden transversal. Sin embargo, desperdicia mucho espacio en memoria.

 

Cabe mencionar los tipos de arboles binarios:

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