Un árbol binario de búsqueda (ABB) es un arbol binario definido de la siguiente forma:
Todo árbol vacío es un árbol binario de búsqueda.
Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
• En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo
almacenado en el subárbol izquierdo, y que el
subárbol izquierdo sea un árbol binario de búsqueda.
• En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo
almacenado en el subárbol derecho, y que el
subárbol derecho sea un árbol binario de búsqueda.
los árboles binarios de búsqueda radica en que su recorrido inorden
proporciona los elementos ordenados de forma ascendente
y en que la búsqueda de algún elemento suele ser muy eficiente.
Dependiendo de las necesidades del usuario que trate con una estructura
de este tipo se podrá permitir la igualdad estricta en alguno,
en ninguno o en ambos de los subárboles que penden de la raíz.
Permitir el uso de la igualdad provoca la aparición de valores dobles
y hace la búsqueda más compleja.
Todas las operaciones realizadas sobre árboles binarios de búsqueda
están basadas en la comparación de los elementos o clave de los mismos,
por lo que es necesaria una subrutina, que puede estar predefinida en el lenguaje de programacion,
que los compare y pueda establecer una relación de orden entre ellos,
es decir, que dados dos elementos sea capaz de reconocer cual es mayor
y cual menor. Se habla de clave de un elemento porque en la mayoría de
los casos el contenido de los nodos será otro tipo de estructura y es
necesario que la comparación se haga sobre algún campo al que se denomina clave.
Descargar:
Algoritmo
JAVA
.
