Árbol de búsqueda binario

Fig. 1: Un árbol de búsqueda binaria de tamaño 9 y profundidad 3, con 8 en la raíz. Las hojas no se dibujan.

En informática, un árbol de búsqueda binaria (BST), también llamado árbol binario ordenado o ordenado, es una estructura de datos de árbol binario enraizado con la clave de cada nodo interno mayor que todas las claves en el subárbol izquierdo del nodo respectivo y menor que las claves en su subárbol derecho. La complejidad temporal de las operaciones en el árbol de búsqueda binaria es directamente proporcional a la altura del árbol.

Los árboles de búsqueda binaria permiten la búsqueda binaria para una rápida búsqueda, adición y eliminación de elementos de datos. Dado que los nodos en un BST están dispuestos de modo que cada comparación salta aproximadamente la mitad del árbol restante, el rendimiento de la búsqueda es proporcional al del logaritmo binario. Los BST se idearon en la década de 1960 para el problema del almacenamiento eficiente de datos etiquetados y se atribuyen a Conway Berners-Lee y David Wheeler.

El rendimiento de un árbol de búsqueda binaria depende del orden de inserción de los nodos en el árbol, ya que las inserciones arbitrarias pueden conducir a la degeneración; se pueden construir varias variaciones del árbol de búsqueda binaria con un rendimiento garantizado en el peor de los casos. Las operaciones básicas incluyen: búsqueda, recorrido, inserción y eliminación. Los BST con complejidades garantizadas en el peor de los casos funcionan mejor que una matriz no ordenada, que requeriría un tiempo de búsqueda lineal.

El análisis de complejidad de BST muestra que, en promedio, la inserción, el borrado y la búsqueda toma ${displaystyle O(log n)}$ para ${displaystyle n}$ nodos. En el peor de los casos, se degradan a la de una lista enlazada: ${displaystyle O(n)}$. Para abordar el incesante aumento de la altura de los árboles con inserciones y eliminaciones arbitrarias, se introducen variantes autoequilibrantes de los BST para limitar la peor complejidad de la búsqueda a la del logaritmo binario. Los árboles de AVL fueron los primeros árboles de búsqueda binaria auto-balance, inventados en 1962 por Georgy Adelson-Velsky y Evgenii Landis.

Los árboles de búsqueda binarios se pueden usar para implementar tipos de datos abstractos, como conjuntos dinámicos, tablas de búsqueda y colas de prioridad, y se pueden usar en algoritmos de clasificación, como la clasificación de árboles.

Historia

El algoritmo del árbol de búsqueda binaria fue descubierto de forma independiente por varios investigadores, incluido P.F. Windley, Andrew Donald Booth, Andrew Colin, Thomas N. Hibbard. El algoritmo se atribuye a Conway Berners-Lee y David Wheeler, quienes lo usaron para almacenar datos etiquetados en cintas magnéticas en 1960. Uno de los algoritmos de árbol de búsqueda binaria más antiguos y populares es el de Hibbard.

Las complejidades temporales de un árbol de búsqueda binaria aumentan sin límites con la altura del árbol si los nodos se insertan en un orden arbitrario, por lo tanto se introdujeron árboles de búsqueda binaria auto-balance para atar la altura del árbol a ${displaystyle O(logn)}$. Varios equilibrado de altura Se introdujeron árboles de búsqueda binaria para limitar la altura del árbol, como árboles AVL, Treaps y árboles negros rojos.

El árbol AVL fue inventado por Georgy Adelson-Velsky y Evgenii Landis en 1962 para la organización eficiente de la información. Fue el primer árbol de búsqueda binario autoequilibrado que se inventó.

Resumen

Un árbol binario de búsqueda es un árbol binario enraizado en el que los nodos se organizan en un orden total en el que los nodos con claves mayores que cualquier nodo en particular se almacenan en los subárboles de la derecha y los que tienen claves iguales o menores que son almacenado en el subárbol izquierdo que satisface la propiedad de búsqueda binaria.

Los árboles de búsqueda binarios también son eficaces en la clasificación y los algoritmos de búsqueda. Sin embargo, la complejidad de búsqueda de un BST depende del orden en que se insertan y eliminan los nodos; ya que en el peor de los casos, las operaciones sucesivas en el árbol de búsqueda binaria pueden conducir a la degeneración y formar una estructura similar a una lista enlazada (o "árbol desequilibrado"), por lo que tiene la misma complejidad en el peor de los casos que una lista enlazada.

