Ingeniero Sistemas
Páginas: 2 (365 palabras)
Publicado: 5 de junio de 2013
UNIVERSIDAD MARIANO GALVEZ
Arboles AVL
Los arboles AVL, son arboles binarios de búsqueda siempre tratan de mantener un equilibrio para todos sus nodos, los nodos de izquierda y derecha nodifieren en más de 1.
El nombre AVL proviene de las siglas de los nombres de sus inventores Adelson-Velskii y Landis
No son arboles perfectamente equilibrados, pero siempre mantienen un equilibrio paraun comportamiento bastante bueno para que garantice una búsqueda óptima.
Para conseguir un equilibrio optimo, la inserción y el borrado de los nodos se realiza de forma especial y no se realiza elproceso correcto se pierde el equilibrio, este método de inserción y borrado se realiza en serie de rotaciones de los nodos.
ROTACIONES DE ARBOLES
El equilibrio se produce de abajo hacia arriba sobrelos nodos en que se produce el desequilibrio, pueden darse dos casos de rotación simple o doble.
Rotación simple a la derecha
Un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo queharemos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrácomo raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).
Rotación simple a la izquierda
De un árbol de raíz(r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdoconstruimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) y el hijo izquierdo será el hijo izquierdo del árbol (i).
Precondición: Tieneque tener hijo derecho no vacío.
Rotación doble a la derecha
La Rotación doble a la Derecha son dos rotaciones simples, primero rotación simple izquierda y luego rotación...
Arboles AVL
Los arboles AVL, son arboles binarios de búsqueda siempre tratan de mantener un equilibrio para todos sus nodos, los nodos de izquierda y derecha nodifieren en más de 1.
El nombre AVL proviene de las siglas de los nombres de sus inventores Adelson-Velskii y Landis
No son arboles perfectamente equilibrados, pero siempre mantienen un equilibrio paraun comportamiento bastante bueno para que garantice una búsqueda óptima.
Para conseguir un equilibrio optimo, la inserción y el borrado de los nodos se realiza de forma especial y no se realiza elproceso correcto se pierde el equilibrio, este método de inserción y borrado se realiza en serie de rotaciones de los nodos.
ROTACIONES DE ARBOLES
El equilibrio se produce de abajo hacia arriba sobrelos nodos en que se produce el desequilibrio, pueden darse dos casos de rotación simple o doble.
Rotación simple a la derecha
Un árbol de raíz (r) y de hijos izquierdo (i) y derecho (d), lo queharemos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i’) y como hijo derecho construimos un nuevo árbol que tendrácomo raíz, la raíz del árbol (r), el hijo derecho de i (d’) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d).
Rotación simple a la izquierda
De un árbol de raíz(r) y de hijos izquierdo (i) y derecho (d), consiste en formar un nuevo árbol cuya raíz sea la raíz del hijo derecho, como hijo derecho colocamos el hijo derecho de d (nuestro d’) y como hijo izquierdoconstruimos un nuevo árbol que tendrá como raíz la raíz del árbol (r), el hijo izquierdo de d será el hijo derecho (i’) y el hijo izquierdo será el hijo izquierdo del árbol (i).
Precondición: Tieneque tener hijo derecho no vacío.
Rotación doble a la derecha
La Rotación doble a la Derecha son dos rotaciones simples, primero rotación simple izquierda y luego rotación...
Leer documento completo
Regístrate para leer el documento completo.