los árboles de búsqueda binarios admiten tres operaciones principales: inserción de elementos, eliminación de elementos y búsqueda (Comprobación de si una clave está presente).

SearchingEdit

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

comenzamos examinando el nodo raíz. Si el árbol es null, la clave que estamos buscando 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 devolvemos el nodo. Si la clave es menor que la de la raíz, buscamos el subárbol izquierdo., Del mismo modo, si la clave es mayor que la de la raíz, buscamos el subárbol derecho. Este proceso se repite hasta que se encuentra la clave o el subárbol restante es nulo. Si la clave buscada no se encuentra después de alcanzar un subárbol nulo, entonces la clave no está presente en el árbol. Esto se expresa fácilmente como un algoritmo recursivo (implementado en Python):

el mismo algoritmo se puede implementar iterativamente:

estos dos ejemplos no admiten duplicados, es decir, dependen de que la relación de orden sea un orden total.

uno puede notar que el algoritmo recursivo es recursivo de cola., En un lenguaje que admite la optimización de llamadas de cola, los ejemplos recursivos e iterativos se compilarán en programas equivalentes.

debido a que en el peor de los casos este algoritmo debe buscar desde la raíz del árbol hasta la hoja más alejada de la raíz, la operación de búsqueda toma un tiempo proporcional a la altura del árbol (ver terminología del árbol). En promedio, los árboles de búsqueda binarios con claves de nodos tienen una altura de o (log / Nodes/). Sin embargo, en el peor de los casos, los árboles de búsqueda binarios pueden tener una altura O(|Nodes|), cuando el árbol desequilibrado se asemeja a una lista enlazada (árbol degenerado).,

buscar con duplicados permitidoseditar

si la relación de orden es solo un preorden total, una extensión razonable de la funcionalidad es la siguiente: también en caso de búsqueda de igualdad hasta las hojas. Lo que permite especificar (o hard-wire) una dirección, donde insertar un duplicado, YA SEA a la derecha o a la izquierda de todos los duplicados en el árbol hasta ahora. Si la dirección está cableada, ambas opciones, derecha e izquierda, admiten una pila con insertar duplicado como operación push y eliminar como operación pop.,: 155

una clasificación de árbol binario equipada con tal función de búsqueda se vuelve estable.

InsertionEdit

la inserción comienza como comenzaría una búsqueda; si la clave no es igual a la de la raíz, buscamos los subárboles izquierdo o derecho como antes. Eventualmente, llegaremos a un nodo externo y agregaremos el nuevo par clave-valor (aquí codificado como un registro ‘newNode’) como su hijo derecho o izquierdo, dependiendo de la clave del nodo., En otras palabras, examinamos la raíz e insertamos recursivamente el nuevo nodo en el subárbol izquierdo si su clave es menor que la de la raíz, o en el subárbol derecho si su clave es mayor o igual que la raíz.

así se puede realizar una inserción típica de árbol de búsqueda binaria en un árbol binario en C++:

alternativamente, se puede implementar una versión no recursiva como esta., El uso de un puntero a puntero para realizar un seguimiento de dónde venimos permite al código evitar la comprobación explícita y el manejo del caso en el que necesita insertar un nodo en la raíz del árbol:

la variante de procedimiento destructivo anterior Modifica el árbol en su lugar. Solo usa espacio de pila constante (y la versión iterativa también usa espacio de pila constante), pero la versión anterior del árbol se pierde., Alternativamente, como en el siguiente ejemplo de Python, podemos reconstruir todos los ancestros del nodo insertado; cualquier referencia a la raíz del árbol original sigue siendo válida, haciendo que el árbol sea una estructura de datos persistente:

la parte que se reconstruye usa el espacio o (log n) en el caso promedio y O(n) en el peor de los casos.

en cualquier versión, esta operación requiere tiempo proporcional a la altura del árbol en el peor de los casos, que es O(log n) tiempo en el caso promedio sobre todos los árboles, pero o(n) tiempo en el peor de los casos.,

otra forma de explicar la inserción es que para insertar un nuevo nodo en el árbol, su clave se compara primero con la de la raíz. Si su clave es menor que la de la raíz, entonces se compara con la clave del Hijo izquierdo de la raíz. Si su clave es mayor, se compara con el hijo derecho de la raíz. Este proceso continúa, hasta que el nuevo nodo se compara con un nodo hoja, y luego se agrega como hijo derecho o izquierdo de este nodo, dependiendo de su clave: si la clave es menor que la clave de la hoja, entonces se inserta como hijo izquierdo de la hoja, de lo contrario como hijo derecho de la hoja.,

hay otras formas de insertar nodos en un árbol binario, pero esta es la única forma de insertar nodos en las hojas y al mismo tiempo preservar la estructura BST.

DeletionEdit

al eliminar un nodo de un árbol de búsqueda binario es obligatorio mantener la secuencia en orden de los nodos. Hay muchas posibilidades para hacer esto. Sin embargo, el siguiente método que ha sido propuesto por T. Hibbard en 1962 garantiza que las alturas de los subárboles sujetos son cambiadas por como máximo uno., Hay tres casos posibles a considerar:

• eliminar un nodo sin hijos: simplemente elimine el nodo del árbol.
• eliminar un nodo con un hijo: elimine el nodo y reemplácelo con su hijo.
• eliminar un Nodo D con dos hijos: elija el predecesor en orden de D o el sucesor en orden E (ver figura). En lugar de eliminar D, sobrescriba su clave y valor con E. si E no tiene un hijo, elimine e de su padre anterior G. Si E tiene un hijo F, es un hijo correcto, por lo que debe reemplazar E en el padre de E.,

