Recorridos en un Árbol

Según sea la estrategia a seguir, los recorridos se conocen como enorden (inorder), preorden (peorder) y postorden(postorder):
Preorden (nodo-izquierdo-derecho)(NID)
Enorden (izquierdo-nodo-derecho)(IND)
Postorden (izquierdo-derecho-nodo)(IDN)

Recorrido Preorden:

El recorrido preorden(NID) conlleva los siguientes pasos, en los que el nodo raíz va antes que los subárboles:
1.- Visitar el nodo raíz (N)
2.- Recorrer el subárbol izquierdo (I) en preorden
3.- Recorrer el sub{árbol derecho (D) en preorden.

Recorrido en Orden:

El recorrido enorden (inorder) procesa primero el suárbol izquierdo, después el raíz y a continuación el subárbol derecho. El significado de in- es que la raíz se procesa entre los subárboles.
Si el árbol no está vacío, el método implica los siguientes pasos:
1.- Recorrer el subárbol izquierdo (I) en inorden.
2.- Visitar el nodo raíz (N)
3.- Recorrer el subárbol derecho (D) en inorden.

Recorrido Postorden:

El recorrido postorden (IDN) procesa el nodo raíz (post) después de que los subárboles izquierdo y derecho se han procesado. Se comienza situándose en la hoja más a la izquierda y se procesa. A continuación se procesa su subárbol derecho. Por último se procesa el nodo raíz. Las etapas del algoritmo, si el árbol no está vacío son:

1.- Recorrer el subárbol izquierdo (I) en postorden.
2.- Recorrer el subárbol derecho (D) en postorden.
3.- Visitar el nodo raíz (N).

.

Más sobre arboles binarios

Árboles Binarios Completos:

Un árbol binario completo de profundidad n es un árbol en el que para cada nivel, del 0 al nivel n-1 tiene un conjunto lleno de nodos y todos los nodos hoja a nivel n ocupan las posiciones más a la izquierda del árbol.
Un árbol binario completo que contiene 2n nodos a nivel n es un árbol lleno.
Un árbol lleno es un árbol binario que tiene el máximo número de entradas para su altura. Esto sucede cuando el último nivel está lleno.

Estructura de un Árbol Binario:

La estructura de un árbol binario se construye con nodos. Cada nodo debe contener el campo dato (datos a almacenar) y dos campos de tipo puntero, uno al subárbol izquierdo y otro al subárbol derecho, que se conocen como puntero izquierdo y puntero derecho respectivamente,
Un valor NULL indica un árbol o un subárbol vacío

Arboles Binarios

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles.
En un árbol binario, cada nodo puede tener cero, uno o dos hijos (subárboles).
Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Un árbol binario es una estructura recursiva. Cada nos es la raíz de su propio subárbol y tiene hijos, que son raíces de árboles llamados subárboles derecho e izquierdo del nodo, respectivamente. Un árbol binario se divide en tres subconjuntos:
{R} Nodo raíz
{I1,I2,…,In} Subárbol izquierdo de R
{D1,D2,…,Dn} Subárbol derecho de R.


Equilibrio

La distancia de un nodo al nodo raíz determina la eficiencia con la que puede ser localizado.
Por ejemplo, dado cualquier nodo de un árbol, a sus hijos se puede acceder siguiendo sólo un camino de bifurcación o de ramas, el que conduce al nodo deseado. De modo similar, los nodos a nivel 2 un árbol sólo pueden ser accedidos siguiendo sólo dos ramas del árbol.

Si la altura del subárbol izquierdo es h, y la altura del subárbol derecho es hD, entonces el factor de equilibrio del árbol B se determina por la siguiente fórmula.

B= hD –hI
Un árbol está perfectamente equilibrado si su equilibrio o balance es cero, y sus subárboles son también perfectamente equilibrados. Dado que esta definición ocurre raramente se aplica una definición alternativa.
Un árbol binario está equilibrado si la altura de sus subárboles difiere en no más de uno (su factor de equilibrio es -1, 01, +1) y sus subárboles son también equilibrados.

.

Operaciones Arbol AVL

Inserción:
La inserción en un árbol de AVL puede ser realizada insertando el valor dado en el árbol como si fuera un árbol de búsqueda binario desequilibrado y después retrocediendo hacia la raíz, rotando sobre cualquier nodo que pueda haberse desequilibrado durante la inserción.


Proceso de inserción:

1.buscar hasta encontrar la posición de inserción o modificación (proceso idéntico a inserción en árbol binario de búsqueda)
2.insertar el nuevo nodo con factor de equilibrio “equilibrado”
3.desandar el camino de búsqueda, verificando el equilibrio de los nodos, y re-equilibrando si es necesario

Rotaciones:

Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.
El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse dos casos: rotación simple o rotación doble; a su vez ambos casos pueden ser hacia la derecha o hacia la izquierda.

.

Arbol AVL

Es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó. [(AVL) Adelson-Velskii y Landis]

Características:

• Están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa
• La complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n)
• La inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.

