Apunte Avl En C++
Páginas: 7 (1641 palabras)
Publicado: 29 de mayo de 2012
Arboles Binarios: revision previa de definiciones
Arbol binario de busqueda:
Es una estructura de datos formada por nodos, cada uno de los cuales tiene a lo sumo dos hijos, con un nodo distinguido llamado raíz, y las claves almacenadas sin repeticiones y totalmente ordenadas.
La definicion recursiva de un árbol binario de búsqueda (ABB o BST, de ‘binary search tree’) especifica que obien es nulo o bien consta de un nodo que contiene una clave y dos subárboles hijos, izquierdo y derecho, que son árboles binarios de búsqueda.
Para cada nodo del ABB se verifica que las claves del subárbol izquierdo son menores que la clave del nodo padre, y esta clave es menor que las de su subárbol derecho.
Un árbol binario de búsqueda balanceado por su altura con diferencia 1 es aquelpara el cual para todo nodo se verifica que la diferencia de alturas entre la altura de su subárbol izquierdo y la altura de su subárbol derecho es menor o igual que 1.
Arboles AVL:
Los arboles AVL (Adelson-Velskii y Landis desarrollaron los algoritmos) son ABB balanceados por su altura que usan ciertas rotaciones para rebalancear el ABB cuando es necesario.
Estas estructuras agreganen los nodos una variable FB, el factor de balanceo, que permite determinar si es necesario realizar una rotación luego de una alta o una baja.
Alta en un arbol AVL:
La primera parte se realiza como en la forma habitual en un ABB.
Luego se procede a recalcular los valores de los FB.
El nodo más próximo a aquel que con su alta produjo el desbalanceo, se llama pivote. Las rotaciones arealizar son reasignaciones en función de las características del esquema en el cual ha quedado el pivote y el nuevo nodo.
Las rotaciones posibles son:
Rotaciones simples:
Rotación Simple a derecha (DD o RR)
Rotación Simple a izquierda(II o LL)Rotaciones dobles
Rotación Doble derecha izquierda(DI o RL o RDI)
Rotación Doble izquierdaderecha (ID o LR o RID)
Rotacion simple a derecha (DD o RR)
En los siguientes gráficos se presenta la situación de desbalanceo y su resolución. En rojo se ha coloreado el nodo pivote.En negro, el nodo que produjo el desbalance. En verde, los punteros involucrados en el rebalanceo.
Ejemplo:
En el siguiente árbol, la inserción del 50 produce un desbalanceo.
[pic]
El rebalanceo con DD da como resultado este árbol:
[pic]
Caso II o LL o RSI:
Enlas rotaciones simples la altura del árbol vuelve a ser la que tenia antes de la inserción.
La búsqueda del pivote se hace en el subárbol que se desequilibra siguiendo el camino a la raíz.
Rotaciones dobles:
Caso DI o RL o RDI:
Las rotaciones dobles tienen dos variantes: la trivial y la no trivial, y la primera forma no puede reducirse a la segunda.
Caso DI trivial:Caso DI no trivial:
Ejemplo:
[pic] [pic]
Caso rotacion doble ID
Caso ID trivial:
Caso ID no trivialEjemplo:
En el siguiente árbol
[pic]
Se agrega un nodo con clave 55 y se produce un desbalanceo, con pivote en 100
[pic]
El rebalanceo se lleva a cabo con una rotación doble ID; el árbol queda así:
[pic]
Borrados en un AVL
Cuando se lleva acabo un borrado, el desequilibrio se produce cuando la eliminación de un nodo trae como...
Arbol binario de busqueda:
Es una estructura de datos formada por nodos, cada uno de los cuales tiene a lo sumo dos hijos, con un nodo distinguido llamado raíz, y las claves almacenadas sin repeticiones y totalmente ordenadas.
La definicion recursiva de un árbol binario de búsqueda (ABB o BST, de ‘binary search tree’) especifica que obien es nulo o bien consta de un nodo que contiene una clave y dos subárboles hijos, izquierdo y derecho, que son árboles binarios de búsqueda.
Para cada nodo del ABB se verifica que las claves del subárbol izquierdo son menores que la clave del nodo padre, y esta clave es menor que las de su subárbol derecho.
Un árbol binario de búsqueda balanceado por su altura con diferencia 1 es aquelpara el cual para todo nodo se verifica que la diferencia de alturas entre la altura de su subárbol izquierdo y la altura de su subárbol derecho es menor o igual que 1.
Arboles AVL:
Los arboles AVL (Adelson-Velskii y Landis desarrollaron los algoritmos) son ABB balanceados por su altura que usan ciertas rotaciones para rebalancear el ABB cuando es necesario.
Estas estructuras agreganen los nodos una variable FB, el factor de balanceo, que permite determinar si es necesario realizar una rotación luego de una alta o una baja.
Alta en un arbol AVL:
La primera parte se realiza como en la forma habitual en un ABB.
Luego se procede a recalcular los valores de los FB.
El nodo más próximo a aquel que con su alta produjo el desbalanceo, se llama pivote. Las rotaciones arealizar son reasignaciones en función de las características del esquema en el cual ha quedado el pivote y el nuevo nodo.
Las rotaciones posibles son:
Rotaciones simples:
Rotación Simple a derecha (DD o RR)
Rotación Simple a izquierda(II o LL)Rotaciones dobles
Rotación Doble derecha izquierda(DI o RL o RDI)
Rotación Doble izquierdaderecha (ID o LR o RID)
Rotacion simple a derecha (DD o RR)
En los siguientes gráficos se presenta la situación de desbalanceo y su resolución. En rojo se ha coloreado el nodo pivote.En negro, el nodo que produjo el desbalance. En verde, los punteros involucrados en el rebalanceo.
Ejemplo:
En el siguiente árbol, la inserción del 50 produce un desbalanceo.
[pic]
El rebalanceo con DD da como resultado este árbol:
[pic]
Caso II o LL o RSI:
Enlas rotaciones simples la altura del árbol vuelve a ser la que tenia antes de la inserción.
La búsqueda del pivote se hace en el subárbol que se desequilibra siguiendo el camino a la raíz.
Rotaciones dobles:
Caso DI o RL o RDI:
Las rotaciones dobles tienen dos variantes: la trivial y la no trivial, y la primera forma no puede reducirse a la segunda.
Caso DI trivial:Caso DI no trivial:
Ejemplo:
[pic] [pic]
Caso rotacion doble ID
Caso ID trivial:
Caso ID no trivialEjemplo:
En el siguiente árbol
[pic]
Se agrega un nodo con clave 55 y se produce un desbalanceo, con pivote en 100
[pic]
El rebalanceo se lleva a cabo con una rotación doble ID; el árbol queda así:
[pic]
Borrados en un AVL
Cuando se lleva acabo un borrado, el desequilibrio se produce cuando la eliminación de un nodo trae como...
Leer documento completo
Regístrate para leer el documento completo.