Download [ editar ] árboles binarios de búsqueda óptima

Notice something different? We've made a few improvements to Wikipedia. Learn
more!
Árbol binario de búsqueda
De Wikipedia, la enciclopedia libre
Saltar a navegación , búsqueda
Un árbol de búsqueda binaria de tamaño 9 y la profundidad de 3, con raíz y hojas de 8
1, 4, 7 y 13
En ciencias de la computación , un árbol binario de búsqueda (BST) o solicitarse en
árbol binario es un nodo basado en árbol binario estructura de datos que tiene las
siguientes propiedades: [1]



La izquierda subárbol de un nodo contiene sólo los nodos con claves de menos
de nodo tecla.
El subárbol derecho de un nodo contiene sólo los nodos con claves de mayor o
igual a la clave del nodo.
Tanto el subárboles izquierdo y derecho también debe ser árboles binarios de
búsqueda.
De las propiedades anteriores la consecuencia natural es que:

Cada nodo (elemento del árbol) tiene una clave distinta.
En general, la información representada por cada nodo es un registro en lugar de un
único elemento de datos. Sin embargo, para la secuenciación de los propósitos, los
nodos son comparados de acuerdo a sus teclas 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 relacionados con algoritmos de clasificación y algoritmos de búsqueda como
el recorrido en orden puede ser muy eficiente.
árboles binarios de búsqueda son fundamentales una estructura de datos utilizada para
construir estructuras de datos más abstractos, tales como conjuntos , conjuntos múltiples
, y arrays asociativos .
Contenido
[hide]