en todos los casos, cuando D pasa a ser la raíz, hacer el nodo de reemplazo raíz de nuevo.

Los nodos con dos hijos son más difíciles de eliminar., El sucesor en orden de un nodo es el hijo más izquierdo de su subárbol derecho, y el predecesor en orden de un nodo es el hijo más derecho del subárbol izquierdo. En cualquier caso, este nodo tendrá solo uno o ningún hijo en absoluto. Suprímase de acuerdo con uno de los dos casos más sencillos anteriores.

usar consistentemente el sucesor en orden o el predecesor en orden para cada instancia del caso de dos hijos puede conducir a un árbol desequilibrado, por lo que algunas implementaciones seleccionan uno u otro en momentos diferentes.,

análisis de tiempo de ejecución: aunque esta operación no siempre atraviesa el árbol hasta una hoja, siempre es una posibilidad; por lo tanto, en el peor de los casos, requiere un tiempo proporcional a la altura del árbol. No requiere más incluso cuando el nodo tiene dos hijos, ya que sigue una sola ruta y no visita ningún nodo dos veces.,

TraversalEdit

Una vez que se ha creado el árbol de búsqueda binario, sus elementos se pueden recuperar en orden recorriendo recursivamente el subárbol izquierdo del nodo raíz, accediendo al nodo en sí, luego atravesando recursivamente el subárbol derecho del nodo, continuando este patrón con cada nodo en el árbol a medida que se accede recursivamente. Al igual que con todos los árboles binarios, se puede realizar un recorrido previo a la orden o un recorrido posterior a la orden, pero es probable que ninguno sea útil para los árboles de búsqueda binarios., Un recorrido en orden de un árbol de búsqueda binario siempre dará como resultado una lista ordenada de elementos de nodo (números, cadenas u otros elementos comparables).

el código para el recorrido en orden en Python se da a continuación. Llamará a callback (alguna función que el programador desea llamar en el valor del nodo, como imprimir en la pantalla) para cada nodo en el árbol.

Traversal requiere O (n) tiempo, ya que debe visitar cada nodo. Este algoritmo también es O (n), por lo que es asintóticamente óptimo.

Traversal también se puede implementar iterativamente. Para ciertas aplicaciones, p. ej., mayor búsqueda igual, Búsqueda aproximada, una operación de paso único (iterativo) recorrido puede ser muy útil. Esto es, por supuesto, implementado sin la construcción callback y toma O(1) en promedio y o (log n) en el peor de los casos.

VerificationEdit

a veces ya tenemos un árbol binario, y necesitamos determinar si es un BST. Este problema tiene una solución recursiva simple.,

la propiedad BST-cada nodo en el subárbol derecho tiene que ser más grande que el nodo actual y cada nodo en el subárbol izquierdo tiene que ser más pequeño que el nodo actual—es la clave para averiguar si un árbol es un BST o no. El algoritmo greedy – simplemente recorrer el árbol, en cada nodo comprobar si el nodo contiene un valor mayor que el valor en el hijo izquierdo y menor que el valor en el hijo derecho—no funciona para todos los casos., Considere el siguiente árbol:

 20 / \ 10 30 / \ 5 40

en el árbol anterior, cada nodo cumple con la condición de que el nodo contenga un valor mayor que su hijo izquierdo y menor que su hijo derecho, y sin embargo no es un BST: el valor 5 está en el subárbol derecho del nodo que contiene 20, una violación de la propiedad BST.

en lugar de tomar una decisión basada únicamente en los valores de un nodo y sus hijos, también necesitamos información que fluya hacia abajo desde el padre también., En el caso del árbol anterior, si pudiéramos recordar sobre el nodo que contiene el valor 20, veríamos que el nodo con el valor 5 está violando el contrato de propiedad BST.,

así que la condición que necesitamos comprobar en cada nodo es:

• si el nodo es el hijo izquierdo de su padre, entonces debe ser más pequeño que (o igual a) el padre y debe pasar el valor de su padre a su subárbol derecho para asegurarse de que ninguno de los nodos en ese subárbol es mayor que el padre
• si el nodo es el hijo derecho de su padre, entonces debe ser mayor que el padre y debe pasar el valor de su padre a su subárbol izquierdo para asegúrese de que ninguno de los nodos en ese subárbol es menor que el padre.,

una solución recursiva en C++ puede explicar esto más:

node->key+1y node->key-1 se hacen para permitir solo elementos distintos en BST.

si queremos que los mismos elementos también estén presentes, entonces podemos usar solo node->key en ambos lugares.

la llamada inicial a esta función puede ser algo como esto:

if (isBST(root, INT_MIN, INT_MAX)) { puts("This is a BST.");} else { puts("This is NOT a BST!");}

esencialmente seguimos creando un rango válido (a partir de ) y seguimos reduciéndolo para cada nodo a medida que bajamos recursivamente.,

como se señala en la sección # Traversal, un recorrido en orden de un árbol de búsqueda binario devuelve los nodos ordenados. Por lo tanto, solo necesitamos mantener el último nodo visitado mientras atravesamos el árbol y verificar si su clave es menor (o menor/igual, si se permiten duplicados en el árbol) en comparación con la clave actual.

algorítmoseditar

También hay algoritmos paralelos para árboles de búsqueda binarios, incluyendo insertar/eliminar múltiples elementos, construcción de matriz, filtrar con cierto predicador, aplanar a una matriz, fusionar/sustraer/intersecar dos árboles, etc., Estos algoritmos se pueden implementar usando algoritmos de árbol basados en join, que también pueden mantener el árbol equilibrado utilizando varios esquemas de equilibrio (incluyendo árbol AVL, árbol rojo-negro, árbol equilibrado de peso y treap) .