…Sabia que algún dia iba a ocupar los grafos. ¡Lo sabía!

Los arboles son casi casi crear un grafo en una computadora, así que antes que nada tengo algo que decirte:

Esta lección no la empezaré desde cero, pues voy a suponer que ya sabes que son los grafos, al menos lo básico, así que ve y revisa esta lección primero:

MD: ¿Qué son los Grafos?

Ok, con esto fuera del camino es hora de que empecemos:

Árboles

 

Estas son esencialmente diferentes a las listas y todas sus parientes. Esta estructura no es lineal (Osea que puede haber nodos que apunten a más de un elemento).

Estos son básicamente estructuras para guardar información en una jerarquía, son utilizadas en las bases de datos o para hacer un árbol de carpetas dentro de una computadora.

Al principio se parecen, volveremos a crear un nodo como antes:

---

Nodos

Vamos a meter cada información que queramos guardar en la pila en un nodo, esto es un nodo:

El nodo tiene dos partes:

1. Dato: Representa el dato a almacenar. Puede ser de cualquier tipo.
2. Enlaces:Los arboles son como listas, pero tienen nodos, con s, son varios.

---

¿Qué es un árbol?

Así una árbol no es más que esto, un montón de nodos unidos. (Hasta se ve sencillo si lo ves así). En Matemáticas Un árbol es un grafo que:

• Es dirigido (Osea en enlace en el nodo tiene un «origen y una dirección»).
• Es conexo (Eso quiere decir que no existen nodos «perdidos» o inaccesibles desde la raíz, es decir que en un árbol puedo llegar  a cualquier nodo desde la raíz).
• Todos los vértices tienen grado de entrada 1 excepto  un vértice (Eso quiere decir que en «español» que cualquier nodo tiene un solo padre, y que solo es posible llegar a ese nodo a través de ese padre; PD: Ese que no tiene grado de entrada se llama raíz).
• No puedes tener ciclos: Ósea regresar a un nodo si ya habías pasado por ahí

Así que veámoslo gráficamente:

• Raíz: Es el nodo al que no es apuntado por nada, es el origen del árbol…digo, por algo se llama raíz.
• Hoja: Es la punta del árbol, no apuntan a nada, no tienen hijos.

Nivel: Es el numero de «saltos» que tengo que hacer para llegar a el nodo indicado.

Podemos finalmente hablar de un último concepto:

Orden: Orden es el número MAXIMO de hijos que puede tener un nodo.

---

Árboles Binarios

Los árboles binarios son mis favoritos, son muy my poderosos, pero ¿Porque me deberían de interesar?

El tema de localizar elemento es muy interesante porque son lo que se utiliza en cosas como las bases de datos, pues con su estructura son capaces de encontrar lo que nosotros le pidamos demasiado rápido.

¿No me crees?

Imagínate un montón de nombres, por ejemplo en una guía telefónica o una base de datos, si fuera un árbol binario (BTS) por ejemplo podría encontrar cualquier elemento de una base tan grande como una de 32,000 nombres en menos de 15 comparaciones. Si, 15 pasos y puedo encontrar a más de 32,000 personas, con 30 comparaciones puedo encontrar hasta 1,073,741,824 nombres. ¡Asombroso! …Pero ¿Cómo lo hacen?

¡Ya lo veremos!

Pero bueno, sigamos, sus características son sencillas:

• Tienes Orden 2 ó máximo 2 hijos, como ustedes quieran verlo.
• Se distingue entre hijo derecho o izquierdo

 

 

---

Tipos de Árboles

 

Full Binary Tree Todos los nodos o son hojas o tienen 2 hijos. Esa es la única condición.

Complete Binary Tree Si ignoras el último nivel es un Perfect Tree. Si hay UN solo hijo en el ultimo nivel tiene que irse llenando de IZQUIERDA A DERECHA

Perfect Tree Es un árbol en el que todos sus nodos o tienen dos hijos o sin hojas y que esta completo INCLUYENDO el último nivel, son preciosos.

Conceptos:

• Un Árbol es degenerado si solo tiene un hijo.

Así que bueno, con esto terminamos por hoy, si, se que es mucho, imagínate a mi inocente cuando pensé que podía meter todo lo de Árboles en una lección. Inocente yo.