6.4.3 Clasificación (altura, número de nodos)

Los árboles se pueden definir como un tipo restringido de grafo.

Un grafo se define de la siguente manera: Un grafoconsiste de un número de nodos (puntos o vértices) y un grupode arcos que unen parejas de nodos. A todos los pares de nodos unidos porun arco se les llama nodos adyacentes. Los arcos pueden t ener una direccióndeterminada, generando así un grafo dirigido, el cual de lo contrariosería no-dirigido. (También existen los grafos mixtos).

Por convención a los nodos de un grafo sele representa con círculos y los arcos que los conectan como líneas(no-dirigido) o flechas (dirigido).

Los árboles son entonces un subconjunto importantede los grafos, y son una herramienta útil para describir estructurasque representan algún tipo de jerarquía.

Un árbol dirigido tiene un nodo al que sele llama "raíz" y de este nodo parten todas las conexiones a losdemás nodos. A los nodos terminales se les llama "hojas" y a todoslos demás se les llama nodos intermedios.

De acuerdo al número de arcos que partende cada nodo en un árbol, este se puede clasificar en diferentescategorías. Así se tienen árboles binarios, árboles2-3-4, árboles rojo-negro, árboles B, etc.

A los nodos que dependen de otro nodo tambiénse les conoce como nodos "hijos" o descendientes y al otro se le llamanodo "padre".

De esto de puede concluir que cada nodo padre esuna raíz de un sub-árbol.

El número de sub-árboles que tieneun nodo determinan el grado del nodo. Naturalmente el grado de lashojas es de cero. Por convención al nodo raíz de arbol sele 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 caminomás largo desde el nodo hasta una hoja que sea decendiente de estenodo.
• Altura de un árbol = altura del nodo raíz.

Para poder realizar búsquedas eficientes en árbolesse manejan dos características: Los árboles pueden estarbalanceados por altura o por peso.

 

• Arbol balanceado por altura: en dóndetodos los hijos o nodos hoja se intentan mantener a la misma distanciade la raíz.
• Arbol balanceado por peso: en dónde losnodos más visitados o utilizados se mantienen a poca distancia dela raíz.