En ciencias de la computación , un árbol binario de búsqueda ( BST ), también llamado ordenado o ordenados árbol binario , es un arraigado árbol binario cuyos nodos internos cada tienda una mayor tecla que no todas las claves en subárbol izquierdo del nodo y menos que los de su derecha subárbol. Un árbol binario es un tipo de estructura de datos para almacenar datos como números de forma organizada. 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, y se pueden utilizar para implementar conjuntos dinámicos y tablas de búsqueda.. El orden de los nodos en un medio BST que cada comparación se salta sobre medio del árbol restante, por lo que toda la búsqueda lleva tiempo proporcional a la logaritmo binario del número de elementos almacenados en el árbol. Esto es mucho mejor que el tiempo lineal requerido para encontrar elementos por clave en una matriz (sin clasificar), pero más lento que las operaciones correspondientes en tablas hash . Se han estudiado varias variantes del árbol de búsqueda binaria.
Árbol de búsqueda binaria | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | árbol | ||||||||||||||||||||
Inventado | 1960 | ||||||||||||||||||||
Inventado por | PF Windley, AD Booth , AJT Colin y TN Hibbard | ||||||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||||||
|
Definición
Un árbol de búsqueda binaria es un árbol binario enraizado , cuyos nodos internos almacenan cada uno una clave (y, opcionalmente, un valor asociado), y cada uno tiene dos subárboles distinguidos, comúnmente denominados izquierda y derecha . El árbol además satisface la propiedad de búsqueda binaria : la clave en cada nodo es mayor o igual que cualquier clave almacenada en el subárbol izquierdo, y menor o igual que cualquier clave almacenada en el subárbol derecho. [1] : 287 Las hojas (nodos finales) del árbol no contienen clave y no tienen estructura para distinguirlas unas de otras.
A menudo, la información representada por cada nodo es un registro en lugar de un solo elemento de datos. Sin embargo, para fines de secuenciación, los nodos se comparan según sus claves en lugar de cualquier parte de sus registros asociados. La principal ventaja de los árboles de búsqueda binaria sobre otras estructuras de datos es que los algoritmos de clasificación relacionados y los algoritmos de búsqueda , como el recorrido en orden, pueden ser muy eficientes.
Árboles binarios de búsqueda son un elemento fundamental estructura de datos utilizada para construir estructuras de datos más abstractos tales como conjuntos , conjuntos múltiples y matrices asociativas .
- Al insertar o buscar un elemento en un árbol de búsqueda binario, la clave de cada nodo visitado debe compararse con la clave del elemento a insertar o encontrar.
- La forma del árbol de búsqueda binaria depende completamente del orden de inserciones y eliminaciones y puede volverse degenerado.
- Después de una larga secuencia entremezclada de inserción y eliminación aleatoria, la altura esperada del árbol se acerca a la raíz cuadrada del número de claves, √ n , [ cita requerida ] que crece mucho más rápido que log n .
- Se han realizado muchas investigaciones para evitar la degeneración del árbol, lo que resulta en la complejidad temporal del peor de los casos de O ( n ) (para más detalles, consulte la sección Tipos ).
Relación de pedido
La búsqueda binaria requiere una relación de orden mediante la cual cada elemento (artículo) se puede comparar con cualquier otro elemento en el sentido de un preorden total . La parte del elemento que efectivamente tiene lugar en la comparación se llama clave . Ya sean duplicados, i. mi. diferentes elementos con la misma clave, se permitirán en el árbol o no, no depende de la relación de orden, sino solo de la aplicación. Para una función de búsqueda que admita y maneje duplicados en un árbol, consulte la sección Búsqueda con duplicados permitidos .
En el contexto de los árboles de búsqueda binarios, un preorden total se realiza de forma más flexible mediante una subrutina de comparación de tres vías .
Operaciones
Los árboles de búsqueda binaria admiten tres operaciones principales: inserción de elementos, eliminación de elementos y búsqueda (verificando si hay una clave presente).
buscando
La búsqueda en un árbol de búsqueda binaria de una clave específica se puede programar de forma recursiva o iterativa .
Comenzamos examinando el nodo raíz . Si el árbol es nulo , 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 en 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 ):
def search_recursively ( clave , nodo ): si el nodo es Ninguno o clave == nodo . clave : nodo de retorno si clave < nodo . clave : volver search_recursively ( clave , nodo . izquierda ) volver search_recursively ( clave , nodo . derecha )
El mismo algoritmo se puede implementar de forma iterativa:
def buscar_iterativamente ( clave , nodo ): mientras que el nodo no es Ninguno y nodo . clave ! = clave : si clave < nodo . clave : nodo = nodo . izquierda otra cosa : nodo = nodo . derecho nodo de retorno
Estos dos ejemplos no admiten duplicados, es decir, consideran el árbol totalmente ordenado.
Se puede notar que el algoritmo recursivo es recursivo de cola . En un lenguaje que admita 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 lleva un tiempo proporcional a la altura del árbol (consulte la terminología del árbol ). En promedio, los árboles de búsqueda binaria con claves de nodos tienen una altura de O (log | Nodes |) . [nota 1] Sin embargo, en el peor de los casos, los árboles de búsqueda binarios pueden tener una altura de O (| Nodos |) , cuando el árbol desequilibrado se asemeja a una lista enlazada ( árbol degenerado ).
Se permite la búsqueda con duplicados
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 igualdad buscar hasta las hojas. De este modo, permite especificar (o cablear) una dirección, donde insertar un duplicado, ya sea a la derecha o izquierda de todos los duplicados en el árbol hasta el momento. Si la dirección está cableada, ambas opciones, derecha e izquierda, admiten una pila con insertar duplicado como operación de inserción y eliminar como operación emergente. [2] : 155
def search_duplicatesAllowed ( clave , nodo ): new_node = nodo while new_node ! = Ninguno : current_node = new_node si clave < current_node . clave : dir = 0 # IZQUIERDA else : # clave> = current_node.key: dir = 1 # DERECHA new_node = current_node . niño [ dir ] return ( dir , nodo_actual )
Un tipo de árbol binario equipado con dicha función de búsqueda se vuelve estable .
Inserción
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 el subárbol derecho si su clave es mayor o igual que la raíz.
Así es como se puede realizar una inserción típica de árbol de búsqueda binaria en un árbol binario en C ++ :
insertar vacío ( Nodo * & root , clave int , valor int ) { if ( ! root ) root = new Node ( clave , valor ); else if ( clave == raíz -> clave ) raíz -> valor = valor ; else if ( clave < raíz -> clave ) insertar ( raíz -> izquierda , clave , valor ); else // clave> raíz-> insertar clave ( raíz -> derecha , clave , valor ); }
Alternativamente, se podría implementar una versión no recursiva como esta. El uso de un puntero a puntero para realizar un seguimiento de dónde venimos permite que el código evite la verificación explícita y el manejo del caso en el que necesita insertar un nodo en la raíz del árbol: [3]
nula inserción ( Nodo ** raíz , int clave , int valor ) { Nodo ** pie = raíz ; while ( * caminar ) { int curkey = ( * caminar ) -> tecla ; if ( curkey == key ) { ( * caminar ) -> valor = valor ; volver ; } if ( tecla > curkey ) caminar = & ( * caminar ) -> derecha ; else caminar = & ( * caminar ) -> izquierda ; } * caminar = nuevo Nodo ( clave , valor ); }
La variante de procedimiento destructiva 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, lo que hace que el árbol sea una estructura de datos persistente :
def binary_tree_insert ( nodo , clave , valor ): si nodo == Ninguno : devuelve NodeTree ( Ninguno , clave , valor , Ninguno ) si clave == nodo . clave : devuelve NodeTree ( nodo . izquierda , clave , valor , nodo . derecha ) si clave < nodo . clave : return NodeTree ( binary_tree_insert ( nodo . izquierda , clave , valor ), nodo . clave , nodo . valor , nodo . derecha ) return NodeTree ( nodo . izquierda , nodo . clave , nodo . valor , binary_tree_insert ( nodo . derecha , clave , valor ))
La parte que se reconstruye usa 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 un 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, primero se compara su clave con la de la raíz. Si su clave es menor que la de la raíz, 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 la de la hoja. hijo izquierdo, 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.
Supresión
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 [4] garantiza que las alturas de los subárboles sujetos se cambian como máximo en uno. Hay tres casos posibles a considerar:
- Eliminar un nodo sin hijos: simplemente elimine el nodo del árbol.
- Eliminación de un nodo con un hijo: elimine el nodo y reemplácelo con su hijo.
- La eliminación de un nodo D con dos hijos: seleccione el controlador D 's en orden predecesor o sucesor en orden E (ver figura). En lugar de eliminar D , sobrescribir la clave y el valor de E s'. [Nota 2] Si E no tiene un niño, retire E de su matriz anterior G . Si E tiene un hijo F , es un hijo correcto, de modo que debe reemplazar a E en el padre de E.
En todos los casos, cuando D sea la raíz, vuelva a hacer que el nodo de reemplazo sea la raíz.
Los nodos con dos hijos son más difíciles de eliminar. El sucesor en orden de un nodo es el hijo más a la izquierda de su subárbol derecho, y el predecesor en orden de un nodo es el hijo más a la derecha del subárbol izquierdo. En cualquier caso, este nodo tendrá solo uno o ningún hijo. Bórrelo de acuerdo con uno de los dos casos más simples anteriores.
El uso constante del sucesor en orden o del predecesor en orden para cada instancia del caso de dos hijos puede generar un árbol desequilibrado , por lo que algunas implementaciones seleccionan una u otra en momentos diferentes.
Análisis en tiempo de ejecución: aunque esta operación no siempre atraviesa el árbol hasta una hoja, siempre es una posibilidad; por 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 un solo camino y no visita ningún nodo dos veces.
def find_min ( self ): "" "Obtiene el nodo mínimo en un subárbol." "" current_node = self mientras current_node . left_child : current_node = current_node . left_child return current_nodedef replace_node_in_parent ( self , new_value = None ) -> None : if self . padre : if self == self . los padres . hijo_izquierdo : self . los padres . hijo_izquierdo = nuevo_valor else : self . los padres . niño_derecho = nuevo_valor si nuevo_valor : nuevo_valor . padre = yo . padredef binary_tree_delete ( self , key ) -> Ninguno : if key < self . clave : yo . left_child . binary_tree_delete ( clave ) return si clave > self . clave : yo . niño_derecho . binary_tree_delete ( key ) return # Elimina la clave aquí si es self . left_child y self . right_child : # Si ambos hijos están presentes sucesor = self . niño_derecho . find_min () self . clave = sucesor . sucesor clave . binary_tree_delete ( sucesor . llave ) elif auto . left_child : # Si el nodo solo tiene un yo hijo * izquierdo * . replace_node_in_parent ( self . left_child ) elif self . right_child : # Si el nodo tiene sólo un yo hijo * derecho * . replace_node_in_parent ( self . right_child ) else : self . replace_node_in_parent ( None ) # Este nodo no tiene hijos
El recorrido
Una vez que se ha creado el árbol de búsqueda binaria, sus elementos pueden ser recuperados en orden por recursiva atravesar el subárbol izquierdo del nodo raíz, el acceso al propio nodo, entonces la exploración recursiva el subárbol derecho del nodo, continuando este patrón con cada nodo el árbol a medida que se accede de forma recursiva. Al igual que con todos los árboles binarios, se puede realizar un recorrido previo al pedido o un recorrido posterior al pedido , pero es probable que ninguno de ellos 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 proporciona a continuación. Llamará a la devolución de llamada (alguna función que el programador desee llamar en el valor del nodo, como imprimir en la pantalla) para cada nodo en el árbol.
def traverse_binary_tree ( nodo , devolución de llamada ): if node == None : return traverse_binary_tree ( node . leftChild , callback ) callback ( nodo . valor ) traverse_binary_tree ( node . rightChild , callback )
Cada forma de primer recorrido de profundidad de árbol binario requiere 2 × ( n -1) ∈ O ( n ) tiempo, ya que visita cada arco exactamente dos veces (una vez hacia abajo, una vez hacia arriba) mientras visita cada nodo. Este algoritmo también es O ( n ) , por lo que es asintóticamente óptimo .
El recorrido también se puede implementar de forma iterativa . Para ciertas aplicaciones, por ejemplo, búsqueda igual mayor, búsqueda aproximada, una operación paraEl recorrido de un solo paso (iterativo) puede ser muy útil. Esto, por supuesto, se implementa sin la construcción de devolución de llamada y toma O (1) en promedio y O (log n ) en el peor de los casos.
Verificación
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 del subárbol derecho debe ser más grande que el nodo actual y cada nodo del subárbol izquierdo debe ser más pequeño que el nodo actual) es la clave para determinar si un árbol es un BST o no. El algoritmo codicioso —simplemente atraviesa el árbol, en cada nodo verifica si el nodo contiene un valor mayor que el valor del hijo izquierdo y menor que el valor del hijo derecho— no funciona en todos los casos. Considere el siguiente árbol:
20 / \ 10 30 / \ 5 40
En el árbol de arriba, cada nodo cumple la condición de que el nodo contiene un valor mayor que su hijo izquierdo y más pequeño 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 desde el padre. 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.
Entonces, la condición que debemos verificar en cada nodo es:
- si el nodo es el hijo izquierdo de su padre, entonces debe ser más pequeño (o igual) que 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 sea mayor que el padre
- si el nodo es el hijo derecho de su padre, entonces debe ser más grande que el padre y debe pasar el valor de su padre al subárbol izquierdo para asegurarse de que ninguno de los nodos en ese subárbol sea menor que el padre.
Una solución recursiva en C ++ puede explicar esto con más detalle:
struct TreeNode { clave int ; valor int ; struct TreeNode * left ; struct TreeNode * right ; }; bool isBST ( struct TreeNode * node , int minKey , int maxKey ) { if ( nodo == NULL ) return true ; if ( nodo -> clave < minKey || nodo -> clave > maxKey ) devuelve falso ; return isBST ( nodo -> izquierda , clave mínima , nodo -> clave -1 ) && isBST ( nodo -> derecha , nodo -> clave + 1 , clave máxima ); }
node->key+1
y node->key-1
están hechos para permitir solo elementos distintos en BST.
Si queremos que también estén presentes los mismos elementos, solo podemos usarlos node->key
en ambos lugares.
La llamada inicial a esta función puede ser algo como esto:
si ( isBST ( raíz , INT_MIN , INT_MAX )) { puts ( "Este es un BST." ); } else { put ( "¡Esto NO es un BST!" ); }
Básicamente, seguimos creando un rango válido (comenzando desde [MIN_VALUE, MAX_VALUE]) y seguimos reduciéndolo para cada nodo a medida que bajamos de forma recursiva.
Como se señaló 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 más pequeña (o más pequeña / igual, si se permiten duplicados en el árbol) en comparación con la clave actual.
Algoritmos paralelos
También hay algoritmos paralelos para árboles de búsqueda binarios, que incluyen insertar / eliminar múltiples elementos, construcción a partir de una matriz, filtrar con cierto predicador, aplanar a una matriz, fusionar / restar / intersecar dos árboles, etc. Estos algoritmos se pueden implementar usando uniones basadas en algoritmos de árbol , que también pueden mantener el árbol equilibrado mediante varios esquemas de equilibrio (incluido el árbol AVL , el árbol rojo-negro , el árbol con equilibrio de peso y el treap ).
Ejemplos de aplicaciones
Clasificar
Se puede utilizar un árbol de búsqueda binario para implementar un algoritmo de clasificación simple . Al igual que en heapsort , insertamos todos los valores que deseamos clasificar en una nueva estructura de datos ordenada, en este caso un árbol de búsqueda binaria, y luego lo recorremos en orden.
El momento en el peor de los casos build_binary_tree
es O ( n 2 ): si lo alimenta con una lista ordenada de valores, los encadena en una lista vinculada sin subárboles a la izquierda. Por ejemplo, build_binary_tree([1, 2, 3, 4, 5])
cede el árbol (1 (2 (3 (4 (5)))))
.
Hay varios esquemas para superar esta falla con árboles binarios simples; el más común es el árbol de búsqueda binario autoequilibrado . Si este mismo procedimiento se realiza utilizando un árbol de este tipo, el tiempo total en el peor de los casos es O ( n log n ) , que es asintóticamente óptimo para una clasificación de comparación . En la práctica, la sobrecarga adicional en tiempo y espacio para una ordenación basada en árboles (particularmente para la asignación de nodos ) la hace inferior a otras ordenaciones asintóticamente óptimas como heapsort para la ordenación de listas estáticas. Por otro lado, es uno de los métodos más eficientes de clasificación incremental , agregando elementos a una lista a lo largo del tiempo y manteniendo la lista ordenada en todo momento.
Operaciones de cola de prioridad
Los árboles de búsqueda binarios pueden servir como colas de prioridad : estructuras que permiten la inserción de claves arbitrarias, así como la búsqueda y eliminación de la clave mínima (o máxima). La inserción funciona como se explicó anteriormente. Find-min camina por el árbol, siguiendo los indicadores de la izquierda tanto como puede sin tocar una hoja:
// Precondición: T no es una función hoja find-min (T): while hasLeft (T): T? izquierda (T) tecla de retorno (T)
Find-max es análogo: siga los punteros de la derecha en la medida de lo posible. Delete-min ( max ) puede simplemente buscar el mínimo (máximo) y luego eliminarlo. De esta manera, tanto la inserción como la eliminación toman un tiempo logarítmico, tal como lo hacen en un montón binario , pero a diferencia de un montón binario y la mayoría de las otras implementaciones de colas de prioridad, un solo árbol puede admitir todos los archivos find-min , find-max , delete-min. y delete-max al mismo tiempo, lo que hace que los árboles de búsqueda binarios sean adecuados como colas de prioridad de dos extremos . [2] : 156
Tipos
Hay muchos tipos de árboles de búsqueda binarios. Los árboles AVL y los árboles rojo-negro son ambas formas de árboles de búsqueda binarios autoequilibrados . Un árbol de distribución es un árbol de búsqueda binario que mueve automáticamente los elementos a los que se accede con frecuencia más cerca de la raíz. En un treap ( montón de árbol ), cada nodo también tiene una prioridad (elegida al azar) y el nodo padre tiene una prioridad más alta que sus hijos. Los árboles de tango son árboles optimizados para búsquedas rápidas. Los árboles T son árboles de búsqueda binarios optimizados para reducir la sobrecarga de espacio de almacenamiento, ampliamente utilizados para bases de datos en memoria.
Un árbol degenerado es un árbol donde para cada nodo padre, solo hay un nodo hijo asociado. Está desequilibrado y, en el peor de los casos, el rendimiento se degrada al de una lista vinculada. Si su función de agregar nodo no maneja el reequilibrio, entonces puede construir fácilmente un árbol degenerado alimentándolo con datos que ya están ordenados. Lo que esto significa es que en una medición de rendimiento, el árbol se comportará esencialmente como una estructura de datos de lista enlazada.
Comparaciones de desempeño
DA Heger (2004) [5] presentó una comparación de rendimiento de árboles de búsqueda binarios. Se encontró que Treap tiene el mejor desempeño promedio, mientras que el árbol rojo-negro tiene el menor número de variaciones de desempeño.
Árboles de búsqueda binarios óptimos
Si no se pretende modificar un árbol de búsqueda y se sabe exactamente con qué frecuencia se accederá a cada elemento, es posible construir [6] un árbol de búsqueda binario óptimo , que es un árbol de búsqueda donde el costo promedio de buscar un artículo (el costo de búsqueda esperado ) se minimiza.
Incluso si solo tenemos estimaciones de los costos de búsqueda, dicho sistema puede acelerar considerablemente las búsquedas en promedio. Por ejemplo, si tenemos una BST de palabras en inglés utilizadas en un corrector ortográfico , podríamos equilibrar el árbol en función de la frecuencia de palabras en los corpus de texto , colocando palabras como the cerca de la raíz y palabras como agerasia cerca de las hojas. Tal árbol podría compararse con los árboles de Huffman , que de manera similar buscan colocar elementos de uso frecuente cerca de la raíz para producir una codificación de información densa; sin embargo, los árboles de Huffman almacenan elementos de datos solo en hojas y no es necesario ordenar estos elementos.
Si la secuencia en la que se accederá a los elementos del árbol se desconoce de antemano, se pueden usar árboles de splay que son asintóticamente tan buenos como cualquier árbol de búsqueda estática que podamos construir para cualquier secuencia particular de operaciones de búsqueda.
Los árboles alfabéticos son árboles de Huffman con la restricción adicional de orden o, de manera equivalente, árboles de búsqueda con la modificación de que todos los elementos se almacenan en las hojas. Existen algoritmos más rápidos para árboles binarios alfabéticos óptimos (OABT).
Ver también
- Algoritmo de búsqueda binaria
- Árbol de búsqueda
- Árbol de búsqueda binaria autoequilibrado
- Árbol AVL
- Árbol rojo-negro
- Árbol de búsqueda binario aleatorio
- Árbol de tango
- Algoritmos de árbol basados en uniones
- Treap
- Árbol de peso equilibrado
Notas
- ^ La noción de BST promedio se precisa de la siguiente manera. Sea una BST aleatoria construida utilizando solo inserciones de una secuencia de elementos únicos en orden aleatorio (todas las permutaciones son igualmente probables); entonces laaltura esperada del árbol es O (log | Nodes |) . Si se permiten tanto las supresiones como las inserciones, "se sabe poco sobre la altura media de un árbol de búsqueda binaria". [1] : 300
- ^ Por supuesto, un paquete de software genérico tiene que trabajar al revés: Tiene que dejar los datos del usuario sin tocar y le proporcionen E con todos los enlaces hacia y desde BST D .
Referencias
- ↑ a b Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03384-4.
- ^ a b Mehlhorn, Kurt ; Sanders, Peter (2008). Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) . Saltador.
- ^ Trubetskoy, Gregory. "Linus sobre la comprensión de los punteros" . Consultado el 21 de febrero de 2019 .
- ^ Robert Sedgewick , Kevin Wayne: Cuarta edición de algoritmos. Pearson Education, 2011, ISBN 978-0-321-57351-3 , pág. 410.
- ^ Heger, Dominique A. (2004), "A Disquisition on The Performance Behavior of Binary Search Tree Data Structures" (PDF) , European Journal for the Informatics Professional , 5 (5): 67–75, archivado desde el original (PDF) el 2014-03-27 , consultado el 2010-10-16
- ^ Gonnet, Gaston. "Árboles de búsqueda binarios óptimos" . Computación científica . ETH Zürich. Archivado desde el original el 12 de octubre de 2014 . Consultado el 1 de diciembre de 2013 .
Otras lecturas
- Este artículo incorpora material de dominio público del documento NIST : Black, Paul E. "Árbol de búsqueda binaria" . Diccionario de algoritmos y estructuras de datos .
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "12: árboles de búsqueda binaria, 15,5: árboles de búsqueda binaria óptimos". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. págs. 253–272, 356–363. ISBN 0-262-03293-7.
- Jarc, Duane J. (3 de diciembre de 2005). "Recorridos de árboles binarios" . Visualizaciones interactivas de estructura de datos . Universidad de Maryland . Archivado desde el original el 27 de febrero de 2014 . Consultado el 30 de abril de 2006 .
- Knuth, Donald (1997). "6.2.2: Búsqueda de árbol binario". El arte de la programación informática . 3: "Ordenar y buscar" (3ª ed.). Addison-Wesley. págs. 426–458. ISBN 0-201-89685-0.
- Largo, Sean. "Árbol de búsqueda binaria" ( PPT ) . Visualización de estructuras de datos y algoritmos: un enfoque basado en diapositivas de PowerPoint . SUNY Oneonta .
- Parlante, Nick (2001). "Árboles binarios" . Biblioteca de educación de CS . Universidad de Stanford .
enlaces externos
- Visualizador de árbol binario (animación JavaScript de varias estructuras de datos basadas en BT)