binary search tree java implementation code examples
Este tutorial cubre el árbol de búsqueda binaria en Java. Aprenderá a crear un BST, insertar, eliminar y buscar un elemento, recorrer e implementar un BST en Java:
Un árbol de búsqueda binario (denominado BST en lo sucesivo) es un tipo de árbol binario. También se puede definir como un árbol binario basado en nodos. BST también se conoce como 'árbol binario ordenado'. En BST, todos los nodos del subárbol izquierdo tienen valores que son menores que el valor del nodo raíz.
De manera similar, todos los nodos del subárbol derecho de la BST tienen valores que son mayores que el valor del nodo raíz. Este orden de los nodos también debe ser válido para los respectivos subárboles.
=> Visite aquí para ver la serie exclusiva de tutoriales de capacitación en Java.
Lo que vas a aprender:
- Árbol de búsqueda binaria en Java
- Conclusión
Árbol de búsqueda binaria en Java
Un BST no permite nodos duplicados.
El siguiente diagrama muestra una representación BST:
Arriba se muestra un ejemplo de BST. Vemos que 20 es el nodo raíz de este árbol. El subárbol izquierdo tiene todos los valores de los nodos que son menores que 20. El subárbol derecho tiene todos los nodos que son mayores que 20. Podemos decir que el árbol anterior cumple con las propiedades de BST.
Se considera que la estructura de datos BST es muy eficiente en comparación con las matrices y la lista vinculada cuando se trata de inserción / eliminación y búsqueda de elementos.
BST tarda O (log n) en buscar un elemento. A medida que se ordenan los elementos, la mitad del subárbol se descarta en cada paso mientras se busca un elemento. Esto es posible porque podemos determinar fácilmente la ubicación aproximada del elemento a buscar.
De manera similar, las operaciones de inserción y eliminación son más eficientes en BST. Cuando queremos insertar un nuevo elemento, sabemos aproximadamente en qué subárbol (izquierdo o derecho) insertaremos el elemento.
Creación de un árbol de búsqueda binaria (BST)
Dada una serie de elementos, necesitamos construir una BST.
Hagamos esto como se muestra a continuación:
Matriz dada: 45, 10, 7, 90, 12, 50, 13, 39, 57
Consideremos primero el elemento superior, es decir, 45 como el nodo raíz. A partir de aquí continuaremos creando el BST considerando las propiedades ya discutidas.
Para crear un árbol, compararemos cada elemento de la matriz con la raíz. Luego colocaremos el elemento en una posición apropiada en el árbol.
El proceso completo de creación de BST se muestra a continuación.
Operaciones de árbol de búsqueda binaria
BST admite varias operaciones. La siguiente tabla muestra los métodos admitidos por BST en Java. Analizaremos cada uno de estos métodos por separado.
| Método / operación | Descripción |
|---|---|
| Insertar | Agregue un elemento al BST sin violar las propiedades del BST. |
| Borrar | Elimina un nodo determinado del BST. El nodo puede ser el nodo raíz, no hoja o nodo hoja. |
| Buscar | Busque la ubicación del elemento dado en el BST. Esta operación comprueba si el árbol contiene la clave especificada. |
Insertar un elemento en BST
Un elemento siempre se inserta como nodo hoja en BST.
A continuación se muestran los pasos para insertar un elemento.
- Empiece desde la raíz.
- Compare el elemento a insertar con el nodo raíz. Si es menor que la raíz, atraviesa el subárbol izquierdo o atraviesa el subárbol derecho.
- Atraviese el subárbol hasta el final del subárbol deseado. Inserte el nodo en el subárbol correspondiente como nodo hoja.
Veamos una ilustración de la operación de inserción de BST.
Considere la siguiente BST e insertemos el elemento 2 en el árbol.
La operación de inserción para BST se muestra arriba. En la figura (1), mostramos la ruta que recorremos para insertar el elemento 2 en la BST. También hemos mostrado las condiciones que se verifican en cada nodo. Como resultado de la comparación recursiva, el elemento 2 se inserta como el hijo derecho de 1 como se muestra en la figura (2).
Operación de búsqueda en BST
Para buscar si un elemento está presente en la BST, nuevamente comenzamos desde la raíz y luego atravesamos el subárbol izquierdo o derecho, dependiendo de si el elemento a buscar es menor o mayor que la raíz.
A continuación se enumeran los pasos que debemos seguir.
- Compare el elemento a buscar con el nodo raíz.
- Si la clave (elemento a buscar) = root, devuelve root node.
- Else if clave
- De lo contrario, recorra el subárbol derecho.
- Compare repetidamente los elementos del subárbol hasta que se encuentre la clave o se alcance el final del árbol.
Ilustremos la operación de búsqueda con un ejemplo. Considere que tenemos que buscar la clave = 12.
En la siguiente figura, trazaremos la ruta que seguimos para buscar este elemento.
Como se muestra en la figura anterior, primero comparamos la clave con la raíz. Como la clave es mayor, atravesamos el subárbol derecho. En el subárbol derecho, volvemos a comparar la clave con el primer nodo del subárbol derecho.
Encontramos que la clave es menor que 15. Entonces nos movemos al subárbol izquierdo del nodo 15. El nodo izquierdo inmediato de 15 es 12 que coincide con la clave. En este punto, detenemos la búsqueda y devolvemos el resultado.
Quitar elemento del BST
Cuando eliminamos un nodo de la BST, existen tres posibilidades, como se explica a continuación:
El nodo es un nodo de hoja
Si un nodo que se va a eliminar es un nodo hoja, entonces podemos eliminarlo directamente ya que no tiene nodos secundarios. Esto se muestra en la siguiente imagen.
Como se muestra arriba, el nodo 12 es un nodo hoja y se puede eliminar de inmediato.
El nodo tiene un solo hijo
Cuando necesitamos eliminar el nodo que tiene un hijo, copiamos el valor del hijo en el nodo y luego eliminamos el hijo.
En el diagrama anterior, queremos eliminar el nodo 90 que tiene un hijo 50. Entonces intercambiamos el valor 50 con 90 y luego eliminamos el nodo 90, que ahora es un nodo hijo.
El nodo tiene dos hijos
Cuando un nodo a eliminar tiene dos hijos, entonces reemplazamos el nodo con el sucesor en orden (raíz izquierda-derecha) del nodo o simplemente dijimos el nodo mínimo en el subárbol derecho si el subárbol derecho del nodo no está vacío. Reemplazamos el nodo con este nodo mínimo y eliminamos el nodo.
En el diagrama anterior, queremos eliminar el nodo 45, que es el nodo raíz de BST. Encontramos que el subárbol derecho de este nodo no está vacío. Luego atravesamos el subárbol derecho y encontramos que el nodo 50 es el nodo mínimo aquí. Entonces reemplazamos este valor en lugar de 45 y luego eliminamos 45.
Si revisamos el árbol, vemos que cumple las propiedades de una BST. Por tanto, el reemplazo del nodo fue correcto.
Implementación del árbol de búsqueda binaria (BST) en Java
El siguiente programa en Java proporciona una demostración de todas las operaciones BST anteriores utilizando el mismo árbol utilizado en la ilustración como ejemplo.
preguntas y respuestas de la entrevista css3 pdf|_+_|
Producción:
Cruce del árbol de búsqueda binaria (BST) en Java
Un árbol es una estructura jerárquica, por lo que no podemos atravesarlo linealmente como otras estructuras de datos como matrices. Cualquier tipo de árbol necesita ser atravesado de una manera especial para que todos sus subárboles y nodos sean visitados al menos una vez.
Dependiendo del orden en que el nodo raíz, el subárbol izquierdo y el subárbol derecho se atraviesan en un árbol, existen ciertos recorridos como se muestra a continuación:
- Traversal en orden
- Recorrido de pedidos anticipados
- PostOrder Traversal
Todos los recorridos anteriores utilizan la técnica de profundidad primero, es decir, el árbol se recorre en profundidad.
Los árboles también utilizan la técnica de amplitud primero para el recorrido. El enfoque que utiliza esta técnica se llama 'Orden de nivel' el recorrido.
En esta sección, demostraremos cada uno de los recorridos utilizando las siguientes BST como ejemplo.
Con el BST como se muestra en el diagrama anterior, el recorrido del orden de nivel para el árbol anterior es:
Desplazamiento del orden de nivel: 10 6 12 4 8
Traversal en orden
El enfoque transversal en orden atravesó la BST en el orden, Subárbol izquierdo => RootNode => Subárbol derecho . El recorrido en orden proporciona una secuencia decreciente de nodos de una BST.
El algoritmo InOrder (bstTree) para InOrder Traversal se muestra a continuación.
- Atraviesa el subárbol izquierdo usando InOrder (left_subtree)
- Visite el nodo raíz.
- Atraviesa el subárbol derecho usando InOrder (right_subtree)
El recorrido en orden del árbol anterior es:
4 6 8 10 12
Como se ve, la secuencia de los nodos como resultado del recorrido en orden está en orden decreciente.
Recorrido de pedidos anticipados
En el recorrido de preorden, primero se visita la raíz seguida por el subárbol izquierdo y el subárbol derecho. El recorrido de preorden crea una copia del árbol. También se puede utilizar en árboles de expresión para obtener una expresión de prefijo.
El algoritmo para el recorrido de PreOrder (bst_tree) se proporciona a continuación:
- Visita el nodo raíz
- Atraviesa el subárbol izquierdo con PreOrder (left_subtree).
- Atraviesa el subárbol derecho con PreOrder (right_subtree).
El recorrido de preorden para el BST indicado anteriormente es:
10 6 4 8 12
PostOrder Traversal
El recorrido postOrder atraviesa la BST en el orden: Subárbol izquierdo-> Subárbol derecho-> Nodo raíz . El recorrido de PostOrder se utiliza para eliminar el árbol u obtener la expresión de sufijo en el caso de árboles de expresión.
El algoritmo para el recorrido de postOrder (bst_tree) es el siguiente:
- Atraviesa el subárbol izquierdo con postOrder (left_subtree).
- Atraviesa el subárbol derecho con postOrder (right_subtree).
- Visita el nodo raíz
El recorrido de postOrder para el ejemplo anterior BST es:
4 8 6 12 10
A continuación, implementaremos estos recorridos utilizando la técnica de profundidad primero en una implementación de Java.
|_+_|Producción:
Preguntas frecuentes
P # 1) ¿Por qué necesitamos un árbol de búsqueda binario?
Responder : La forma en que buscamos elementos en la estructura de datos lineal como matrices usando la técnica de búsqueda binaria, siendo el árbol una estructura jerárquica, necesitamos una estructura que se pueda usar para ubicar elementos en un árbol.
Aquí es donde viene el árbol de búsqueda binaria que nos ayuda en la búsqueda eficiente de elementos en la imagen.
P # 2) ¿Cuáles son las propiedades de un árbol de búsqueda binaria?
Responder : Un árbol de búsqueda binaria que pertenece a la categoría de árbol binario tiene las siguientes propiedades:
- Los datos almacenados en un árbol de búsqueda binaria son únicos. No permite valores duplicados.
- Los nodos del subárbol izquierdo son menores que el nodo raíz.
- Los nodos del subárbol derecho son mayores que el nodo raíz.
P # 3) ¿Cuáles son las aplicaciones de un árbol de búsqueda binario?
Responder : Podemos usar árboles de búsqueda binaria para resolver algunas funciones continuas en matemáticas. La búsqueda de datos en estructuras jerárquicas se vuelve más eficiente con los árboles de búsqueda binaria. Con cada paso, reducimos la búsqueda a la mitad del subárbol.
P # 4) ¿Cuál es la diferencia entre un árbol binario y un árbol de búsqueda binario?
Responder: Un árbol binario es una estructura de árbol jerárquica en la que cada nodo conocido como padre puede tener como máximo dos hijos. Un árbol de búsqueda binario cumple con todas las propiedades del árbol binario y también tiene sus propiedades únicas.
En un árbol de búsqueda binaria, los subárboles de la izquierda contienen nodos que son menores o iguales que el nodo raíz y el subárbol derecho tiene nodos que son mayores que el nodo raíz.
P # 5) ¿El árbol de búsqueda binaria es único?
Responder : Un árbol de búsqueda binario pertenece a una categoría de árbol binario. Es único en el sentido de que no permite valores duplicados y además todos sus elementos están ordenados según un orden específico.
Conclusión
Los árboles de búsqueda binaria son parte de la categoría de árbol binario y se utilizan principalmente para buscar datos jerárquicos. También se utiliza para resolver algunos problemas matemáticos.
En este tutorial, hemos visto la implementación de un árbol de búsqueda binario. También hemos visto varias operaciones realizadas en BST con su ilustración y también exploramos los recorridos de BST.
=> Tenga cuidado con la serie de capacitación simple de Java aquí.
Lectura recomendada
- Árbol de búsqueda binaria C ++: implementación y operaciones de BST con ejemplos
- Algoritmo de búsqueda binaria en Java: implementación y ejemplos
- Estructura de datos de árbol binario en C ++
- Árboles en C ++: terminología básica, técnicas transversales y tipos de árboles de C ++
- TreeMap en Java - Tutorial con ejemplos de Java TreeMap
- TreeSet en Java: Tutorial con ejemplos de programación
- Tutorial de JAVA para principiantes: más de 100 tutoriales prácticos en vídeo de Java
- Lista vinculada en Java: implementación de lista vinculada y ejemplos de Java