Árbol de búsqueda binaria en orden sucesor

El sucesor en orden de un árbol binario es el nodo que viene a continuación en el recorrido en orden del árbol binario. Entonces, es NULL para el último nodo dentro del árbol. Dado que el recorrido en orden del árbol de búsqueda binaria es un array ordenada. El nodo con la clave más pequeña mayor que el nodo dado se define como su sucesor en orden. En una BST, hay dos posibilidades para el sucesor del orden, el nodo con el menor valor en el subárbol derecho o antepasado del nodo. De lo contrario, el sucesor en orden del nodo no existe.

Sucesor de orden en algoritmo BST

Sucesor de orden en la ilustración BST

El sucesor en orden de 3 es 4 porque 3 tiene un nodo derecho y 4 es el nodo más pequeño que es mayor que 3 en el subárbol derecho.

El sucesor en orden de 4 es 5 porque 4 no tiene un nodo correcto, y tenemos que mirar sus ancestros y entre ellos, 5 es el nodo más pequeño que es mayor que 4.

Sucesor de orden en la implementación de BST

#include <iostream>
using namespace std;

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

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

Node* getNextleft(Node* root) {
  while (root->left) {
    root = root->left;
  }

  return root;
}

void inorderSuccessor(Node* root, Node*& succ, int key) {
  if (root == NULL) {
    succ = NULL;
    return;
  }

  if (root->data == key) {
    if (root->right) {
      succ = getNextleft(root->right);
    }
  }

  else if (key < root->data) {
    succ = root;
    inorderSuccessor(root->left, succ, key);
  } else {
    inorderSuccessor(root->right, succ, key);
  }
}

int main() {
  int keys[] = {1, 5, 8, 2, 6, 3, 7, 4};
  Node* root = NULL;
  for (int key : keys) {
    root = insert(root, key);
  }
  for (int key : keys) {
    Node* prec = NULL;
    inorderSuccessor(root, prec, key);
    if (prec) {
      cout << "Inorder successor of node " << key << " is " << prec->data;
    } else {
      cout << "No inorder Successor of node " << key;
    }

    cout << '\n';
  }

  return 0;
}

Complejidad del sucesor de orden en el algoritmo BST

Complejidad del tiempo

• Caso promedio

En el caso promedio, la complejidad temporal de encontrar un sucesor de orden en una BST es del orden de la altura del árbol de búsqueda binaria. 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 eliminación 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 de tiempo en el peor de los casos de las operaciones de inserción y búsqueda es O(n).

Complejidad espacial

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