Implementación de un árbol de búsqueda binario

2024 Autor: Angel Austin | [email protected]. Última modificación: 2023-12-17 05:23

Árbol de búsqueda binario: una base de datos estructurada que contiene nodos, dos enlaces a otros nodos, derecho e izquierdo. Los nodos son un objeto de la clase que tiene datos, y NULL es el signo que marca el final del árbol.

A menudo se denomina BST, que tiene una propiedad especial: los nodos más grandes que la raíz se ubican a la derecha y los más pequeños a la izquierda.

Teoría general y terminología

En un árbol de búsqueda binaria, cada nodo, excepto la raíz, está conectado por un borde dirigido de un nodo a otro, que se denomina padre. Cada uno de ellos se puede conectar a un número arbitrario de nodos, llamados hijos. Los nodos sin "hijos" se llaman hojas (nodos externos). Los elementos que no son hojas se llaman internos. Los nodos con el mismo padre son hermanos. El nodo superior se llama raíz. En BST, asigne un elemento a cada nodo y asegúrese de que tengan una propiedad especial establecida para ellos.

Terminología del árbol:

1. La profundidad de un nodo es el número de aristas definidas desde la raíz hasta él.
2. La altura de un nodo es el número de aristas definidas desde él hasta la hoja más profunda.
3. La altura del árbol está determinada por la altura de la raíz.
4. El árbol de búsqueda binario es un diseño especial, proporciona la mejor proporción de altura y número de nodos.
5. Altura h con N nodos como máximo O (log N).

Puedes probar esto fácilmente contando los nodos en cada nivel, comenzando desde la raíz, asumiendo que contiene el mayor número de ellos: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Resolviendo esto para h da h=O (log n).

Beneficios de la madera:

1. Refleja las relaciones estructurales de los datos.
2. Se utiliza para representar jerarquías.
3. Asegure una instalación y búsqueda eficientes.
4. Los árboles son datos muy flexibles, lo que le permite mover subárboles con un esfuerzo mínimo.

Método de búsqueda

En general, para determinar si un valor está en el BST, inicie un árbol de búsqueda binario en su raíz y determine si cumple con los requisitos:

• estar en la raíz;
• estar en el subárbol izquierdo de la raíz;
• en el subárbol derecho de root.

Si no se satisface ningún registro base, se realiza una búsqueda recursiva en el subárbol correspondiente. En realidad, hay dos opciones básicas:

1. El árbol está vacío - devuelve false.
2. El valor está en el nodo raíz - devuelve verdadero.

Cabe señalar que un árbol de búsqueda binaria con un esquema desarrollado siempre comienza a buscar a lo largo del camino desde la raíz hasta la hoja. En el peor de los casos, llega hasta la hoja. Por tanto, el peor tiempo es proporcional a la longitud del camino más largo desde la raíz hasta la hoja, que es la altura del árbol. En general, aquí es cuando necesita saber cuánto tiempo lleva buscar en función de la cantidad de valores almacenados en el árbol.

En otras palabras, existe una relación entre el número de nodos en un BST y la altura de un árbol, dependiendo de su "forma". En el peor de los casos, los nodos tienen un solo hijo y un árbol de búsqueda binario equilibrado es esencialmente una lista enlazada. Por ejemplo:

50

/

10

15

30

/

20

Este árbol tiene 5 nodos y altura=5. Encontrar valores en el rango 16-19 y 21-29 requerirá la siguiente ruta desde la raíz hasta la hoja (el nodo que contiene el valor 20), es decir, llevará un tiempo proporcional al número de nodos. En el mejor de los casos, todos tienen 2 hijos y las hojas están ubicadas a la misma profundidad.

Este árbol de búsqueda binaria tiene 7 nodos y una altura=3. En general, un árbol como este (árbol completo) tendrá una altura de aproximadamente log 2 (N), donde N es el número de nodos en el árbol. El valor de log 2 (N) es el número de veces (2) que N se puede dividir antes de llegar a cero.

Resumiendo: el peor tiempo necesario para buscar en BST es O (altura del árbol). El peor caso de árbol "lineal" es O(N), donde N es el número de nodos en el árbol. En el mejor de los casos, un árbol "completo" es O(log N).

BST inserción binaria

