Árbol equilibrado de altura dada

21 abril 2007

En otro ejercicio de clase se nos pide que diseñemos una función que, dado un natural h, devuelva un árbol binario que cumpla que es el árbol equilibrado de altura h con el menor número de nodos posible. El contenido de los nodos de dicho árbol será un natural en el rango de 1 hasta el número de nodos del árbol, de forma que todos los nodos tengan información diferente y el árbol esté ordenado.

Recordemos los conceptos de,

Árbol equilibrado: es un árbol binario de búsqueda en el que para cada nodo el número de niveles de sus subárboles izquierdo y derecho no debe diferir en más de una unidad.

Árbol binario de búsqueda: es un árbol binario que tiene la propiedad que hace que todos los elementos almacenados en el subárbol izquierdo son menores que la raíz y ésta es menor que todos los elementos del subárbol derecho.

Veamos algunos ejemplos de árboles equilibrados,

Árboles equilibrados para una altura dada

Podemos ver que el número de nodos para una altura dada coincide con la expresión 2^(altura – 1). Mi implementación se basa en una función auxiliar recursiva que vaya construyendo los árboles binarios desde las hojas a la raíz sabiendo que los nodos que compondrán el árbol irán ordenados desde 2 hasta el número de nodos además de la primera hoja etiquetada con 1 que hace que se alcance la altura pedida con el mínimo número de nodos.

Esta es mi implementación:

func generaAVL (h: natural) dev (a: BinaryTree)
alg
	// Funcion recursiva auxiliar que genera el arbol binario de búsqueda
	// a partir del número de nodos del árbol que viene dado por 2^(altura -1)
	a := generaAVLaux(2, 2^(h-1)) 
fin

func generaAVLaux (ini, fin) dev (a: BinaryTree)
var
	raiz: Entero
	izq, der: BinaryTree
alg
	raiz := (ini + fin) / 2
	
	si ((raiz - ini) = 1):		// Caso base
		si (ini = 2)
			izq := BinaryTree(BinaryTree(null,1,null), ini, null )
		| otras:
			izq := BinaryTree(null, ini, null)
		fsi
		der := BinaryTree(null, fin, null)
		a := BinaryTree(izq, raiz, der)
	| otras:			// Caso recursivo
		a := BinaryTree( generaAVLaux(ini, raiz-1), raiz, generaAVLaux(raiz+1, fin) )
	fsi
fin

Creo que se trata de una implementación un poco sucia en cuanto al código pero creo que es bastante eficiente. Se trata del ejercicio 4 del boletín de árboles de EDA.

:wq

6 Responses to “Árbol equilibrado de altura dada”

  1. alidhaey Says:

    A este ritmo, vas a reforestar el amazonas.


  2. Hola Antonio. Somos la chica y el chico que te han hablado antes en meebo. Te habíamos comentado lo de árboles. Te hemos dejado el mail por si nos quieres contestar pero si no tienes tiempo, no te acuerdas o no te apetece no te preocupes. Emhorabuena por tu página. Un saludo.


  3. Zaira, Miguel, gracias por visitar mi blog antes que nada.

    Me habéis pillado en el trabajo y no me he enterado bien de qué cuestión me habéis planteado sobre árboles AVL. Refrescadme la memoria a ver si os puedo ayudar en algo.

    Un saludo.

  4. -- Paty -- Says:

    Hola soy de Mexico…

    Me podrias decir si existe este tipo de arboles de busqueda binaria equilibrados con rotacion a la derecha, izquierda, derecha-izquierda, izquierda-derecha

  5. Samu Says:

    Hola, quisiera saber qué aplicaciones de la vida cotidiana podemos aplicar los arboles equilibrados, sabes como estoy comenzando en esto quiero tener una clara vision de lo que puedo aplicar utilizando este tipo de estructuras, que son muy interesantes; especialmente en C que es el lenguaje que ocupamos en la Universidad,

    De antemano gracias y espero su valiosa respuesta!

  6. matiasargertina Says:

    soy puto :$


Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: