Primero, entenderemos el árbol binario y árbol de búsqueda binaria por separado, y luego veremos las diferencias entre un árbol binario y un árbol de búsqueda binario.

¿Qué es un árbol binario?

A Árbol binario es unPuntero al niño izquierdo:Almacena la referencia del nodo secundario izquierdo.Puntero al niño correcto:Almacena la referencia del nodo secundario derecho.Elemento de datos:El elemento de datos es el valor de los datos almacenados por el nodo.

El árbol binario se puede representar como:

npm borrar caché

En la figura anterior, podemos observar que cada nodo contiene como máximo 2 hijos. Si algún nodo no contiene un hijo izquierdo o derecho, entonces el valor del puntero con respecto a ese hijo sería NULL.

Las terminologías básicas utilizadas en un árbol binario son:

Nodo raíz:El nodo raíz es el primero o el nodo superior en un árbol binario.Nodo padre:Cuando un nodo está conectado a otro nodo a través de bordes, ese nodo se conoce como nodo padre. En un árbol binario, el nodo padre puede tener un máximo de 2 hijos.Nodo hijo:Si un nodo tiene su predecesor, entonces ese nodo se conoce como nodo hijo .Nodo hoja:El nodo que no contiene ningún hijo conocido como nodo de hoja .Nodo interno:El nodo que tiene al menos 2 hijos conocido como nodo interno .Profundidad de un nodo:La distancia desde el nodo raíz al nodo dado se conoce como profundidad de un nodo . Proporcionamos etiquetas a todos los nodos, como el nodo raíz está etiquetado con 0 porque no tiene profundidad, los hijos de los nodos raíz están etiquetados con 1, los hijos del hijo raíz están etiquetados con 2.Altura:La distancia más larga desde el nodo raíz al nodo hoja es la altura del nodo .

En un árbol binario, hay un árbol conocido como árbol binario perfecto . Es un Árbol en el que todos los nodos internos deben contener dos nodos y todos los nodos hoja deben estar a la misma profundidad. En el caso de un árbol binario perfecto, el número total de nodos que existen en un árbol binario se puede calcular mediante la siguiente ecuación:

norte = 2^m+1-1

donde n es el número de nodos, m es la profundidad de un nodo.

¿Qué es un árbol de búsqueda binaria?

A Árbol de búsqueda binaria es un árbol que sigue algún orden para organizar los elementos, mientras que el árbol binario no sigue ningún orden. En un árbol de búsqueda binaria, el valor del nodo izquierdo debe ser menor que el nodo principal y el valor del nodo derecho debe ser mayor que el nodo principal.

Entendamos el concepto de árbol de búsqueda binario a través de ejemplos.

En la figura anterior, podemos observar que el valor del nodo raíz es 15, que es mayor que el valor de todos los nodos en el subárbol izquierdo. El valor del nodo raíz es menor que los valores de todos los nodos en un subárbol derecho. Ahora, pasamos al hijo izquierdo del nodo raíz. 10 es mayor que 8 y menor que 12; también satisface la propiedad del árbol de búsqueda binaria. Ahora, pasamos al hijo derecho del nodo raíz; el valor 20 es mayor que 17 y menor que 25; también satisface la propiedad del árbol de búsqueda binario. Por tanto, podemos decir que el árbol que se muestra arriba es el árbol de búsqueda binaria.

Ahora, si cambiamos el valor de 12 a 16 en el árbol binario anterior, tenemos que averiguar si sigue siendo un árbol de búsqueda binario o no.

etiquetas html

El valor del nodo raíz es 15, que es mayor que 10 pero menor que 16, por lo que no satisface la propiedad del árbol de búsqueda binaria. Por tanto, no es un árbol de búsqueda binario.

Operaciones en el árbol de búsqueda binaria

Podemos realizar operaciones de inserción, eliminación y búsqueda en el árbol de búsqueda binaria. Entendamos cómo se realiza una búsqueda en una búsqueda binaria. A continuación se muestra el árbol binario sobre el cual tenemos que realizar la operación de búsqueda:

Supongamos que tenemos que buscar 10 en el árbol binario anterior. Para realizar la búsqueda binaria, consideraremos todos los números enteros en una matriz ordenada. Primero, creamos una lista completa en un espacio de búsqueda y todos los números existirán en el espacio de búsqueda. El espacio de búsqueda está marcado por dos punteros, es decir, inicio y fin. La matriz del árbol binario anterior se puede representar como

Primero, calcularemos el elemento del medio y compararemos el elemento del medio con el elemento que se va a buscar. El elemento medio se calcula usando n/2. El valor de n es 7; por lo tanto, el elemento del medio es 15. El elemento del medio no es igual al elemento buscado, es decir, 10.

Nota: Si el elemento que se busca es menor que el elemento medio, la búsqueda se realizará en la mitad izquierda; de lo contrario, la búsqueda se realizará en la mitad derecha. En el caso de igualdad, se encuentra el elemento.

Como el elemento a buscar es menor que el elemento medio, la búsqueda se realizará en la matriz izquierda. Ahora la búsqueda se reduce a la mitad, como se muestra a continuación:

El elemento medio en la matriz izquierda es 10, que es igual al elemento buscado.

Complejidad del tiempo

En una búsqueda binaria, hay n elementos. Si el elemento del medio no es igual al elemento buscado, entonces el espacio de búsqueda se reduce a n/2, y seguiremos reduciendo el espacio de búsqueda en n/2 hasta que encontremos el elemento. En toda la reducción, si pasamos de n a n/2 a n/4 y así sucesivamente, se necesitará log₂n pasos.

Diferencias entre árbol binario y árbol de búsqueda binaria