Árboles I: La Amenaza Fantasma

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

g53Los 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

 

arbolEstas 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.

arbol


¿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.
raiz-hoja

Raiz- Hoja

padreshijos

Padres e Hijos

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

nivel-arbol

Nivel de un árbol

Podemos finalmente hablar de un último concepto:

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


Árboles Binarios

g53.pngLos á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.

output_Y95Fjl

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

Complete

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.

perfect

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.

btn1 btn
btn

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s