Motivación

La idea de guardar datos en un Árbol Binario de Búsqueda (ABB) es conseguir mejor tiempo de acceso a los datos en las operaciones de búsqueda/recuperación, inserción o eliminación comparado con los tiempos en estructuras lineales como arreglos y listas.

En los ABBs el acceso a un dato es proporcional a la altura del árbol, ya que su ubicación podría ser, en el peor de los casos, en una hoja. En consecuencia, es deseable que el ABB tenga la menor altura posible; como este tipo de árbol sólo debe respetar su propiedad de orden, la altura dependerá de la secuencia en que los datos se fueron insertando en el momento de la creación del mismo.

El mismo conjunto de datos, por ejemplo: 13, 15, 28, 32, 35, 22, puede generar ABBs con distintas alturas.

Secuencia 1: 13, 15, 22, 28, 32, 35          Secuencia 2:  28, 22, 15, 13, 32, 35            Secuencia 3:  28, 15, 13,  22, 35, 32

 Observemos que con la última secuencia de ingreso se obtiene el ABB con mínima altura posible.

Un árbol binario de búsqueda tiene altura mínima posible cuando es balanceado (recordar que un árbol binario es balanceado si para todo nodo en el árbol, la altura de los subárboles izquierdo y derecho difiere a lo sumo en 1)

A partir de una secuencia de datos, podemos obtener un ABB de altura mínima si primero la ordenamos y luego tomamos los elementos en forma dicotómica para insertarlos en el ABB.

Siguiendo con el ejemplo anterior, a partir de los datos 13, 15, 28, 32, 35, 22 obtenemos la siguiente secuencia ordenada: 13, 15, 22, 28, 32, 35   

El orden en que construimos el ABB sería : 28, 35, 32, 15, 13, 22

El esfuerzo adicional de construir el ABB de esta manera no nos garantiza que se mantenga balanceado con futuras operaciones de inserción o eliminación, para salvar estos inconvenientes se pueden utilizar los árboles AVL inventados por Adelson-Velskii y Landis  en el año 1962 y que serán descriptos en las próximas secciones.