 Representación gráfica de un árbol binario
Un árbol binario es un árbol nulo o un árbol cuyos nodos tienen a lo sumo dos hijos. Los hijos de un árbol binario se pueden denotar como hijo izquierdo e 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 a 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úsquedas, los montículos binarios y Codificación de Huffman. Un árbol binario es un árbol en el que ningún nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho. Existen tipos de árboles binarios que suelen usarse para fines específicos, como: Árbol binario de búsqueda y Árbol de Fibonnacci.
Complejidad: árboles completos
Deduciremos, de manera inductiva la altura de las hojas en función del número de nodos.
Árbol de nivel 1.
Nodos=3 = 2^2-1
Altura =2
El caso más simple de un árbol completo tiene tres nodos,un nivel y altura (A) de dos.
Árbol de nivel 2.
Nodos = 7 =2^3-1
Altura = 3
Hemos modificado levemente la definición de altura, como el número de nodos que deben ser revisados desde la raíz a las hojas, ya que a la complejidad de los algoritmos dependerá de esta variable. A medida que se avanza en la trayectoria se descarta T(n/2) nodos en cada avance.
Árbol de nivel 3.
Nodos = 15=2^4-1
Altura = 4
Un árbol perfectamente balanceado que tiene n nodos internos tiene n+1 hojas.
Árbol de "n" nodos
n=2^A-1
A=log2(n+1) = 0(log n)
Los árboles binarios pueden ser construidos a partir de lenguajes de programación 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 almacena datos, cada uno de estos nodos y punteros 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.
Los árboles binarios también pueden ser almacenados como una estructura de datos implícita 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 encuentran en el índice [ i-1/2 ] (partiendo de que la raíz tenga índice cero). Este método tiene 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 preorden transversal. Sin embargo, desperdicia mucho espacio en memoria.
Fuentes :
|
¿Qué entendemos por abstracción? Pues bien, básicamente es un medio fundamental usado por el ser humano para enfrentarse a la complejidad del mundo. Consiste en básicamente describir o especificar aspectos esenciales e importantes de un fenómeno o entidad, al mismo tiempo que se desechan características irrelevantes según el interés de quien realiza la abstracción, un claro ejemplo sería la imagen que tenemos arriba, en donde se presenta un gato y dos personas con visión diferente con respecto a la mascota, la anciana de la izquierda observa a la criatura de una manera que se le pueda dar amor o cariño, por otra parte, la señora de la derecha, observa al animal de una manera más científica, es decir, se centra más en la cualidades o partes internas del gato. La abstracción de datos en la programación nos ayuda muchas veces a entender los problemas y atacarlos de una manera más sencilla y que la situación que se haya presentado se entienda más fácil, es decir, desechar lo que no oc...
Comentarios
Publicar un comentario