1 Operaciones
o
1,1 búsqueda
o
1.2 Inserción
o
1.3 Supresión
o
1.4 Traversal
o
Ordenar 1,5
2 Tipos
o
2.1 Comportamiento comparaciones
o
2,2 árboles de búsqueda binaria óptima
3 Véase también
4 Referencias
5 Véase también
6 Enlaces externos
[ editar ] Operaciones
Las operaciones en un árbol binario requieren comparaciones entre los nodos. Estas
comparaciones se hacen con llamadas a un comparador , que es una subrutina que
calcula el total del pedido (orden lineal) en cualquiera de los dos valores. Esta
comparación puede ser explícita o implícitamente definido, según el idioma en que se
aplica el BST.
[ editar ] Búsqueda
Buscando un árbol binario de un valor específico puede ser un recursivo o iterativo
proceso. Esta explicación abarca un método iterativo.
Comenzamos examinando el nodo raíz . Si el árbol es nulo, el valor que está buscando
no existe en el árbol. De lo contrario, si el valor es igual a la raíz, la búsqueda tiene
éxito. Si el valor es inferior a la raíz, busque en el subárbol izquierdo. Del mismo
modo, si ésta es superior a la raíz, busque en el subárbol derecho. Este proceso se repite
hasta que el valor se encuentra o el subárbol indicado es nulo. Si el valor buscado no se
encuentra ante un subárbol nula es alcanzado, entonces el tema no debe estar presente
en el árbol.
Aquí está el algoritmo de búsqueda en el lenguaje de programación Python :
# 'Nodo' se refiere a la relación padre-nodo en este caso
def search_binary_tree (nodo, clave):
si el nodo es None:
Ninguno de retorno que no se encuentra la tecla #
si el nodo <clave. clave:
search_binary_tree retorno (node. leftChild, clave)
elif nodo> clave. clave:
search_binary_tree retorno (node. rightChild, clave)
else: # clave es igual al nodo clave
nodo de retorno. valor # encontrados clave
... O equivalente Haskell :
searchBinaryTree NullNode _ = Nothing
searchBinaryTree clave (nodeKey nodeValue Nodo (leftChild,
rightChild)) =
caso comparar nodeKey clave de
LT - searchBinaryTree> Tecla leftChild
GT - searchBinaryTree> Tecla rightChild
EQ -> Solamente nodeValue
Esta operación requiere O (log n) en el caso promedio, pero necesita O (n) el tiempo en
el peor de los casos, cuando el árbol se parece a un desequilibrio lista enlazada ( árbol
degenerado ).
Suponiendo que BinarySearchTree es una clase con una función miembro "de
búsqueda (int)" y un puntero al nodo raíz, el algoritmo también es fácil de implementar
en términos de un enfoque iterativo. El algoritmo entra en un bucle, y decide si la rama
izquierda o derecha según el valor del nodo en cada nodo primario.
bool BinarySearchTree:: buscar (int val)
(
Nodo * siguiente = esto - root> ();
while (siguiente! = 0)
(
if (val == siguiente - valor> ())
(
return true;
)
else if (val <Los - valor> ())
(
next = siguiente - a la izquierda> ();
)
else if (val siguiente> - valor> ())
(
next = siguiente -> derecha ();
)
)
/ / No encontrado
return false;
)
Aquí está el algoritmo de búsqueda en el lenguaje de programación Java :
búsqueda booleana pública (nodo TreeNode, los datos int) (
if (nodo == null) (
return false;
)
if (node. getData () == data) (
return true;
) Else if (datos <nodo. GetData ()) (
/ / Datos deben estar en subárbol izquierdo
búsqueda de retorno (node. getLeft (), datos);
Else ()
/ / Datos deben estar en subárbol derecho
búsqueda de retorno (node. GetRight (), datos);
)
)
[ editar ] Inserción
La inserción comienza como una búsqueda comenzaría, si la raíz no es igual al valor,
buscamos la izquierda o derecha subárboles como antes. Con el tiempo, llegaremos a
un nodo externo y agregue el valor como su hijo derecho o izquierdo, dependiendo del
valor del nodo. En otras palabras, se examinan la raíz y de forma recursiva insertar el
nuevo nodo al subárbol izquierdo si el nuevo valor es inferior a la raíz, o el subárbol de
la derecha si el nuevo valor es mayor o igual a la raíz.
Así es como una típica búsqueda de la inserción árbol binario puede ser realizado en C
++:
/ * Inserta el nodo apuntado por "nodo_nuevo" en el subárbol con
raíz en "TreeNode" * /
insertarNodo vacío (* Nodo y TreeNode Nodo * nodo_nuevo)
(
if (TreeNode == NULL)
TreeNode = nodo_nuevo;
else if (nodo_nuevo - clave TreeNode <> -> Clave)
InsertarNodo (TreeNode - izquierda>, nodo_nuevo);
más
InsertarNodo (TreeNode -> derecha, nodo_nuevo);
)
Lo anterior "destructiva" variante de procedimiento modifica el árbol en su lugar.
Utiliza solamente el espacio constante, pero la versión anterior del árbol se pierde. Por
otra parte, como en el siguiente Python ejemplo, 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 de una estructura de datos persistente :
def binary_tree_insert (nodo, clave, valor):
si el nodo es None:
volver TreeNode (Ninguno, clave, valor, ninguno)
si la clave == nodo. clave:
TreeNode retorno (node. izquierda, la tecla, el valor, el
nodo. Derecha)
si el nodo <clave. clave:
volver TreeNode (binary_tree_insert (node. izquierda, clave,
valor), el nodo. clave, nodo. valor, nodo. derecha)
otra cosa:
TreeNode retorno (node. izquierda, nodo. Clave, nodo. Valor,
binary_tree_insert (node. derecho, clave, valor))
La parte que se vuelve a generar usos Θ (log n) de espacio en el caso promedio y Ω (n)
en el peor de los casos (véase la notación-O ).
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) en el caso promedio de todos los árboles,
pero (n Ω) tiempo en el peor de los casos.
Otra manera de explicar la inserción es que para insertar un nuevo nodo en el árbol, su
valor se compara primero con el valor de la raíz. Si su valor es inferior a la raíz, que se
compara con el valor del hijo izquierdo de la raíz. Si su valor es mayor, se la 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 añade como derecho de este nodo o un niño a la
izquierda, dependiendo de su valor.
Hay otras maneras de insertar nodos en un árbol binario, pero esta es la única manera
de insertar nodos en las hojas y, al mismo tiempo preservar la estructura de BST.
Aquí hay un enfoque iterativo para la inserción en un árbol de búsqueda binaria en el
Lenguaje de Programación Java :
public void insertar (datos int) (
if (raiz == null) (
root = TreeNode nueva (datos, null, null);
Else ()
TreeNode actual root =;
while (actual! = null) (
if (datos <actual. getData ()) (
/ / Inserto la izquierda
if (current. getLeft () == null) (
actual. setLeft (nuevo TreeNode
(datos, null, null));
de retorno;
Else ()
actual = actual. getLeft ();
)
Else ()
/ / Inserto la derecha
if (current. GetRight () == null) (
actual. setRight (nuevo
TreeNode (datos, null, null));
de retorno;
Else ()
actual = actual. GetRight ();
)
)
)
)
)
A continuación se muestra un enfoque recursivo al método de inserción. Como los
punteros no están disponibles en Java tenemos que devolver un puntero nuevo nodo a la
persona que llama como se indica por la línea final en el método.
pública insertar TreeNode (nodo TreeNode, los datos int) (
if (nodo == null) (
= nodo TreeNode nueva (datos, null, null);
Else ()
if (datos <nodo. getData ()) (
/ / Inserto la izquierda
nodo. izquierda = inserción (node. getLeft (),
datos);
Else ()
/ / Inserto la derecha
nodo. derecha = inserción (node. GetRight (),
datos);
)
)
volver nodo;
)
[ editar ] Supresión
Hay tres posibles casos a considerar:



Eliminación de una hoja (nodo sin hijos): Cómo eliminar una hoja es fácil, ya
que simplemente puede eliminarlo del árbol.
Eliminar un nodo con un hijo: Eliminarlo y sustituirlo por su hijo.
Eliminar un nodo con dos hijos: Llame al nodo que se borró "N". No elimine
N. En su lugar, elegir entre su nodo en el sucesor de orden o su nodo antecesor
en orden, "R". Vuelva a colocar el valor de N con el valor de R, a continuación,
elimine R. (Nota: R se tiene hasta un niño.)
Al igual que con todos los árboles binarios, en orden sucesor un nodo es el hijo más a
la izquierda de su subárbol derecho, y en orden un predecesor del nodo es el hijo más a
la derecha de su subárbol izquierdo. En cualquier caso, este nodo tiene cero o un niño.
Eliminar de acuerdo con uno de los dos casos más sencillos anteriores.
El uso constante de la orden o el sucesor en orden antecesor en cada instancia del caso
de dos niños-puede conducir a un desequilibrio de árboles, por lo que añadimos una
buena implementaciones inconsistencia de esta selección.
Tiempo de análisis: Aunque esta operación no siempre recorrer el árbol hasta una hoja,
esto es siempre una posibilidad, por lo que en el peor de los casos se requiere un tiempo
proporcional a la altura del árbol. No requiere más aún cuando el nodo tiene dos hijos,
dado que todavía sigue un camino único y no visita ningún nodo dos veces.
Este es el código en Python:
def findMin (self):
'''
Busca el elemento más pequeño que es un hijo de la libre * *
'''
current_node = auto
mientras current_node. left_child:
current_node = current_node. left_child
volver current_node
def replace_node_in_parent (self, = Ninguno new_value):
'''
Elimina la referencia a * * * * yo de self.parent y lo reemplaza
con * new_value *.
'''
si trabaja por cuenta propia ==. padres. left_child:
uno mismo. padres. left_child = new_value
otra cosa:
uno mismo. padres. right_child = new_value
si new_value:
new_value. padres = yo. padres
def binary_tree_delete (self, clave):
si <clave auto. clave:
uno mismo. left_child. binary_tree_delete (clave)
elif clave auto>. clave:
uno mismo. right_child. binary_tree_delete (clave)
else: # eliminar la clave aquí
si uno mismo. left_child y yo. right_child: # si ambos la
presencia de niños
# Obtiene el más pequeño nodo que es más grande que uno
mismo * *
sucesor = yo. right_child. findMin ()
key = sucesor. auto. clave
# * * Si el sucesor tiene un hijo, que se sustituya por
# En este momento, sólo puede tener un right_child * *
# Si no tiene hijos, * * right_child será "Ninguno"
sucesor. replace_node_in_parent (successor. right_child)
elif auto. left_child o por cuenta propia. right_child: # si
el nodo tiene un solo hijo
si uno mismo. left_child:
uno mismo. replace_node_in_parent (auto. left_child)
otra cosa:
uno mismo. replace_node_in_parent (auto. right_child)
else: # este nodo no tiene hijos
uno mismo. replace_node_in_parent (Ninguno)
[ editar ] Recorrido
Artículo principal: recorrido de árbol
Una vez que el árbol de búsqueda binaria se ha creado, sus elementos pueden ser
recuperados en orden de forma recursiva que atraviesa el subárbol izquierdo del nodo
raíz, el acceso a la misma nodo, a continuación, recorrer recursivamente el subárbol
derecho del nodo, continuando este patrón con cada nodo El árbol ya que es visitada de
forma recursiva. Al igual que con todos los árboles binarios, se puede realizar un
recorrido pre-orden o una orden de recorrido de post , pero tampoco son susceptibles de
ser utilizadas para los árboles binarios de búsqueda.
El código en el orden de recorrido en Python es la siguiente. Se ha previsto de
devolución de llamada para cada nodo en el árbol.
def traverse_binary_tree (nodo, de devolución de llamada):
si el nodo es None:
volver
traverse_binary_tree (node. leftChild, devolución de llamada)
de devolución de llamada (node. valor)
traverse_binary_tree (node. rightChild, devolución de llamada)
Traversal requiere Ω (n) el tiempo, ya que debe visitar cada nodo. Este algoritmo es O
(n), por lo que es asintóticamente óptima .
[ editar ] Ordenar
Un árbol de búsqueda binaria se puede utilizar para poner en práctica un sencillo pero
eficiente algoritmo de ordenación . Al igual que heapsort , insertamos todos los valores
que desea ordenar en nuevos ordenó la estructura de datos, en este caso un árbol de
búsqueda binaria, y luego recorrer en ella el orden, la construcción de nuestro resultado:
def build_binary_tree (valores):
árbol = Ninguno
para v en valores:
= árbol binary_tree_insert (árbol, v)
retorno de árboles
get_inorder_traversal def (root):
'''
Devuelve una lista que contiene todos los valores en el árbol,
comenzando en la raíz * *.
Recorre el árbol en orden (leftChild, raíz, rightChild).
'''
resultado = []
traverse_binary_tree (raíz, elemento lambda: resultado. append
(elemento))
return resultado
El caso peor tiempo de build_binary_tree es Θ (n 2)-Si le das una lista ordenada de
valores, se los encadena en una lista enlazada sin subárboles izquierdo. Por ejemplo,
traverse_binary_tree([1, 2, 3, 4, 5]) se obtiene el árbol (1 (2 (3 (4
(5))))) .
Hay varios planes para superar esta falencia con simples árboles binarios, el más
común es el de equilibrio de árbol binario de búsqueda auto . Si este mismo
procedimiento se realiza mediante un árbol, el peor de los casos el tiempo total es O (n
log n), que es asintóticamente óptima para un tipo de comparación . En la práctica, los
pobres caché de rendimiento y agregó sobrecarga en el tiempo y espacio para una base
tipo de árboles (en particular para el nodo de asignación ) que sea asintóticamente
óptima a otros tipos inferiores, tales como heapsort para ordenar la lista estática. Por
otra parte, es uno de los métodos más eficientes de selección adicionales, agregar
elementos a una lista con el tiempo, manteniendo la lista ordenada en todo momento.
[ editar ] Tipos
Hay muchos tipos de árboles binarios de búsqueda. AVL árboles y los árboles rojonegro son las formas de auto-equilibrio de los árboles binarios de búsqueda . Un árbol
de angulación es un árbol de búsqueda binaria que se mueve automáticamente visitada
con frecuencia los elementos más cerca de la raíz. En un treap ("árbol montón "), cada
nodo también tiene una prioridad y el nodo primario tiene mayor prioridad que a sus
hijos.
Otros dos títulos que describen los árboles de búsqueda binaria es que de un árbol
completo y degenerada.
Un árbol completo es un árbol con n niveles, donde para cada nivel d <= n - 1, el
número de nodos existentes a nivel d es igual a 2 d. Esto significa que todos los nodos
posibles existen en estos niveles. Un requisito adicional para que un árbol binario
completo es que para n º nivel, mientras que cada nodo no tiene que existir, los nodos
que existan deben llenar de izquierda a derecha.
Un árbol degenerado es un árbol donde cada nodo primario, sólo hay un nodo
secundario asociado. Lo que esto significa es que en una medición del rendimiento, el
árbol esencialmente se comportará como una lista enlazada estructura de datos.
[ editar ] comparaciones de rendimiento
DA Heger (2004) [2] presenta una comparación de rendimiento de los árboles binarios
de búsqueda. Treap se encontró que la media de mejor rendimiento, mientras que -negro
árbol rojo se encontró que la cantidad más pequeña de las fluctuaciones de rendimiento.
[ editar ] árboles binarios de búsqueda óptima
Si no va a modificar un árbol de búsqueda, y sabemos exactamente con qué frecuencia
cada artículo será accesible, podemos construir un árbol binario de búsqueda óptimo,
que es un árbol de búsqueda donde el coste medio de buscar un artículo (el esperado
coste de búsqueda) se reduce al mínimo.
Incluso si sólo tenemos estimaciones de los costos de búsqueda, este sistema puede
acelerar considerablemente las búsquedas en promedio. Por ejemplo, si usted tiene una
BST de las palabras utilizadas en Inglés un corrector ortográfico , que podría equilibrar
el árbol basado en la frecuencia de palabras en el corpus de texto , colocando palabras
como "el" cerca de la raíz y palabras como "agerasia" cerca de las hojas. Este árbol
puede ser comparado con los árboles Huffman , que igualmente pretenden poner
Artículos de uso frecuente cerca de la raíz a fin de producir una densa información de
codificación, sin embargo, los árboles Huffman elementos de datos única tienda en
hojas, y esos elementos no tiene que ser ordenado.
Si no sabemos la secuencia en que los elementos en el árbol se tendrá acceso con
antelación, podemos utilizar árboles splay que son asintóticamente tan bueno como
cualquier árbol de búsqueda estática podemos construir para cualquier secuencia
particular de operaciones de búsqueda.
alfabético árboles son árboles Huffman con la restricción adicional sobre el orden, o,
equivalentemente, árboles de búsqueda con la modificación que todos los elementos se
almacenan en las hojas. algoritmos más rápidos existentes para una óptima árboles
binarios alfabéticos (OABTs).
Ejemplo:
procedimiento de búsqueda del árbol óptimo (f, f, c):
para j = 0 hasta n hacer
c [j, j] = 0, M j [, j] = f'j
para d = 1 hasta n hacer
para i = 0 a (n - d) hacer
j = i + d
M [i, j] = F [i, j - 1] + f '+ f'j
c [i, j] = MIN (i <k <= j) (c [i, k - 1] + c [k, j]) + F [i, j]
[ editar ] Véase también






Búsqueda binaria
Árbol binario
Uno mismo-equilibrio del árbol de búsqueda binaria
árbol de búsqueda binaria aleatorios
B-tree