English Deutsch Français Italiano Español Português 繁體中文 Bahasa Indonesia Tiếng Việt ภาษาไทย
Todas las categorías
0

2006-12-31 11:18:58 · 3 respuestas · pregunta de victordrh 1 en Ciencias y matemáticas Ingeniería

3 respuestas

Un árbol AVL (llamado así por las iniciales de sus inventores: Adelson-Velskii y Landis) es un árbol binario de búsqueda en el que para cada nodo, las alturas de sus subárboles izquierdo y derecho no difieren en más de 1.

No se trata de árboles perfectamente equilibrados, pero sí son lo suficientemente equilibrados como para que su comportamiento sea lo bastante bueno como para usarlos donde los ABB no garantizan tiempos de búsqueda óptimos.

El algoritmo para mantener un árbol AVL equilibrado se basa en reequilibrados locales, de modo que no es necesario explorar todo el árbol después de cada inserción o borrado.

El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, Adelson-Velskii y Landis. Lo dieron a conocer en la publicación de un artículo en 1962: "An algorithm for the organization of information" ("Un algoritmo para la organización de la información").

Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n). El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.

Para conseguir esta propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.

Los árboles AVL más profundos son los árboles de Fibonacci.

Mas informacion asi como aclaracion de dudas en:

2006-12-31 11:56:31 · answer #1 · answered by Kyara 7 · 0 0

Siembralo en el jardin de tu casa.

2007-01-01 15:19:28 · answer #2 · answered by Doctor Moko 3 · 0 0

http://es.answers.yahoo.com/question/index?qid=20061229093259AA7krmm&cp=5&tp=5#all-answers

2006-12-31 19:21:22 · answer #3 · answered by MICAELA 3 · 0 0

fedest.com, questions and answers