Me pregunto dónde debería estarel nuevo nodo está ubicado en el BST, debe comprender la lógica, debe colocarse donde el usuario lo encuentre. Además, debe recordar las reglas:

1. No se permiten duplicados, intentar insertar un valor duplicado generará una excepción.
2. El método de inserción público utiliza un método auxiliar recursivo "ayudante" para realizar la inserción.
3. Un nodo que contiene un nuevo valor siempre se inserta como una hoja en BST.
4. El método de inserción pública devuelve void, pero el método auxiliar devuelve un BSTnode. Hace esto para manejar el caso en el que el nodo que se le pasó es nulo.

En general, el método auxiliar indica que si el árbol de búsqueda binaria original está vacío, el resultado es un árbol con un nodo. De lo contrario, el resultado será un puntero al mismo nodo que se pasó como argumento.

Eliminación en algoritmo binario

Como era de esperar, eliminar un elemento implica encontrar un nodo que contenga el valor que se eliminará. Hay varias cosas en este código:

1. BST utiliza un método auxiliar de eliminación sobrecargado. Si el elemento que está buscando no está en el árbol, el método de ayuda finalmente se llamará con n==nulo. Esto no se considera un error, el árbol simplemente no cambia en este caso. El método auxiliar de eliminación devuelve un valor: un puntero al árbol actualizado.
2. Cuando se elimina una hoja, la eliminación del árbol de búsqueda binario establece el puntero secundario correspondiente de su padre en nulo, o la raíz en nulo si el que se elimina esel nodo es una raíz y no tiene hijos.
3. Tenga en cuenta que la llamada de eliminación debe ser una de las siguientes: root=delete (raíz, clave), n.setLeft (delete (n.getLeft (), clave)), n.setRight (delete(n. getRight(), clave)). Por lo tanto, en los tres casos es correcto que el método de eliminación simplemente devuelva nulo.
4. Cuando la búsqueda del nodo que contiene el valor que se eliminará tiene éxito, hay tres opciones: el nodo que se eliminará es una hoja (no tiene hijos), el nodo que se eliminará tiene un hijo, tiene dos niños.
5. Cuando el nodo que se está eliminando tiene un hijo, simplemente puede reemplazarlo con un hijo, devolviendo un puntero al hijo.
6. Si el nodo a eliminar tiene cero o 1 hijo, entonces el método de eliminación "seguirá la ruta" desde la raíz hasta ese nodo. Entonces, el peor momento es proporcional a la altura del árbol, tanto para buscar como para insertar.

Si el nodo a eliminar tiene dos hijos, se siguen los siguientes pasos:

1. Encuentre el nodo a eliminar, siguiendo la ruta desde la raíz hasta él.
2. Encuentre el valor más pequeño de v en el subárbol derecho, continuando por el camino a la hoja.
3. Elimine recursivamente el valor de v, siga el mismo camino que en el paso 2.
4. Así, en el peor de los casos, el camino de la raíz a la hoja se realiza dos veces.

Orden de las poligonales

Recorrido es un proceso que visita todos los nodos de un árbol. Debido a que un árbol de búsqueda binario C es una estructura de datos no lineal, no hay un recorrido único. Por ejemplo, a veces varios algoritmos transversalesagrupados en los siguientes dos tipos:

• profundidad de cruce;
• primer paso.

Solo hay un tipo de cruce de ancho: pasar por alto el nivel. Este recorrido visita los nodos a nivel inferior e izquierdo, superior y derecho.

Hay tres tipos diferentes de cruces de profundidad:

1. Pasando el pedido anticipado: primero visite al padre y luego al hijo izquierdo y derecho.
2. Passing InOrder: visita al hijo izquierdo, luego al padre y al hijo derecho.
3. Pasado el pedido posterior: visitar el hijo izquierdo, luego el hijo derecho, luego el padre.

Ejemplo de cuatro recorridos de un árbol de búsqueda binaria:

1. Reserva - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
2. En orden - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
3. PostOrden - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
4. Orden de nivel - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

La figura muestra el orden en que se visitan los nodos. El número 1 es el primer nodo en un recorrido particular y el 7 es el último nodo.

