TRABAJO COLABORATIVO 3 ESTRUCTURAS DE DATOS

ACTIVIDAD 1: TEORIA DE ÁRBOLES BINARIOS DE BÚSQUEDA Esta sección discute una de las estructuras de datos más 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 f (n) = 0 (log2 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 f(n) = (log2n), pero es costoso el insertar y borrar elementos. b. Lista enlazada. Aquí se puede insertar y borrar elementos fácilmente, pero es costoso el buscar y encontrar un elemento, ya que se debe usar una búsqueda secuencial. Aunque cada nodo de un árbol binario de búsqueda puede contener un registro entero de datos, la definición del árbol binario depende de un campo dado cuyos valores son distintos y deben estar ordenados. Supongamos que T es un árbol binario. Entonces T se dice que es un árbol binario de búsqueda ( o árbol binario ordenado) si cada nodo 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 garantiza el recorrido inorden de T dará una lista ordenada de los elementos de T) .

Definición de árboles de búsqueda binaria

Un árbol es una estructura de datos recursiva que se puede caracterizar en forma inductiva:

 El árbol vacío es un árbol.

 Un nodo del cual cuelgan uno más árboles es un árbol.

...