Factor de equilibrio:

El factor de equilibrio es la diferencia entre las alturas del árbol derecho y el izquierdo:
FE = altura subárbol derecho - altura subárbol izquierdo; Por definición, para un árbol AVL, este valor debe ser -1, 0 ó 1.

Si el factor de equilibrio de un nodo es: 0 -> el nodo está equilibrado y sus subárboles tienen exactamente la misma altura. 1 -> el nodo está desequilibrado y su subárbol derecho es un nivel más alto. -1 -> el nodo está desequilibrado y su subárbol izquierdo es un nivel más alto.
Si el factor de equilibrio Fe≥2 o Fe≤-2 es necesario reequilibrar.

.

Arboles

El árbol es una estructura muy usada en todos los ámbitos de la informática ya que se adapta a la representación natural de informaciones homogéneas organizadas y de una gran comodidad y rapidez de manipulación. Las estructuras tipo árbol se usan para representar datos con una relación jerárquica entre sus elementos, como son árboles genealógicos, tablas, etc

CARACTERSTCAS:

Un árbol se define como un conjunto finito de uno o más nodos relacionados de la siguiente forma:

• Hay un nodo especial llamado raíz del árbol, que proporciona un punto de entrada a la estructura.
• Los nodos restantes se subdividen en conjuntos disjuntos, cada uno de los cuales es a su vez un árbol. (Recursividad) Estos árboles se llaman subárboles del raíz.

La representación y terminología de los árboles se realiza con las típicas notaciones de las relaciones familiares en los árboles genealógicos: padre, hijo, hermano, ascendiente, descendiente.

Junto a estos conceptos se definen otros tales como raíz, nodo, hoja, camino, nivel, profundidad, etc.

PARTES DE UN ARBOL:

Longitud de caminos interno y externo

Se define como la longitud de camino del nodo X como el numero de arcos q se deben recorrer para llegar desde la raíz hasta el nodo X.
La raíz tiene longitud de camino 1, sus descendientes directos longitud de camino 2 y así sucesivamente.

.

Ordenamiento Shell (codigo)

En el método se propone que las comparaciones se efectúen con saltos de mayor tamaño, pero con incrementos que sean saltos de mayor tamaño pero con incrementos decrecientes, así los elementos quedarán ordenados en el arreglo.

Pseudocódigo

INT, I y AUX son variables de tipo entero. BAND es una variable de tipo booleano)
1.- Hacer INT ? N +1.
2.- Mientras (INT > 1) Repetir
Hacer INT ? parte entera (INT /2) y BAND? VERDADERO.
2.1.- Mientras (BAND == VERDADERO) Repetir.
Hacer BAND ? FALSO e I ? 1.
2.1.1.- Mientras ((I + INT) <= N) Repetir.
2.1.1.1.- Si A [I] > A[I + INT] Entonces.
Hacer AUX ? A[I], A[I] ? A[I + INT], A[I + INT] ? AUX y
BAND ? VERDADERO.
2.1.1.2.- {Fin del condicional del paso 2.1.1.1}
Hacer I ? I + 1.
2.1.2.- {Fin del ciclo del paso 2.1.1}
2.2.- { Fin del ciclo del paso 2.1}
3.- { Fin del ciclo del paso 2}