Características del árbol de búsqueda binaria

1. Orden

El árbol de búsqueda binaria puede considerarse una implementación de una tabla de búsqueda.

Nuestro objetivo al usar el árbol de búsqueda binaria es obtener el valor inmediatamente mediante la búsqueda de la clave. minimum, maximum, successor (sucesor), predecessor (predecesor), floor (piso), ceil (techo), rank (el elemento en la clasificación), select (cuál es el elemento en el puesto n) son todas manifestaciones del orden del árbol de búsqueda binaria.

2. Limitaciones

El árbol de búsqueda binaria tiene limitaciones en el rendimiento temporal.

Como se muestra en la siguiente figura, con los mismos nodos de elementos, se forman dos árboles de búsqueda binaria diferentes, ambos cumplen con la definición:

El árbol de búsqueda binaria puede degenerar en una lista enlazada. En consecuencia, la operación de búsqueda del árbol de búsqueda binaria está relacionada con la altura del árbol, y en este momento la altura de este árbol es el número de nodos n. A su vez, todos los algoritmos correspondientes del árbol de búsqueda binaria degeneran al nivel O(n).

Otras extensiones