balanceo de arboles

Instituto Politécnico Nacional

Escuela Superior de Ingeniería Mecánica y Eléctrica

Estructuras y Base de Datos
“Balanceo de Arboles, Recursividad, Factorial y Exponencial”





BALANCEO DE ARBOLES
Árboles Balanceados


Balanceo de árboles binarios.

Mantener un árbol perfectamente balanceado es muy costoso, entoncesseadopta un concepto menos estricto de balanceo: árboles balanceados (equilibrados).Un árbol está balanceado si para cada uno de sus nodos se tiene que las alturas de sus dos sub árboles difieren a lo más en 1. Se tiene que un árbol perfectamente balanceado es también balanceado; pero no es cierto lo contrario. Para estos árboles el mantenimiento del balanceo no es muy costoso, y las operaciones de búsqueda, inserción y borrado mantienen su orden O(log2n).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.
Arbol balanceado por peso: en dónde los nodos más visitados outilizados se mantienen a poca distancia de la raíz. Un árbol es un grafo conexo y sin ciclos.
Propiedades:
Si G = (V,A) es un árbol de n vértices, entonces:
1)Para todo par de vértices x e y existe un único camino de x a y.
2) Todas las aristas de G son puentes.
3) ½ A½ = n - 1.
4) Todo árbol tiene al menos dos hojas (vértices de grado uno).
Caracterizaciones:
Un grafo G=(V,A) es un árbol Û Para todo par de vértices x e y existe un único camino de x a y Û G es conexo y todas las aristas son puentes Û G es acíclico y maximal (la adición de una aristanueva origina un ciclo) Û G es conexo y ½ A½ = n - 1 Û G es acíclico y ½ A½ = n – 1. Los árboles forman una de las subclases de las gráficas de uso más amplio. En el terreno de la computación los árboles sirven para organizar y relacionar los datos de una base de datos
Cuando se estudiaron los arboles binarios de búsqueda se menciono que es una estructura sobre la cual se pueden realizareficientemente las operaciones de búsqueda, inserción y eliminación. Sin embargo, si el árbol crece o decrece descontroladme, el rendimiento puede disminuir considerablemente. El caso más desfavorable se produce cuando se inserta un conjunto de claves ordenadas en forma ascendente o descendente.
Es de notar que el número promedio de comparaciones que se deben realizar para localizar una determinadaclave en un árbol binario de búsqueda con crecimiento descontrolado es N/2, cifra que muestra un rendimiento muy pobre en la estructura.
Con el objeto de mantener la eficiencia en la operación de búsqueda surgen los arboles balanceados. La principal característica de estos es la de realizar reacomodos o balanceos, después de inserciones o eliminaciones de elementos. Estos árboles reciben el nombrede AVL en honor a sus inventores, dos matemáticos rusos, G. M. Adelson-Velskii y E. M. Landis.


Formalmente se define un árbol balanceado como un árbol binario de búsqueda, en el cual se debe cumplir la siguiente condición: Para todo nodo T del árbol, la altura de los subárbols izquierdo y derecho no deben diferir en más de una unidad.

Donde  HRI es la altura de la rama o subárbol izquierdoy HRD  es la altura de la rama o subárbol derecho.
Los arboles balanceados se parecen mucho, en su mecanismo de formación, a los números Fibonacci. El árbol de altura 0 es vacío, el árbol de altura 1 tiene un único nodo y, en general, el número de nodos del árbol con altura h  > 1 se calcula aplicando la siguiente formula recursiva:

- donde K indica el número de nodos del árbol y h la altura.Por otra parte, algunos estudios demuestran que la altura de un árbol balanceado de n nodos nunca excederá de 1.44 * log n.

Inserción en árboles balanceados

Al insertar un elemento en un árbol balanceado se deben distinguir los siguientes casos:

1. Las ramas izquierda (RI) y derecha (RD) del árbol tienen la misma altura (HRI = HRD) por lo tanto:
       1.1  Si se inserta un...