Recorrido narrado

Buscar y recorrer, en pseudocódigo

función buscar(nodo, k):    mientras nodo ≠ nada:        si k = nodo.clave: devolver nodo        si k < nodo.clave: nodo ← nodo.izquierdo        si no: nodo ← nodo.derecho    devolver nadafunción en_orden(nodo):           # se llama a sí misma: recursión    si nodo = nada: devolver    en_orden(nodo.izquierdo)    escribir nodo.clave    en_orden(nodo.derecho)

La altura de un árbol es la cantidad de nodos del camino más largo desde la raíz hasta una hoja. Buscar, insertar, el mínimo (bajar siempre a la izquierda) y el sucesor cuestan O(h), con h la altura. Recorrer en orden cuesta O(n).

Cuánto vale h depende de la forma del árbol, que depende del orden en que llegaron las claves. Es el siguiente tema.

Su fila en la tabla de costos

El BST sin balancear, en las columnas de conjunto y diccionario de la ruta. La condición es la altura h, que puede llegar a n.