Un árbol binario de búsqueda también llamado BST (acrónimo del inglés Binary Search Tree) es un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol usada en informática.
Para una fácil comprensión queda resumido en que es un árbol binario que cumple que el subárbol izquierdo de cualquier nodo ( si no está vacío ) contiene valores menores que el que contiene dicho nodo, y el subárbol derecho ( si no está vacío ) contiene valores mayores.
Para estas definiciones se considera que hay una relación de orden establecida entre los elementos de los nodos. Que cierta relación esté definida, o no, depende de cada lenguaje de programación.
De aquí se deduce que puede haber distintos árboles binarios de búsqueda para un mismo conjunto de elementos.
La altura h en el peor de los casos es siempre el mismo tamaño que el número de elementos disponibles. Y en el mejor de los casos viene dada por la expresión
El interés de los árboles binarios de búsqueda (ABB) radica en que su recorrido en in orden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.
Dependiendo de las necesidades del usuario que trate con una estructura de este tipo, se podrá permitir la igualdad estricta en alguno, en ninguno o en ambos de los subárboles que penden de la raíz. Permitir el uso de la igualdad provoca la aparición de valores dobles y hace la búsqueda más compleja.
Copyright 2024 puzzlefactory.com Reservados todos los derechos.