Los árboles de búsqueda binarios también son una estructura de datos fundamental utilizada en la construcción de estructuras de datos abstractas como conjuntos, conjuntos múltiples y matrices asociativas.

Operaciones

Buscando

La búsqueda en un árbol de búsqueda binario para una clave específica se puede programar de forma recursiva o iterativa.

La búsqueda comienza examinando el nodo raíz. Si el árbol es ${displaystyle {text{nil}}$, la clave que se busca no existe en el árbol. De lo contrario, si la clave es igual a la de la raíz, la búsqueda es exitosa y el nodo es devuelto. Si la clave es menor que la de la raíz, la búsqueda procede examinando el subárbol izquierdo. Del mismo modo, si la clave es mayor que la de la raíz, la búsqueda procede examinando el subárbol derecho. Este proceso se repite hasta que se encuentre la llave o el subárbol restante ${displaystyle {text{nil}}$. Si la clave registrada no se encuentra después de una ${displaystyle {text{nil}}$ subárbol es alcanzado, entonces la llave no está presente en el árbol.

Búsqueda recursiva

El siguiente pseudocódigo implementa el procedimiento de búsqueda BST mediante recursividad.

 Recursive-Tree-Search(x, clave)
 si x = NIL o llave = x.key entonces retorno x
 si llave entonces retorno Recursive-Tree-Search(x.left, key)
 más retorno Recursive-Tree-Search(x.right, key)
 terminar si

El procedimiento recursivo continúa hasta que un ${displaystyle {text{nil}}$ o el ${displaystyle {text{key}}}$ ser buscado se encuentran.

Búsqueda iterativa

La versión recursiva de la búsqueda se puede "desenrollar" en un bucle while. En la mayoría de las máquinas, se encuentra que la versión iterativa es más eficiente.

 Iterative-Tree-Search(x, key)
 mientras x ل NIL y clave ل x.key entonces si llave entoncesx:= x.left
 másx:= x.right
 terminar si repetición retorno x

Puesto que la búsqueda puede continuar hasta algunos nodos de hoja, la complejidad del tiempo de funcionamiento de la búsqueda BST es ${displaystyle O(h)}$ Donde ${displaystyle h}$ es la altura del árbol. Sin embargo, el peor caso para la búsqueda de BST es ${displaystyle O(n)}$ Donde ${displaystyle n}$ es el número total de nodos en el BST, porque un BST desequilibrado puede degenerar a una lista vinculada. Sin embargo, si el BST es equilibrado de altura la altura es ${displaystyle O(log n)}$.

Sucesor y predecesor

Para ciertas operaciones, dado un nodo ${displaystyle {text{x}}}$, encontrar el sucesor o predecesor de ${displaystyle {text{x}}}$ es crucial. Asumiendo que todas las llaves del BST son distintas, el sucesor de un nodo ${displaystyle {text{x}}}$ en BST es el nodo con la clave más pequeña que ${displaystyle {text{x}}}$Es clave. Por otra parte, el predecesor de un nodo ${displaystyle {text{x}}}$ en BST es el nodo con la llave más grande más pequeña que ${displaystyle {text{x}}}$Es clave. Seguir es pseudocódigo para encontrar al sucesor y predecesor de un nodo ${displaystyle {text{x}}}$ en BST.

 BST-Successor(x)
 si x.right ل NIL entonces retorno BST-Minimum(x.right)
 terminar siy:= x.parent
 mientras y √≥ NIL y x = y.right entoncesx:= Sí.
Y...
 repetición retorno Sí.

 BST-Predecessor(x)
 si x.left ل NIL entonces retorno BST-Maximum(x.left)
 terminar siy:= x.parent
 mientras y √≥ NIL y x = y.izquierda entoncesx:= Sí.
Y...
 repetición retorno Sí.

Operaciones como encontrar un nodo en un BST cuya clave sea el máximo o el mínimo son críticas en ciertas operaciones, como determinar el sucesor y el predecesor de los nodos. A continuación se muestra el pseudocódigo de las operaciones.

 BST-Maximum(x)
 mientras x.right ل NIL entoncesx:= x.right
 repetición retorno x

 BST-Minimum(x)
 mientras x.left ل NIL entoncesx:= x.left
 repetición retorno x

Inserción

Operaciones como la inserción y la eliminación hacen que la representación BST cambie dinámicamente. La estructura de datos debe modificarse de tal manera que las propiedades de BST se mantengan. Los nuevos nodos se insertan como nodos hoja en el BST. A continuación se muestra una implementación iterativa de la operación de inserción.

1 BST-Insert(T, z)
2 y= NIL
3 x:= T.root
4 mientras x ل NIL do5 y:= x
6 si z.key entonces7 x:= x.left
8 más9 x:= x.right
10 terminar si11 repetición12 z.parent:= Sí.
13 si Y... entonces14 T.root:= z
15 si z.key entonces16 y.left:= z
17 más18 y.right:= z
19 terminar si

El procedimiento mantiene un "puntero de navegación" ${displaystyle {text{y}}}$ como padre de ${displaystyle {text{x}}}$. Después de la inicialización en la línea 2, el mientras el bucle en las líneas 4-11 hace que los punteros sean actualizados. Si ${displaystyle {text{y}}}$ es ${displaystyle {text{nil}}$, el BST está vacío, por lo tanto ${displaystyle {text{z}}$ se inserta como el nodo raíz del árbol de búsqueda binaria ${displaystyle {text{T}}}$, si no es ${displaystyle {text{nil}}$, la inserción procede comparando las claves con la de ${displaystyle {text{y}}}$ en las líneas 15-19 y el nodo se inserta en consecuencia.

Eliminación

Fig. 2: Árbol de búsqueda binaria casos especiales ilustración de eliminación.

Eliminación de un nodo, digamos ${displaystyle {text{z}}$, desde un árbol de búsqueda binaria ${displaystyle {text{T}}}$ debe cumplir tres casos:

1. Si ${displaystyle {text{z}}$ es un nodo de hoja, el puntero del nodo padre ${displaystyle {text{z}}$ se reemplaza con ${displaystyle {text{nil}}$ y en consecuencia ${displaystyle {text{z}}$ se quita del árbol.
2. Si ${displaystyle {text{z}}$ tiene un solo nodo infantil, el niño se eleva como niño izquierdo o derecho de ${displaystyle {text{z}}$'s padre dependiendo de la posición de ${displaystyle {text{z}}$ dentro del BST, como se muestra en el gráfico 2 parte a) y parte b), y como resultado, ${displaystyle {text{z}}$ se quita del árbol.
3. Si ${displaystyle {text{z}}$ tiene un hijo izquierdo y derecho, el sucesor ${displaystyle {text{z}}$ (que sea ${displaystyle {text{y}}}$) toma la posición de ${displaystyle {text{z}}$ en el árbol. Esto depende de la posición de ${displaystyle {text{y}}}$ dentro del BST:
   1. Si ${displaystyle {text{y}}}$ es ${displaystyle {text{z}}$Es niño derecho inmediato, ${displaystyle {text{y}}}$ se eleva y ${displaystyle {text{y}}}$'s left child made point to ${displaystyle {text{z}}$'s inicial sub-árbol izquierdo, como se muestra en fig. 2 parte (c).
   2. Si ${displaystyle {text{y}}}$ no es el niño derecho inmediato ${displaystyle {text{z}}$, la supresión procede reemplazando la posición de ${displaystyle {text{y}}}$ por su hijo derecho, y ${displaystyle {text{y}}}$ toma la posición de ${displaystyle {text{z}}$ en el BST, como se muestra en el gráfico 2 parte d).

El siguiente pseudocódigo implementa la operación de eliminación en un árbol de búsqueda binario.

1 BST-Delete(T, z)
2 si z.left = NIL entonces3 Shift-Nodes(T, z, z.right)
4 si z.right = NIL entonces5 Shift-Nodes(T, z, z.left)
6 más7 y= Tree-Successor(z)
8 si y.parent √ z entonces9 Shift-Nodes(T, y, y.right)
10 y.right:= z.right
11 y.right.parent:= Sí.
12 terminar si13 Shift-Nodes(T, z, y)
14 y.left:= z.left
15 y.left.parent:= Sí.
16 terminar si

1 Shift-Nodes(T, u, v)
2 si U.parent = NIL entonces3 T.root:= v
4 si u = u.parent.left entonces5 u.parent.left:= v
5 más6 u.parent.right:= v
7 terminar si8 si v ل NIL entonces9 v.parent:= u.parent
10 terminar si

El ${displaystyle {text{Tree-Delete}}}$ el procedimiento se refiere a los 3 casos especiales mencionados anteriormente. Las líneas 2-3 se refieren al caso 1; las líneas 4-5 se refieren al caso 2 y las líneas 6-16 para el caso 3. Función de ayuda ${displaystyle {text{Shift-Nodes}}$ se utiliza dentro del algoritmo de eliminación para reemplazar el nodo ${displaystyle {text{u}}}$ con ${displaystyle {text{v}}}$ en el árbol de búsqueda binaria ${displaystyle {text{T}}}$. Este procedimiento maneja la eliminación (y sustitución) de ${displaystyle {text{u}}}$ del BST.

Transversal

Un BST se puede atravesar a través de tres algoritmos básicos: paseos en árbol en orden, en orden previo y en orden posterior.

• Paseo en el árbol: Nodos del subárbol izquierdo se visitan primero, seguido por el nodo raíz y el subárbol derecho.
• Paseo de árboles preordenados: El nodo raíz se visita primero, seguido por los subárboles izquierdo y derecho.
• Paseo por los árboles del cartel: Nodos del subárbol izquierdo se visitan primero, seguido por el subárbol derecho, y finalmente la raíz.

Lo siguiente es una implementación recursiva de los paseos en árbol.

 Inorder-Tree-Walk(x)
 si x ل NIL entoncesInorder-Tree-Walk(x.left)
 visit nodeInorder-Tree-Walk(x.right)
 terminar si

 Preorder-Tree-Walk(x)
 si x ل NIL entonces visit nodePreorder-Tree-Walk(x.left)
Preorder-Tree-Walk(x.right)
 terminar si

 Postorder-Tree-Walk(x)
 si x ل NIL entoncesPostorder-Tree-Walk(x.left)
Postorder-Tree-Walk(x.right)
 visit node terminar si

Árboles de búsqueda binaria equilibrada

Sin rebalamentar, las inserciones o eliminaciones en un árbol de búsqueda binario pueden conducir a la degeneración, dando lugar a una altura ${displaystyle n}$ del árbol (donde ${displaystyle n}$ es el número de elementos en un árbol), por lo que el rendimiento de la búsqueda se deteriora a la de una búsqueda lineal. Mantener el árbol de búsqueda equilibrado y atado por ${displaystyle O(log n)}$ es una clave para la utilidad del árbol de búsqueda binario. Esto se puede lograr mediante mecanismos de "auto-balancing" durante las operaciones de elevación al árbol diseñado para mantener la altura del árbol a la complejidad logarítmica binaria.

Árboles de altura equilibrada

Un árbol está equilibrado en altura si se garantiza que las alturas del subárbol izquierdo y del subárbol derecho están relacionadas por un factor constante. Esta propiedad fue introducida por el árbol AVL y continuada por el árbol Rojo-Negro. Las alturas de todos los nodos en la ruta desde la raíz hasta el nodo hoja modificado deben observarse y posiblemente corregirse en cada operación de inserción y eliminación en el árbol.

Árboles de peso equilibrado

En un árbol balanceado de peso, el criterio de un árbol equilibrado es el número de hojas de los subárboles. Los pesos de los subárboles izquierdo y derecho difieren en la mayoría por ${displaystyle 1}$. Sin embargo, la diferencia está vinculada por una relación ${displaystyle alpha }$ de los pesos, desde una fuerte condición de equilibrio ${displaystyle 1}$ no se puede mantener con ${displaystyle O(log n)}$ rebalancing work during insert and delete operations. El ${displaystyle alpha }$- árboles balanceados con peso da a toda una familia de condiciones de equilibrio, donde cada subárbol izquierdo y derecho tiene cada al menos una fracción de ${displaystyle alpha }$ del peso total del subárbol.

Tipos

Hay varios árboles de búsqueda binarios autoequilibrados, incluidos el árbol T, treap, árbol rojo-negro, árbol B, árbol 2–3 y árbol Splay.

Ejemplos de aplicaciones

Ordenar

Los árboles de búsqueda binarios se utilizan en algoritmos de clasificación, como la clasificación de árbol, donde todos los elementos se insertan a la vez y el árbol se recorre en orden. Los BST también se utilizan en la ordenación rápida.

Operaciones de cola prioritaria

Los árboles de búsqueda binarios se utilizan para implementar colas de prioridad, utilizando la clave del nodo como prioridades. La adición de nuevos elementos a la cola sigue la operación normal de inserción de BST, pero la operación de eliminación depende del tipo de cola de prioridad:

• Si se trata de una cola de prioridad de orden ascendente, la eliminación de un elemento con la prioridad más baja se realiza a través de la transversal izquierda del BST.
• Si se trata de una cola de prioridad de orden descendente, la eliminación de un elemento con la máxima prioridad se realiza a través de la transversal derecha del BST.