Verificación del árbol binario de búsqueda

  2. Tutorial
  3. Estructura de datos
  4. Verificación del árbol binario de …
Harshit Jindal 12 octubre 2023
Data Structure Binary Tree Binary Search Tree
  1. El algoritmo para comprobar si el árbol binario es un árbol de búsqueda binario
  2. Implementación del algoritmo para verificar que el árbol binario es un árbol de búsqueda binario
  3. Análisis de complejidad
Verificación del árbol binario de búsqueda

Un árbol binario es una estructura de datos no lineal. Se llama árbol binario porque cada nodo tiene un máximo de dos hijos. Estos niños se llaman niños izquierdos y niños derechos. Para que un árbol binario se convierta en BST, debe satisfacer 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 algoritmo para comprobar si el árbol binario es un árbol de búsqueda binario

Algoritmo 1

En este enfoque, verificamos si el subárbol izquierdo contiene algún elemento mayor que el valor de la raíz y si el subárbol derecho contiene un elemento más pequeño que el valor de la raíz al considerar cada nodo como la raíz de su subárbol. Para encontrar el elemento max y min, tenemos que usar dos funciones separadas, getMin() y getMax().

getMin()

  • Inicializar temp como root.
  • Mientras que temp tiene una left, haz lo siguiente:
    • Configure temp como temp->left, es decir, muévase hacia la izquierda para encontrar el elemento más pequeño.
  • Devuelve temp->val como el valor mínimo dentro de ese subárbol.

getMax()

  • Inicializar temp como root.
  • Mientras que temp tiene un derecho, haz lo siguiente:
    • Configure temp como temp->right, es decir, muévase hacia la derecha para encontrar el elemento más grande.
  • Devuelve temp->val como el valor máximo dentro de ese subárbol.

isBST(root)

  • Si la root es NULL, devuelve true.
  • Encuentra el elemento máximo maxm en el subárbol izquierdo llamando a getMax(root->left);
  • Encuentra el elemento mínimo minm en el subárbol derecho llamando a getMin(root->right);
  • Si el elemento raíz es menor que maxm o mayor que minm, devuelve false.
  • Comprueba todos los nodos de forma recursiva llamando a isBST(root->left) e isBST(root->right). Si ambas llamadas recursivas devuelven verdadero, entonces el árbol es BST, devuelve verdadero; de lo contrario, devuelve falso.

El algoritmo anterior nos dice si un árbol es BST o no, pero es extremadamente lento. La función getMin() y getMax() tiene una complejidad de tiempo en el peor de los casos de O(n) y se llaman para n nodos que hacen que la complejidad de tiempo total O(n2).

Algoritmo 2:

Este algoritmo mejora el algoritmo anterior al no realizar cálculos repetidos. El enfoque anterior llamado getMin() y getMax() para cada nodo. Este enfoque mejora el enfoque anterior al realizar un seguimiento de los valores mínimos y máximos permitidos a medida que atravesamos los nodos.

isBST(root)

  • Inicializa dos variables min como INT_MIN y max como INT_MAX.
  • Llamar isBST(root,min,max).

isBST(root, min, max)

  • Si la root es NULL, devuelve true.
  • Si min> root->data entonces se viola la propiedad BST, devuelve falso.
  • Si max <root->data entonces se viola la propiedad BST, devuelve falso.
  • Verifica recursivamente el subárbol izquierdo llamando a isBST(root->left, min, root->data-1) (pasando min y root->data - 1 como argumentos cambia el valor válido rango para BST en el subárbol izquierdo) y el subárbol derecho llamando a isBST(root->right, root->data + 1, max) (pasando root->data + 1 y max como argumentos cambia el valor válido rango para BST en el subárbol derecho).
  • Si ambas llamadas recursivas devuelven true, entonces el árbol es BST, devuelve true.

La complejidad temporal de este algoritmo es O(n), lo que supone una mejora significativa con respecto al método anterior.

Algoritmo 3:

Este algoritmo evita el uso de INT_MIN e INT_MAX en el algoritmo anterior reemplazándolos con dos punteros, l y r.

isBST(root)

  • Inicializa dos nodos l y r como NULL.
  • Llamar a isBST(root, l, r). (Llamada de función sobrecargada)

