Árbol avl
Páginas: 4 (872 palabras)
Publicado: 16 de enero de 2012
DEFINICIÓN TIPOS DE ROTACIONES INSERCIÓN DE NODOS ELIMINACIÓN DE NODOS
Lorena Reyes González
Ing. Informática
• Un árbol AVL es un árbol binario de búsqueda que cumple con lacondición de que la diferencia entre las alturas de los subárboles de cada uno de sus nodos es, como mucho 1. La denominación de árbol AVL viene dada por los creadores de tal estructura (Adelson-Velskiiy Landis).
• Reestructurar un árbol balanceado significa rotar los nodos del mismo. La rotación puede ser simple o compuesta. En el primer tipo de rotación se involucran dos nodos y en el segundo,se afectan tres. Si la rotación es simple puede realizarse por las ramas derechas (RDD: Rotación Derecha Derecha) o por las ramas izquierdas (RII : Rotación Izquierda Izquierda). Si la rotación escompuesta puede realizarse por las ramas izquierda y derecha (RDI: Rotación Derecha Izquierda) por las ramas izquierda y derecha (RID: Rotación Izquierda Derecha).
De un árbol de raíz (r) y dehijos izquierdo (i) y derecho (d), lo que haremos 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 hijoderecho 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).
De un árbol deraí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 hijoizquierdo construimos 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).
La Rotacióndoble a la Derecha son dos rotaciones simples, primero rotación simple izquierda y luego rotación simple derecha.
La Rotación doble a la Izquierda son dos rotaciones simples, primero rotación...
DEFINICIÓN TIPOS DE ROTACIONES INSERCIÓN DE NODOS ELIMINACIÓN DE NODOS
Lorena Reyes González
Ing. Informática
• Un árbol AVL es un árbol binario de búsqueda que cumple con lacondición de que la diferencia entre las alturas de los subárboles de cada uno de sus nodos es, como mucho 1. La denominación de árbol AVL viene dada por los creadores de tal estructura (Adelson-Velskiiy Landis).
• Reestructurar un árbol balanceado significa rotar los nodos del mismo. La rotación puede ser simple o compuesta. En el primer tipo de rotación se involucran dos nodos y en el segundo,se afectan tres. Si la rotación es simple puede realizarse por las ramas derechas (RDD: Rotación Derecha Derecha) o por las ramas izquierdas (RII : Rotación Izquierda Izquierda). Si la rotación escompuesta puede realizarse por las ramas izquierda y derecha (RDI: Rotación Derecha Izquierda) por las ramas izquierda y derecha (RID: Rotación Izquierda Derecha).
De un árbol de raíz (r) y dehijos izquierdo (i) y derecho (d), lo que haremos 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 hijoderecho 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).
De un árbol deraí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 hijoizquierdo construimos 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).
La Rotacióndoble a la Derecha son dos rotaciones simples, primero rotación simple izquierda y luego rotación simple derecha.
La Rotación doble a la Izquierda son dos rotaciones simples, primero rotación...
Leer documento completo
Regístrate para leer el documento completo.