Árbol de búsqueda binaria

1. Operación de búsqueda en el Árbol binario de búsqueda
2. Algoritmo de búsqueda BST
3. Ilustración de búsqueda BST
4. Inserción en BST
5. Algoritmo de inserción BST
6. Ilustración de inserto BST
7. Implementación de búsqueda e inserción de BST
8. Complejidad del algoritmo de inserción y búsqueda de BST

El Árbol binario de búsqueda (BST) es una estructura de datos de árbol binario ordenada basada en nodos. Los nodos tienen un valor y dos nodos secundarios (un árbol binario tiene un máximo de dos nodos secundarios) adjuntos a la izquierda y a la derecha. A excepción del nodo raíz, solo su padre puede hacer referencia a todos los nodos. Un BST tiene las siguientes propiedades:

• Todos los nodos del subárbol izquierdo son más pequeños que el nodo raíz.
• Todos los nodos del subárbol derecho son más grandes que el nodo raíz.
• Los subárboles izquierdo y derecho también deben ser árboles de búsqueda binarios.

El árbol de la izquierda satisface todas las propiedades de BST. Por otro lado, el árbol del lado derecho parece ser un BST ya que todos los nodos del subárbol izquierdo son más pequeños y los del subárbol derecho son más grandes. Pero el nodo 1 en el subárbol izquierdo no satisface las propiedades de BST ya que es más pequeño que el nodo 4 pero no mayor que el nodo raíz 3. Por lo tanto, no es un BST.

Dado que se trata de una estructura de datos ordenada, los elementos introducidos siempre se organizan de forma ordenada. Podemos utilizar el recorrido en orden para recuperar los datos almacenados en BST en orden ordenado. Recibe su nombre porque, al igual que la búsqueda binaria, se puede utilizar para buscar los datos en O(logn).

Operación de búsqueda en el Árbol binario de búsqueda

Sabemos que en una BST, todos los elementos del lado derecho de la raíz son más grandes y, por lo tanto, si el elemento de destino que estamos buscando es más pequeño que la raíz, se puede descuidar todo el subárbol derecho. De manera similar, si el elemento es más grande que la raíz, el subárbol izquierdo puede despreciarse. Nos movemos de manera similar hasta que agotamos el árbol o encontramos el elemento de destino como raíz del subárbol. Si el BST está balanceado (un árbol se llama árbol balanceado si para todos los nodos la diferencia entre la altura del subárbol izquierdo y derecho es menor que igual a 1), entonces la búsqueda dentro de BST se realiza de manera similar a la búsqueda binaria ya que ambos los subárboles tienen alrededor de la mitad de los elementos que se descuidan en cada iteración, pero en el caso de un árbol desequilibrado, todos los nodos pueden estar presentes en el mismo lado y la búsqueda puede funcionar de manera similar a la búsqueda lineal.

Algoritmo de búsqueda BST

Sea raíz el nodo raíz de BST y X el elemento de destino que se busca.

Ilustración de búsqueda BST

Supongamos que tenemos el BST anterior y queremos encontrar el elemento X = 25.

Inserción en BST

El algoritmo para insertar un elemento dentro de BST es bastante similar a buscar un elemento dentro de BST porque antes de insertar un elemento, tenemos que encontrar su posición correcta. La única diferencia en la función de inserción y búsqueda es que en el caso de la búsqueda, devolvemos el nodo que contiene el valor objetivo, mientras que creamos un nuevo nodo en la posición apropiada del nodo en el caso de una inserción.

Algoritmo de inserción BST

Sea raíz el nodo raíz de BST y X el elemento que queremos insertar.

Ilustración de inserto BST

Así es como insertamos elementos dentro de una BST.

Implementación de búsqueda e inserción de BST

#include <iostream>
using namespace std;

class Node {
 public:
  int key;
  Node *left, *right;
};

Node *newNode(int item) {
  Node *temp = (Node *)malloc(sizeof(Node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

void inorder(Node *root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}

Node *insert(Node *root, int key) {
  if (root == NULL) return newNode(key);
  if (key < root->key)
    root->left = insert(root->left, key);
  else
    root->right = insert(root->right, key);

  return root;
}

Node *search(Node *root, int key) {
  if (root == NULL || root->key == key) return root;

  if (root->key < key) return search(root->right, key);

  return search(root->left, key);
}
int main() {
  Node *root = NULL;
  root = insert(root, 5);
  root = insert(root, 3);
  root = insert(root, 8);
  root = insert(root, 6);
  root = insert(root, 4);
  root = insert(root, 2);
  root = insert(root, 1);
  root = insert(root, 7);
  cout << search(root, 5)->key << endl;
}

Complejidad del algoritmo de inserción y búsqueda de BST

Complejidad del tiempo

• Caso promedio

En el caso promedio, la complejidad temporal de insertar un nodo o buscar un elemento en una BST es del orden de la altura del Árbol binario de búsqueda. En promedio, la altura de un BST es O(logn). Ocurre cuando la BST formada es una BST equilibrada. Por tanto, la complejidad del tiempo es del orden de [Big Theta]: O(logn).

• Mejor caso

El mejor de los casos ocurre cuando el árbol es una BST equilibrada. La complejidad de tiempo de inserción y búsqueda en el mejor de los casos es del orden de O(logn). Es lo mismo que la complejidad del tiempo promedio de los casos.

• Peor caso

En el peor de los casos, podríamos tener que atravesar desde la raíz hasta el nodo de la hoja más profundo, es decir, toda la altura h del árbol. Si el árbol está desequilibrado, es decir, está sesgado, la altura del árbol puede convertirse en n y, por lo tanto, la complejidad temporal en el peor de los casos tanto de la operación de inserción como de la operación de búsqueda es O(n).

Complejidad espacial

La complejidad espacial de la operación de inserción y búsqueda es O(n) debido al espacio requerido por las llamadas recursivas.