clase 3 y 4 - procesos y algoritmos.pptx

descargable

1. PROCESOS Y ALGORITMOS II LUIS FERNANDO DE PAZ SANTIZO INGENIERO EN CIENCIAS Y SISTEMAS CLASE 3 y 4

2. IMPLEMENTACIÓN DE ARBOLES

3. PM APP MEET 1 APP_X - NOMBRE = ‘’ 2 APP_X - NUMERO = 0 3 4 5 6 CADA POSICIÓN DE MEMORIA EQUIVALE A 4MB - 28 MB

4. ARBOLES BALANCEADOS Un árbol está perfectamente balanceado si su estructura es óptima con respeto al largo del camino de la raíz a cada hoja: Todas las hojas están en el mismo nivel, es decir, el largo máximo de tal camino es igual al largo mínimo de tal camino sobre todas las hojas. Esto es solamente posible cuando el número de hojas es 2 k para k ∈ Z +, en que caso el largo de todos los caminos desde la raíz hasta las hojas es exactamente k.

5. ARBOLES BALANCEADOS Necesitamos operaciones para “recuperar” la forma balanceada después de inserciones y eliminaciones de elementos, aunque no cada operación causa una falta de balance en el árbol. Estas operaciones se llaman rotaciones.

6. DETERMINAR BALANCEO El balance de un nodo en un árbol binario en general y de un árbol AVL en particular, se define como la altura de su subárbol izquierdo menos la altura de su subárbol derecho: | altura(árbol Izquierdo) - altura(árbol Derecho) | < 2 |3 - 5| = |-2| = 2 < 2 También existe la correspondiente definición simétrica: la altura de su subárbol derecho menos la altura de su subárbol izquierdo; Por convención, la altura de un árbol AVL nulo o vacío se define como -1.

7. ARBOLES BALANCEADOS La rotación adecuada está elegida según las alturas de los ramos que están fuera de balance, es decir, tienen diferencia de altura mayor o igual a dos. Si se balancea después de cada insercion y eliminación siempre y cuando es necesario, la diferencia será siempre exactamente dos.

8. (paso 1)  k1 = k2.hijoIzquierdo (paso 2)  k2.hijoIzquierdo = k1.hijoDerecho (paso 3)  k1.hijoDerecho = k2 (paso 4)  retornar K1 para que tome el lugar anterior de K2 en el árbol nodo K1 tomar el valor del hijo izquierdo de la raíz El hijo izquierdo de la raíz será el hijo derecho de k1 El hijo derecho de k1 será el nodo raíz