Arboles AVL Rotaciones

42 %
58 %
Information about Arboles AVL Rotaciones
ing

Published on October 29, 2007

Author: evansbv

Source: slideshare.net

Description

Arboles AVL Rotaciones

ESTRUCTURA DE DATOS II ROTACIONES EN ÁRBOLES AVL UNIVERSIDAD AUTONOMA GABRIEL RENE MORENO FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIA PROFESOR: Ing. Evans Balcazar Veizaga

PROFESOR:

Ing. Evans Balcazar Veizaga

Rotaciones de Nodos   : Los reequilibrados se realizan mediante rotaciones, en el siguiente punto veremos cada caso, ahora vamos a ver las cuatro posibles rotaciones que podemos aplicar y son Simples y Dobles. Rotación simple a la derecha (SD): Rotación simple a la izquierda (SI): Rotación doble a la derecha (DD): Rotación doble a la izquierda (DI):

Los reequilibrados se realizan mediante rotaciones, en el siguiente punto veremos cada caso, ahora vamos a ver las cuatro posibles rotaciones que podemos aplicar y son Simples y Dobles.

Rotación simple a la derecha (SD):

Rotación simple a la izquierda (SI):

Rotación doble a la derecha (DD):

Rotación doble a la izquierda (DI):

AVL – Definición Formal: Definición del altura de un árbol Sea T un árbol binario de búsqueda y sean Ti y Td sus subárboles, su altura H ( T ), es: 0 si el árbol T está vacío 1 + max( H ( Ti ), H ( Td )) si no lo está Definición de árbol AVL Sea T un árbol binario de búsqueda con Ti y Td siendo sus subárboles izquierdo y derecho respectivamente, tenemos que: Si T es vacío, es un árbol AVL Si T es un ABB no vacío, es AVL si (si y sólo si): Ti y Td son AVL y H ( Ti ) − H ( Td ) = − 1, 0 ó + 1 (factor de equilibrio)

Definición del altura de un árbol

Sea T un árbol binario de búsqueda y sean Ti y Td sus subárboles, su altura H ( T ), es:

0 si el árbol T está vacío

1 + max( H ( Ti ), H ( Td )) si no lo está

Definición de árbol AVL

Sea T un árbol binario de búsqueda con Ti y Td siendo sus subárboles izquierdo y derecho respectivamente, tenemos que:

Si T es vacío, es un árbol AVL

Si T es un ABB no vacío, es AVL si (si y sólo si):

Ti y Td son AVL y

H ( Ti ) − H ( Td ) = − 1, 0 ó + 1 (factor de equilibrio)

Rotación Simple a la Derecha: Se usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo tenga una FE de -1, es decir, que esté cargado a la izquierda. Pasamos el subárbol derecho del nodo Q como subárbol izquierdo de P. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de Q siguen estando a la izquierda de P. El árbol P pasa a ser el subárbol derecho del nodo Q. Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura. Arbol AVL Final

Se usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo tenga una FE de -1, es decir, que esté cargado a la izquierda.

Pasamos el subárbol derecho del nodo Q como subárbol izquierdo de P. Esto mantiene el árbol como ABB, ya que todos los valores a la derecha de Q siguen estando a la izquierda de P.

El árbol P pasa a ser el subárbol derecho del nodo Q.

Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.

Rotación Simple a la Izquierda: S e usará cuando el subárbol derecho de un nodo sea 2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2. Y además, la raíz del subárbol derecho tenga una FE de 1, es decir, que esté cargado a la derecha. Pasamos el subárbol izquierdo del nodo Q como subárbol derecho de P. Esto mantiene el árbol como ABB, ya que todos los valores a la izquierda de Q siguen estando a la derecha de P. El árbol P pasa a ser el subárbol izquierdo del nodo Q. Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura. Arbol AVL Final

S e usará cuando el subárbol derecho de un nodo sea 2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2. Y además, la raíz del subárbol derecho tenga una FE de 1, es decir, que esté cargado a la derecha.

Pasamos el subárbol izquierdo del nodo Q como subárbol derecho de P. Esto mantiene el árbol como ABB, ya que todos los valores a la izquierda de Q siguen estando a la derecha de P.

El árbol P pasa a ser el subárbol izquierdo del nodo Q.

Ahora, el nodo Q pasa a tomar la posición del nodo P, es decir, hacemos que la entrada al árbol sea el nodo Q, en lugar del nodo P. Previamente, P puede que fuese un árbol completo o un subárbol de otro nodo de menor altura.

Rotación Doble a la Derecha: S e usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo tenga una FE de 1, es decir, que esté cargado a la derecha. Haremos una rotación simple de Q a la izquierda. Después, haremos una rotación simple de P a la derecha. Arbol AVL Final

S e usará cuando el subárbol izquierdo de un nodo sea 2 unidades más alto que el derecho, es decir, cuando su FE sea de -2. Y además, la raíz del subárbol izquierdo tenga una FE de 1, es decir, que esté cargado a la derecha.

Haremos una rotación simple de Q a la izquierda.

Después, haremos una rotación simple de P a la derecha.

Rotación Doble a la Izquierda: Se usará cuando el subárbol derecho de un nodo sea 2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2. Y además, la raíz del subárbol derecho tenga una FE de -1, es decir, que esté cargado a la izquierda. Se trata del caso simétrico del anterior. Haremos una rotación simple de Q a la derecha. Después, haremos una rotación simple de P a la izquierda. Árbol AVL Final

Se usará cuando el subárbol derecho de un nodo sea 2 unidades más alto que el izquierdo, es decir, cuando su FE sea de 2. Y además, la raíz del subárbol derecho tenga una FE de -1, es decir, que esté cargado a la izquierda. Se trata del caso simétrico del anterior.

Haremos una rotación simple de Q a la derecha.

Después, haremos una rotación simple de P a la izquierda.

Practica 2: Realice una definición para el ADT Nodo para de un ADT árbol AVL. Realice la definición del ADT árbol AVL. Implemente el procedimiento para obtener la altura de un árbol. Implemente el procedimiento para calcular FE (Factor de Equilibrio del árbol)

Realice una definición para el ADT Nodo para de un ADT árbol AVL.

Realice la definición del ADT árbol AVL.

Implemente el procedimiento para obtener la altura de un árbol.

Implemente el procedimiento para calcular FE (Factor de Equilibrio del árbol)

¿Ahora a Trabajar?

GRACIAS INF-310 Estructura de Datos II

Add a comment

Related presentations

Related pages

Arboles AVL - YouTube

Arboles AVL y operaciones. Category Education; License Standard YouTube License; Music ... Arboles Binarios,ABB,AVL y B - Duration: 5:15.
Read more

ARBOLES AVL by Alyssa Cadena on Prezi

Transcript of ARBOLES AVL. Definición Georgi Adelsón-Velski Características ÁRBOLES AVL Por: Deysi Báez Rolando Cachipuendo Alyssa Cadena Wilmer Crisanto
Read more

Arbol AVL by renny hernandez on Prezi

Arboles AVL by renny hernandez on 6 June 2016 Tweet. Comments (0) ... Rotaciones Operaciones Que es un Árbol AVL? Factor Equilibrio Árboles AVL Insertar
Read more

PPT – Arboles AVL PowerPoint presentation | free to ...

Los rboles AVL ... v de T, las alturas de los hijos de v difieren como mucho en 1. ... Proposici n: La altura de un rbol AVL T que almacena n llaves es O ...
Read more

1 Arboles AVL Introducción Arboles AVL (Adel’son-Vel’skii ...

1 Arboles AVL Introducción Arboles AVL (Adel’son-Vel’skii and Landis. Jan 23, 2016 Documents maria-belmonte-rodriguez
Read more

Árbol AVL - Wikipedia, la enciclopedia libre

El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, Georgii Adelson-Velskii y Yevgeniy Landis. Lo dieron a conocer en la ...
Read more

Árboles (estructura) - Buch - buecher.de

Fuente: Wikipedia. Páginas: 71. Capítulos: Árbol biselado, Árbol rojo-negro, Árbol binario de búsqueda, Árbol-B, Quadtree, Árbol AVL, Algoritmo de ...
Read more