Arboles

1. Concepto: 

 Estructura de datos no lineal para organización de información por niveles.

2. Utilidad:

 Organización por jerarquía (diferenciación entre elementos mayores y menores).

3. Aplicaciones:

Estructura organizacionales, genealogía, directorias, expresiones aritméticas, búsqueda y ordenadamente.

4. Terminología:

                     

Nodo: cada componente de un árbol, la comunicación es descendente, raíz hacia las hojas.

Tipos

Implementacion 

ÁRBOLES BINARIOS

1. Concepto: 

 Máximo dos hijos por nodo.            

2. Terminología:

Completo: todos los nodos tienen dos o cero hijos.

Balanceado: la diferencia entre las alturas de los subárboles para todos los nodos es de cero o uno.

Degenerado: todos los nodos solo tienen un descendiente excepto la hoja.

Lleno: todos los niveles tienen el máximo de nodos 2^h-1.

Implementación:

Recorrido

REFLEXIÓN: Es posible definir un árbol binario como un conjunto de finitos elementos, el cual consta de una raíz la cual esta conformado por dos subárboles: derecho e izquierdo.

ÁRBOL DE EXPRESIONES

Es un árbol binario completo, que se utiliza para representar y evaluar expresiones aritméticas donde las hojas son los operandos y el resto de nodos los operadores.

REFLEXIÓN: un árbol de expresión tiene una funcionalidad similar a la de una aplicación aritmética de pilas ya que ordenan los elementos teniendo en cuenta las prioridades. 

Nota: el recorrido en un árbol de expresión el preorden produce la expresión prefija, el inorden la infija y el posorden posfija 

ÁRBOLES ABB: ÁRBOL BINARIO DE BÚSQUEDA

1.CONCEPTO:

Contienen un algoritmo que permite ordenar y hacer más eficiente el proceso de búsqueda que en las estructuras vistas anteriormente.

Ventajas: 

- Mayor eficiencia.

- Menor número de comparaciones al buscar un elemento.

-El proceso de búsqueda a medida que se avanza se hace un descarte del 50%.

CRITERIO:

Para todos los nodos, los datos en el subárbol izquierdo deben ser menores y los del subárbol derecho mayores.

OPERACIONES EN ABB:

INSERCIÓN: se debe buscar el sitio de inserción, verificar que no exista el elemento.

ELIMINACIÓN: Buscar y verificar que exista el elemento.

- Si es una hoja solo se debe suprimir.

- Si es un nodo con un subárbol, es reemplazado por su descendiente inmediato.

- Si es un nodo con dos subárboles, se reemplaza con el nodo más a la izquierda del subárbol derecho o con el nodo más a la derecha del subárbol izquierdo.

BUSCAR: Inicia en la raíz comparando el dato si es mayor se desplaza a la derecha si es menor a la izquierda y si es igual el elemento ha sido encontrado.

REFLEXIÓN: Son árboles binarios en los que se cumple que cada nodo, el valor del elemento de la raíz del subárbol izquierdo es menor que el valor del elemento del nodo y también que el valor del elemento de la raíz del subárbol derecho es mayor.

ÁRBOLES BINARIOS BALANCEADOS (AVL)

Insertar: Se aplica inicialmente la misma de los ABB pero adicionalmente se calcula el FE en la rama de inserción, comenzando por la hoja y subimos a la raíz, si se encuentra en un nodo "FE=0" o llegamos a la raíz con FE normal en balance paramos, si un nodo presenta FE fuera de rango de balance, se produce una reestructuración del árbol dependiendo de los siguientes casos.

Eliminar: se aplica la misma regla  ABB pero adicionalmente se calcula el FE en la rama de eliminación e igual que en la inserción si se presenta un caso de rotación se hace la respectiva reestructuración del árbol.

REFLEXIÓN: En conclusión es posible decir que un árbol AVL es aquel que tiene como condición  de que la diferencia entre las alturas de sus subárboles debe ser máximo de 1.

Además el factor de equilibro determina en que momento se debe realizar una reestructuración, es decir si es diferente de -1, 0 ó 1.