Binary Search Tree , es una estructura de datos de árbol binario basada en Nodes que tiene las siguientes propiedades:
- El subárbol izquierdo de un Node contiene solo Nodes con claves menores que la clave del Node.
- El subárbol derecho de un Node contiene solo Nodes con claves mayores que la clave del Node.
- El subárbol izquierdo y derecho también debe ser un árbol de búsqueda binaria.
No debe haber Nodes duplicados.
Un BST admite operaciones como búsqueda, inserción, eliminación, suelo, techo, mayor, menor, etc. en tiempo O(h), donde h es la altura del BST. Para mantener una altura menor, en la práctica se utilizan BST de autoequilibrio (como AVL y Red Black Trees ). Estos BST de autoequilibrio mantienen la altura como O (Log n). Por lo tanto, todas las operaciones mencionadas anteriormente se convierten en O (Log n). Junto con estos, BST también permite el recorrido ordenado de datos en tiempo O(n).
- Se utiliza un árbol de búsqueda binario autoequilibrado para mantener ordenado el flujo de datos. Por ejemplo, supongamos que estamos recibiendo pedidos en línea y queremos mantener los datos en vivo (en RAM) en orden de precios. Por ejemplo, deseamos saber el número de artículos comprados a un costo por debajo de un costo dado en cualquier momento. O deseamos saber el número de artículos comprados a un costo mayor que el costo dado.
- Se utiliza un árbol de búsqueda binario autoequilibrado para implementar una cola de prioridad de dos extremos . Con Binary Heap, podemos implementar una cola de prioridad con soporte de extractMin() o con extractMax(). Si deseamos admitir ambas operaciones, usamos un árbol de búsqueda binario autoequilibrado para hacer ambas en O (Iniciar sesión)
- Hay muchos más problemas de algoritmos en los que una BST autoequilibrada es la estructura de datos más adecuada, como contar los elementos más pequeños a la derecha , el elemento más pequeño y mayor a la derecha , etc.