Un árbol de búsqueda es una estructura de datos utilizada en la programación de computadoras para contener y organizar una lista de datos. Cada árbol de búsqueda se compone de un conjunto ordenado de nodos. Estos nodos pueden conectarse a cero o más otros nodos. Los nodos individuales contienen algunos datos, así como enlaces a otros nodos. Los datos que están contenidos en los nodos del árbol se ordenan muy a menudo de alguna manera para permitir que los algoritmos eficientes busquen, inserte y elimine nodos con facilidad.
Los nodos de un árbol de búsqueda se describen con cuatro términos importantes. La parte superior de un árbol, donde se encuentra el primer nodo, se llama raíz. Si un nodo contiene enlaces a sub -nodos, ese nodo se conoce como padre. Los nodos que están debajo del padre se llaman hijos, y cualquier nodo que no tenga nodos hijos se llama hoja. un nodo raíz se identifica porque no tiene un padre y los nodos hoja no tendrán hijos.
Un programa puede moverse a través de un árbol buscando datos comenzando en un nodo en particular, realizando una verificación condicional y luego moviéndose al siguiente nodo lógico si los datos requeridos no están presentes. Dependiendo de la estructura de datos utilizada , esta búsqueda puede llevar una cantidad de tiempo variable. Si el árbol de búsqueda está organizado durante el proceso de agregar y quitar nodos, la búsqueda puede ser muy rápida. Cuando se ensambla un árbol aleatoriamente, no está clasificado o permite varios padres, la búsqueda puede llevar mucho tiempo.
Un factor que afecta el uso de los árboles de búsqueda es la cuestión del equilibrio. Un árbol equilibrado es aquel en el que los elementos secundarios derecho e izquierdo del nodo raíz contienen la misma profundidad de nodos secundarios o están dentro de un recuento de un nodo. La profundidad de un árbol es el número de nodos desde la hoja más baja de un árbol hasta la raíz. Un árbol desequilibrado podría tener todos los nodos en un solo lado o tener todos los nodos dispuestos de forma lineal sin ramas.Cuando aumenta la profundidad de un árbol, la velocidad de los algoritmos de búsqueda puede disminuir drásticamente.
Hay ciertos tipos de árboles de búsqueda que se describen como autoequilibrados. Estos árboles utilizan operaciones como la rotación de árboles para ayudar a mantener el equilibrio y al mismo tiempo preservar el orden de los datos en las hojas. Las rotaciones de árboles pueden ralentizar un programa al agregar y eliminar nodos, esto se contrarresta con la velocidad a la que se pueden recuperar los datos.
Aunque hay muchos tipos de árboles de búsqueda, la estructura de datos de árbol más común es un árbol de búsqueda binario. Este tipo de datos consta de nodos que tienen de cero a dos nodos secundarios. Solo hay un nodo raíz, y todas las hojas del árbol están ordenadas de izquierda a derecha en valores ascendentes de acuerdo con los datos que contienen. Existen muchos algoritmos para árboles de búsqueda binaria que pueden facilite los datos de pedido.
No existe una implementación estándar única para los nodos de árbol de búsqueda. Los nodos se pueden representar mediante una amplia variedad de estructuras de datos. Se pueden utilizar matrices de matrices, al igual que múltiples listas enlazadas. A menudo, un El árbol de búsqueda utiliza una estructura de datos personalizada que está diseñada para ayudar a completar las operaciones necesarias solicitadas por el programa Algunas bibliotecas de programación estándar incluso incluyen sus propias implementaciones internas de árboles de búsqueda.