ARBOLES BINARIOS DE BÚSQUEDA

Esta sección discute una de las estructuras de datos mas importantes de la informática, el árbol binario de búsqueda. Esta estructura permite buscar y encontrar un elemento  con una media de tiempo de ejecución ʄ(n)=0(log₂n). También permite insertar y borrar elementos fácilmente. Esta estructura contrasta con las siguientes estructuras.

(a) Array lineal ordenado. Aquí se puede buscar y encontrar un elemento con un tiempo de ejecución ʄ(n)=0(log₂n), pero es costoso al insertar y borrar elementos.

(b) lista enlazada. Aquí se puede insertar y borrar  fácilmente, pero es costoso el buscar y encontrar un elemento, ya que se pude buscar una búsqueda secuencial.

Supongamos que T es un árbol binario. Entonces T se dice que es un árbol binario de búsqueda (o árbol binario ordenado) se cada N de T tiene la siguiente propiedad: el valor de N es mayor que cualquier valor del subárbol izquierdo de N y es menor que cualquier valor del subárbol derecho de N. (no es difícil ver que esta propiedad garantice que el recorrido inorden de T dará una lista ordenado de los elementos de T).