Taller 3

Programación Matemática a Gran Escala
Departamento de Ingeniería de Sistemas e Industrial
Universidad Nacional de Colombia

Fecha de Entrega: Octubre 14, 2003

Desarrollar un programa que resuleva el siguiente problema:

Un árbol binario de búsqueda debe satisfacer las siguientes propiedades:
  1. Cada nodo debe tener un único valor
  2. El valor de un nodo dado debe ser mayor que el valor de cada nodo en el subárbol izquierdo.
  3. El valor de un nodo dado debe ser menor que el valor de cada nodo en el subárbol derecho.
La profundidad de un nodo corresponde al número de vértices en el único camino a la raíz (la profundidad de la raíz es 1). El access score (AS) de un árbol de búsqueda se calcula multiplicando la profundidad de cada nodo por la probabilidad de accederlo.

El problema es encontrar el árbol con AS mínimo para un conjunto de datos con una serie de probabilidades dada.

El programa debe recibir los datos y las probabilidades de acceso. Las probabilidades se especifican porcentualmente, es decir, con números enteros entre 0 y 100. El programa debe imprimir el AS y el árbol optimo.

Ejemplos:

 1. Datos= {2,5,3,6} Probabilidades de acceso={15,25,35,25}

AS máximo = 2*15 + 1*35 + 2*25 + 3*25 = 190,  para el árbol:
   3
  / \
 2   5
      \
       6
2. Datos= {6,5,3,7,51,36} Probabilidades de acceso={15,13,39,10,3,20} AS mínimo = 211, para el árbol:
    6
   / \
  5  36
 /  /  \
3  7   51

3. Datos= {6,5,3,7,51,36} Probabilidades de acceso={20,3,10,39,13,15}

AS mínimo = 190, para el árbol:
    7
   / \
  6   36
 /     \
3       51
 \
  5