Matemáticas digital: Árboles

Árbol Binario Un árbol binario es un conjunto finito de elementos, el cual está vacío o dividido en tres subconjuntos separados: El primer subconjunto contiene un elemento único llamado raíz del árbol. El segundo subconjunto es en sí mismo un árbol binario y se le conoce como sub-árbol izquierdo del árbol original. El tercer subconjunto es también un árbol binario y se le conoce como sub-árbol derecho del árbol original. El sub-árbol izquierdo o derecho puede o no estar vacío. Cada elemento de un árbol binario se conoce como nodo del árbol. Si B es la raíz de un árbol binario y D es la raíz del sub-árbol izquierdo/derecho, se dice que B es el padre de D y que D es el hijo izquierdo/derecho de B. A un nodo que no tiene hijos, tal como A o C de la Ilustración 2, se le conoce como hoja. Un nodo n1 es un ancestro de un nodo n2 (y n2 es un descendiente de n1) si n1 es el padre de n2 o el padre de algún ancestro de n2. Recorrer un árbol de la raíz hacia las hojas se denomina descende...

Conceptos Altura de un nodo: en un árbol es el número de nodos del camino más largo de ese nodo a una hoja. Altura del árbol: es la altura de la raíz, o 0 si el árbol es vacío. Profundidad de un nodo: es la longitud del camino único que va desde la raíz hasta ese nodo. Grado de un nodo: número de hijos de dicho nodo. Grado de un árbol: es el mayor grado de los nodos que contiene. Nivel de un nodo: se asigna en función al criterio siguiente: Raíz: tiene nivel 1. Nodo tiene nivel N: sus hijos tendrán nivel N+l. El nº de niveles de un árbol es igual a la altura de su raíz, o a 0, si el árbol es vacío. Conceptos menos utilizados son: Longitud del camino externo: Suma de los niveles de cada nodo externo. Longitud del camino interno: Suma de los niveles de cada nodo interno. Componentes RAÍZ: Todos los árboles que no están vacíos tienen un único nodo raíz. Todos los demás elementos o nodos derivan o descienden de él. El nodo Raíz no tiene Padre es deci...

Árboles de expansión mínima      Un árbol de expansión mínima es un subconjunto de aristas de un grafo no dirigido que une a todos los vértices de los extremos recorriendo el camino más corto posible.  Útil para la optimización de redes, como por ejemplo una que todos conocemos: El Internet: estos arboles deben ser tomado en cuenta para poner servidores centrales que repartan ancho de banda a otras centrales pequeñas a lo largo de un país para poner los menos posibles (y ahorrar costos) y aún así tener un buen resultado. O incluso al poner servicios como agua en una colonia, la disposición de las tuberías es importante. Distribución optima de un sistema de electricidad

Los arboles binarios son especialmente útiles para ordenar datos para su posterior búsqueda, pues puede mejorar la eficiencia al buscar un elemento que de otra manera podría estar por ejemplo al final de una larga lista, con los arboles binarios es posible reducir el numero de pasos máximos con los que es posible llegar a un elemento en especifico. Por ejemplo: al ordenar una lista con muchos nombres en orden alfabético puede que sea poco eficiente llegar a alguien llamado Yordi, pues cada que uno necesite consultarlo tendría que pasar por todos los demás nombres. Esto puede ser mitigado usando un árbol de búsqueda binario Lista ordenada, para llegar a Frank hay que bajar 6 niveles Los arboles binarios son usados en aplicaciones para buscar datos eficientemente, también algunas arquitecturas de dispositivos como módems de anchos de banda altos los implementan. Árbol binario, para llegar a cualquier nombre de abajo solo hay que bajar tres niveles

Los  árboles  son por naturaleza grafos simples, sin circuitos o ciclos y no dirigidos: esto quiere decir que todas las ramas o aristas son bidireccionales y se conectan mutuamente, por lo que se les  llama grafos  conectados.    De tal manera que para que un grafo cualquiera sea considerado un  arbol   hay que  considerar 3 cosas:   1.- Es “No dirigido” no existe una arista que conecte a dos nodos que solo se  diriga  en una dirección   2.- Es simple, no contiene circuitos o ciclos: Un grafo no dirigido es un árbol si y sólo si existe una ruta  única  simple entre cualquiera dos de sus vértices.   Notémoslo  en este sencillo ejercicio: