Universidad Fermín Toro

Vicerrectorado Académico

Facultad de Ingeniería en Computación

Autor: Oswaldo Pérez

Cedula: 17305581

Tutor: Diosmary Marrón

Sección: SAIA “A”

Cabudare; Febrero del 2015

“Arboles Binarios de

Búsqueda”

Arboles Binarios de Búsqueda

El nombre AVL o ABB son las iniciales de los creadores este tipo de

árbol Adelson-Velskii y Landis en 1962.

Un árbol AVL es un árbol binario de

búsqueda al que se le añade una condición

de equilibrio.

Un árbol binario es un AVL si y sólo si cada uno de sus nodos tiene un equilibrio de

–1, 0, + 1

Técnicas para balancear un

Árbol Binario de Búsqueda

• Caso 1• Caso 2• Caso 3• Caso 4

Arboles Binarios

de Búsqueda

Técnicas para balancear un Árbol Binario de Búsqueda

Caso 1 Rotación simple

izquierda RSI

Caso 2 Rotación simple

derecha RSD

Caso 3 Rotación

dobleizquierda RDI

Caso 4 Rotación

doblederecha RDD

Si está desequilibrado a la izquierda y su

hijo derecho tiene el mismo signo (+)

Si está desequilibrado a la derecha y su hijo

izquierdo tiene el mismo signo (-)

Si está desequilibrado a la izquierda}

(FE < –1), y su hijo derecho tiene distinto

signo (+)

Si está desequilibrado a la derecha y

su hijo izquierdo tiene distinto

signo (–)

Ejemplo 1

Ejemplo 2

Ejemplo 3

Ejemplo 4