por William Read
El árbol binario es una estructura de datos formada por un conjunto de nodos. Existe un nodo raíz que es el origen de la estructura de datos.
Cada nodo lleva la información utilitaria deseada; además, contiene dos vínculos -generalmente llamados izquierdo y derecho- que conectan el nodo por la izquierda a otro nodo, por la derecha a otro nodo distinto. Estas conexiones sirven para ordenar los nodos según algún criterio de mayor que y/o menor que. Uno y hasta ambos vínculos pueden no estar conectados, quedan en el limbo, y entonces su valor es nil.
Los lenguajes de programación modernos (c++, pascal, etc.) permiten modelar estructuras de árbol binario fácilmente. El manejo de los árboles binarios puede hacerse usando funciones muy sencillas, pero difíciles de entender al principio. Se trata de las llamadas funciones recursivas; éstas se llaman a si mismas tantas veces como sea necesario, hasta alcanzar la meta propuesta.
Un árbol binario bien diseñado debe ser simétrico. En el nivel cero está solamente la raiz, en el nivel 1 hay 2 nodos, en el 2do nivel hay 4 nodos, en el 3ro se tienen 8 y así sucesivamente. Si asignásemos un nodo a cada habitante del planeta, necesitaríamos un árbol de unos 26 niveles, solamente.
La principal utilidad del árbol binario está en los llamados árboles de búsqueda. Asignando un número de identificación a cada habitante del caso anterior, ordenados en un árbol binario simétrico, podríamos encontrar el número correspondiente a un habitante en particular entrando por la raíz y preguntando si el número buscado es menor o mayor que el de la raíz. Si es menor nos dirigimos al nodo izquierdo y repetimos la misma pregunta, si es mayor vamos al nodo de la derecha, y así hasta encontrar la entrada buscada. Máximo 25 veces tendríamos que preguntar para encontrar la ficha identificadora de cualquier habitante.
En computación se usa poco el árbol binario porque las funciones recursivas que logran la búsqueda con tanta eficiencia, usan el mecanismo de la pila ó "stack" que pudiera causar desbordes en la memoria interna de los computadores. Por eso se prefiere la búsqueda iterativa, aunque ésta sea mas lenta. Cuando las listas de búsqueda son muy grandes y entonces valdría la pena usar almacenamientos en estructura de árbol binario, entonces hay que asegurarse de que el árbol creado resulte lo mas balanceado posible, para que la pila no tenga que visitar muchos niveles.
Iterando para encontrar un habitante de los últimos en una lista lineal habría que preguntar unos seis mil millones de veces. Recurriendo en un árbol binario balanceado solamente tendríamos que preguntar 25 veces -con mala suerte-. Si la raiz del árbol es 1 y todas las hojas izquierdas están vacías (=nil), el nivel del árbol sería seis mil millones y ninguna computadora actual tiene una pila así, lo que resultaría es un desborde de pila.
En computación hay un adagio que reza: "Iterar es humano, recurrir es divino".
Cada nodo lleva la información utilitaria deseada; además, contiene dos vínculos -generalmente llamados izquierdo y derecho- que conectan el nodo por la izquierda a otro nodo, por la derecha a otro nodo distinto. Estas conexiones sirven para ordenar los nodos según algún criterio de mayor que y/o menor que. Uno y hasta ambos vínculos pueden no estar conectados, quedan en el limbo, y entonces su valor es nil.
Los lenguajes de programación modernos (c++, pascal, etc.) permiten modelar estructuras de árbol binario fácilmente. El manejo de los árboles binarios puede hacerse usando funciones muy sencillas, pero difíciles de entender al principio. Se trata de las llamadas funciones recursivas; éstas se llaman a si mismas tantas veces como sea necesario, hasta alcanzar la meta propuesta.
Un árbol binario bien diseñado debe ser simétrico. En el nivel cero está solamente la raiz, en el nivel 1 hay 2 nodos, en el 2do nivel hay 4 nodos, en el 3ro se tienen 8 y así sucesivamente. Si asignásemos un nodo a cada habitante del planeta, necesitaríamos un árbol de unos 26 niveles, solamente.
La principal utilidad del árbol binario está en los llamados árboles de búsqueda. Asignando un número de identificación a cada habitante del caso anterior, ordenados en un árbol binario simétrico, podríamos encontrar el número correspondiente a un habitante en particular entrando por la raíz y preguntando si el número buscado es menor o mayor que el de la raíz. Si es menor nos dirigimos al nodo izquierdo y repetimos la misma pregunta, si es mayor vamos al nodo de la derecha, y así hasta encontrar la entrada buscada. Máximo 25 veces tendríamos que preguntar para encontrar la ficha identificadora de cualquier habitante.
En computación se usa poco el árbol binario porque las funciones recursivas que logran la búsqueda con tanta eficiencia, usan el mecanismo de la pila ó "stack" que pudiera causar desbordes en la memoria interna de los computadores. Por eso se prefiere la búsqueda iterativa, aunque ésta sea mas lenta. Cuando las listas de búsqueda son muy grandes y entonces valdría la pena usar almacenamientos en estructura de árbol binario, entonces hay que asegurarse de que el árbol creado resulte lo mas balanceado posible, para que la pila no tenga que visitar muchos niveles.
Iterando para encontrar un habitante de los últimos en una lista lineal habría que preguntar unos seis mil millones de veces. Recurriendo en un árbol binario balanceado solamente tendríamos que preguntar 25 veces -con mala suerte-. Si la raiz del árbol es 1 y todas las hojas izquierdas están vacías (=nil), el nivel del árbol sería seis mil millones y ninguna computadora actual tiene una pila así, lo que resultaría es un desborde de pila.
En computación hay un adagio que reza: "Iterar es humano, recurrir es divino".
Comentarios
Publicar un comentario