isBST(root, l, r)

  • Si la root es NULL, devuelve true.
  • Si l no es NULL y l->data >= root->data entonces se viola la propiedad BST, devuelve falso.
  • Si r no es NULL y r->data <= root->data, entonces se viola la propiedad BST, devuelve falso.
  • Compruebe recursivamente el subárbol izquierdo llamando a isBST(root->left, left, root) (pasando la raíz como tercer argumento cambia el límite de valor mínimo para el subárbol) y el subárbol derecho llamando a isBST(root->right, root, right) (pasar la raíz como segundo argumento cambia el límite de valor máximo para el subárbol).
  • Si ambas llamadas recursivas devuelven true, entonces el árbol es BST, devuelve true.

Algoritmo 4:

El recorrido en orden del árbol binario de búsqueda devuelve elementos ordenados. Podemos usar esta propiedad para verificar si un árbol binario es BST. Si todos los elementos en el recorrido en orden no están en orden ascendente, entonces el árbol dado no es un árbol de búsqueda binario.

isBST(root)

  • Inicializa la variable prev como INT_MIN. prev se utiliza para comprobar si el nodo actual es mayor que prev y, por tanto, sigue el orden ordenado.
  • Llamar a isBST(root, prev). (Llamada a función sobrecargada).

isBST(root, prev)

  • Si la root es NULL, devuelve true.
  • Verifica recursivamente el subárbol izquierdo por isBST(root->left, prev). Si devuelve false, devuelve false.
  • Si root->data <= prev. se viola el orden ascendente, devuelva falso.
  • Actualiza prev->data como root->data.
  • Comprobar recursivamente el subárbol derecho mediante isBST(root->right, prev). Si devuelve false, devuelve false.
  • De lo contrario, devuelve true.

Implementación del algoritmo para verificar que el árbol binario es un árbol de búsqueda binario

Algoritmo 1

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
int getMin(Node* root) {
  while (root->left) {
    root = root->left;
  }

  return root->data;
}
int getMax(Node* root) {
  while (root->right) {
    root = root->right;
  }

  return root->data;
}
bool isBST(Node* root) {
  if (root == NULL) return true;

  if (root->left != NULL && getMax(root->left) > root->data) return false;

  if (root->right != NULL && getMin(root->right) < root->data) return false;

  if (!isBST(root->left) || !isBST(root->right)) return false;

  return true;
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

Algoritmo 2

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, int min, int max) {
  if (root == NULL) return 1;
  if (root->data < min || root->data > max) return 0;

  return isBST(root->left, min, root->data - 1) &&
         isBST(root->right, root->data + 1, max);
}

bool isBST(Node* root) { return isBST(root, INT_MIN, INT_MAX); }
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

Algoritmo 3

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, Node* l, Node* r) {
  if (root == NULL) return true;

  if (l != NULL and root->data <= l->data) return false;
  if (r != NULL and root->data >= r->data) return false;

  return isBST(root->left, l, root) && isBST(root->right, root, r);
}
bool isBST(Node* root) {
  Node* l = NULL;
  Node* r = NULL;
  return isBST(root, l, r);
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

Algoritmo 4

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, int& prev) {
  if (!root) return true;

  if (!isBST(root->left, prev)) return false;

  if (root->data <= prev) return false;
  prev = root->data;

  return isBST(root->right, prev);
}

bool isBST(Node* root) {
  int prev = INT_MIN;
  return isBST(root, prev);
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

Análisis de complejidad

Complejidad del tiempo

  • Caso promedio

Para comprobar si el árbol binario dado es BST o no, tenemos que atravesar todos los nodos n porque un solo nodo que desafía las propiedades conducirá a que el árbol no sea BST. Por tanto, la complejidad del tiempo es del orden de [Big Theta]: O(n).

  • Mejor caso

La complejidad del tiempo en el mejor de los casos es del orden de O(n). Es lo mismo que la complejidad del tiempo promedio de los casos.

  • Peor caso

La complejidad de tiempo en el peor de los casos es del orden de O(n). Es lo mismo que la complejidad del tiempo en el mejor de los casos.

Complejidad espacial

La complejidad espacial del algoritmo es O(n) debido al espacio extra requerido por las llamadas recursivas.

Autor: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Artículo relacionado - Data Structure

Artículo relacionado - Binary Tree

Artículo relacionado - Binary Search Tree