Un grafo se define de la siguiente manera: Un grafo consiste de un número de nodos (puntos o vértices) y un grupo de arcos que unen parejas de nodos. A todos los pares de nodos unidos por un arco se les llama nodos adyacentes. Los arcos pueden tener una dirección determinada, generando así un grafo dirigido, el cual de lo contrario sería no-dirigido. (También existen los grafos mixtos).
Por convención a los nodos de un grafo se le representa con círculos y los arcos que los conectan como líneas(no-dirigido) o flechas (dirigido).
Los árboles son entonces un subconjunto importante de los grafos, y son una herramienta útil para describir estructuras que representan algún tipo de jerarquía.
Un árbol dirigido tiene un nodo al que se le llama "raíz" y de este nodo parten todas las conexiones a los demás nodos. A los nodos terminales se les llama "hojas" y a todos los demás se les llama nodos intermedios.
De acuerdo al número de arcos que parten de cada nodo en un árbol, este se puede clasificar en diferentes categorías. Así se tienen árboles binarios, árboles 2-3-4, árboles rojo-negro, árboles B, etc.
A los nodos que dependen de otro nodo también se les conoce como nodos "hijos" o descendientes y al otro se le llama nodo "padre".
De esto de puede concluir que cada nodo padre es una raíz de un sub-árbol.
El número de sub-árboles que tiene un nodo determinan el grado del nodo. Naturalmente el grado de las hojas es de cero. Por convención al nodo raíz de árbol se le considera el nivel cero del árbol.
Cuando se tienen varios árboles en un conjunto,al conjunto se le llama bosque.
Altura de un nodo: Es la longitud del camino más largo desde el nodo hasta una hoja que sea descendiente de este nodo.
Altura de un árbol = altura del nodo raíz.
Para poder realizar búsquedas eficientes en árboles se manejan dos características: Los árboles pueden estar balanceados por altura o por peso.
Árbol balanceado por altura: en dónde todos los hijos o nodos hoja se intentan mantener a la misma distancia de la raíz.
Árbol balanceado por peso: en dónde los nodos más visitados o utilizados se mantienen a poca distancia de la raíz.
Tipos de Árboles:
Árboles binarios
Un árbol binario representado con nodos ligados:
Como lo indica su nombre, estos árboles estan formados por nodos que pueden tener un máximo de 2 hijos.
DEFINICIONES :
Arbol relleno : Cuando todo nodo tiene 2 hijos o bien es hoja.
Arbol binario completo : Un arbol binario relleno en dónde todas las hojas tienen la misma profundidad.
Métodos para recorrer un árbol binario:
a) Pre-orden (preorder) :
Primero se recorre la raíz
Segundo se recorre el subárbol izquierdo en pre-orden
Tercero se recorre el subárbol derecho en pre-orden
b) En-orden (inorder)
Primero se recorre el subárbol izquierdo en-orden
Segundo se recorre la raíz
Tercero se recorre el subárbol derecho en-orden
c) Post-orden (postorder)
Primero se recorre el subárbol izquierdo en post-orden
Segundo se recorre el subárbol derecho en post-orden
Tercero se recorre la raiz
Intercambiando izquierda por derecha en los tres métodos anteriores se obtienen tres métodos a los cuales se les llama :
Pre-orden converso
En-orden converso
Post-orden converso
No hay comentarios:
Publicar un comentario