Estos recorridos generales se pueden representar como un solo algoritmo, asumiendo que cada nodo se visita tres veces. El recorrido de Euler es un paseo por un árbol binario donde cada borde se trata como una pared que el usuario no puede cruzar. En este recorrido, cada nodo se visitará a la izquierda, abajo oa la derecha. El recorrido de Euler, que visita los nodos de la izquierda, hace que se pase por alto la preposición. Cuando se visitan los nodos a continuación, se recorren en orden. Y cuando se visiten los nodos de la derecha, obtengaderivación paso a paso.

Navegación y depuración

Para facilitar la navegación por el árbol, cree funciones que primero verifiquen si son el hijo izquierdo o derecho. Para cambiar la posición de un nodo, debe haber fácil acceso al puntero en el nodo principal. Implementar correctamente un árbol es muy difícil, por lo que es necesario conocer y aplicar procesos de depuración. Un árbol de búsqueda binaria con una implementación a menudo tiene punteros que en realidad no indican la dirección de viaje.

Para resolver todo esto, se usa una función que verifica si el árbol puede ser correcto y ayuda a encontrar muchos errores. Por ejemplo, comprueba si el nodo principal es un nodo secundario. Con assert(is_wellformed(root)) muchos errores pueden detectarse prematuramente. Usando un par de puntos de interrupción dados dentro de esta función, también puede determinar exactamente qué puntero está mal.

Función Konsolenausgabe

Esta función descarga todo el árbol en la consola y, por lo tanto, es muy útil. El orden en que se ejecuta el objetivo de salida del árbol es:

1. Para hacer esto, primero debe determinar qué información se generará a través del nodo.
2. Y también necesita saber qué tan ancho y alto es el árbol para tener en cuenta cuánto espacio dejar.
3. Las siguientes funciones calculan esta información para el árbol y cada subárbol. Dado que solo puede escribir en la consola línea por línea, también deberá imprimir el árbol línea por línea.
4. Ahora necesitamos otra forma de retirartodo el árbol, no solo línea por línea.
5. Con la ayuda de la función de volcado, puede leer el árbol y mejorar significativamente el algoritmo de salida, en lo que respecta a la velocidad.

Sin embargo, esta función será difícil de usar en árboles grandes.

Copiar constructor y destructor

Debido a que un árbol no es una estructura de datos trivial, es mejor implementar un constructor de copia, un destructor y un operador de asignación. El destructor es fácil de implementar recursivamente. Para árboles muy grandes, puede manejar el "desbordamiento del montón". En este caso, se formula iterativamente. La idea es eliminar la hoja que representa el valor más pequeño de todas las hojas, para que quede en el lado izquierdo del árbol. Cortar las primeras hojas crea otras nuevas, y el árbol se encoge hasta que finalmente deja de existir.

El constructor de copias también se puede implementar de forma recursiva, pero tenga cuidado si se lanza una excepción. De lo contrario, el árbol rápidamente se vuelve confuso y propenso a errores. Es por eso que se prefiere la versión iterativa. La idea es pasar por el árbol viejo y el árbol nuevo, como lo harías en el destructor, clonando todos los nodos que están en el árbol viejo pero no los nuevos.

Con este método, la implementación del árbol de búsqueda binaria está siempre en buen estado y el destructor puede eliminarla incluso en un estado incompleto. Si ocurre una excepción, todo lo que necesita hacer es indicarle al destructor que elimine el árbol semiacabado. operador de asignaciónse puede implementar fácilmente usando Copiar e intercambiar.

Creando un árbol de búsqueda binaria

Los árboles de búsqueda binarios óptimos son increíblemente eficientes si se gestionan correctamente. Algunas reglas para árboles de búsqueda binarios:

1. Un nodo principal tiene como máximo 2 nodos secundarios.
2. El nodo secundario izquierdo siempre es menor que el nodo principal.
3. Un nodo secundario válido siempre es mayor o igual que el nodo principal.

La matriz que se usará para construir el árbol de búsqueda binaria:

1. Una matriz entera base de siete valores en orden no ordenado.
2. El primer valor en la matriz es 10, por lo que el primer paso para construir el árbol es crear un nodo raíz de 10, como se muestra aquí.
3. Con un conjunto de nodos raíz, todos los demás valores serán hijos de este nodo. Con referencia a las reglas, el primer paso que se debe tomar para agregar 7 al árbol es compararlo con el nodo raíz.
4. Si el valor 7 es menor que 10, se convertirá en el nodo secundario izquierdo.
5. Si el valor 7 es mayor o igual a 10, se moverá hacia la derecha. Como se sabe que 7 es menor que 10, se designa como el nodo secundario izquierdo.
6. Realiza comparaciones recursivas para cada elemento.
7. Siguiendo el mismo patrón, realice la misma comparación con el valor 14 de la matriz.
8. Comparando el valor 14 con el nodo raíz 10, sabiendo que 14 es el hijo correcto.
9. Recorriendo la matriz,ven a 20.
10. Comience comparando la matriz con 10, el que sea mayor. Muévase a la derecha y compárelo con 14, tiene más de 14 años y no tiene hijos a la derecha.
11. Ahora hay un valor de 1. Siguiendo el mismo patrón que los otros valores, compare 1 con 10, moviéndose hacia la izquierda y comparando con 7 y finalmente con el 1 hijo izquierdo del 7º nodo.
12. Si el valor es 5, compárelo con 10. Como 5 es menor que 10, pase a la izquierda y compárelo con 7.
13. Sabiendo que 5 es menor que 7, continúa hacia abajo en el árbol y compara 5 con el valor 1.
14. Si 1 no tiene hijos y 5 es mayor que 1, entonces 5 es un hijo válido de 1 nodo.
15. Finalmente inserte el valor 8 en el árbol.
16. Cuando 8 es menor que 10, muévelo a la izquierda y compáralo con 7, 8 es mayor que 7, así que muévelo a la derecha y completa el árbol, haciendo que 8 sea un hijo apropiado de 7.

Obtener y evaluar la elegancia simple de los árboles de búsqueda binarios óptimos. Al igual que muchos temas de programación, el poder de los árboles de búsqueda binarios proviene de su capacidad para resolver los datos en pequeños componentes relacionados. A partir de ahora, puede trabajar con el conjunto de datos completo de forma organizada.

Problemas potenciales de búsqueda binaria

Los árboles de búsqueda binarios son geniales, pero hay algunas advertencias a tener en cuenta. Por lo general, solo son efectivos si están equilibrados. Un árbol equilibrado es un árbol en el quela diferencia entre las alturas de los subárboles de cualquier nodo del árbol es como máximo uno. Veamos un ejemplo que podría ayudar a aclarar las reglas. Imaginemos que la matriz comienza como ordenable.

Si intenta ejecutar un algoritmo de árbol de búsqueda binaria en este árbol, funcionará exactamente como si estuviera iterando a través de la matriz hasta encontrar el valor deseado. El poder de la búsqueda binaria radica en la capacidad de filtrar rápidamente los valores no deseados. Cuando un árbol no está equilibrado, no proporcionará los mismos beneficios que un árbol equilibrado.

Es muy importante examinar los datos con los que trabaja el usuario al crear un árbol de búsqueda binaria. Puede integrar rutinas como la aleatorización de matrices antes de implementar un árbol de búsqueda binaria de enteros para equilibrarlo.

Ejemplos de cálculo de búsqueda binaria

Necesitamos determinar qué tipo de árbol resultará si se inserta 25 en el siguiente árbol binario de búsqueda:

10

/

/

5 15

/ /

/ /

2 12 20

Al insertar x en un árbol T que aún no contiene x, la clave x siempre se coloca en una hoja nueva. En relación con esto, el nuevo árbol se verá así:

10

/

/

5 15

/ /

/ /

2 12 20

25

¿Qué tipo de árbol obtendría si insertara 7 en el siguiente árbol binario de búsqueda?

10

/

/

5 15

/ /

/ /

2 12 20

Respuesta:

10

/

/

/

5 15

/ / /

/ / /

2 7 12 20

Se puede utilizar un árbol de búsqueda binaria para almacenar cualquier objeto. La ventaja de usar un árbol de búsqueda binario en lugar de una lista enlazada es que si el árbol está razonablemente equilibrado y se parece más a un árbol "completo" que a uno "lineal", se pueden implementar operaciones de inserción, búsqueda y eliminación para que se ejecuten en O(log N) tiempo.