Estructura de datos: árbol de búsqueda binaria

Un árbol de búsqueda binaria (BST) es un árbol en el que todos los nodos siguen las propiedades mencionadas a continuación:

  • El valor de la clave del subárbol izquierdo es menor que el valor de la clave de su nodo principal (raíz).

  • El valor de la clave del subárbol derecho es mayor o igual que el valor de la clave de su nodo principal (raíz).

Por tanto, BST divide todos sus subárboles en dos segmentos; el subárbol izquierdo y el subárbol derecho y se puede definir como -

left_subtree (keys) < node (key) ≤ right_subtree (keys)

Representación

BST es una colección de nodos organizados de manera que mantienen las propiedades de BST. Cada nodo tiene una clave y un valor asociado. Durante la búsqueda, la clave deseada se compara con las claves en BST y, si se encuentra, se recupera el valor asociado.

A continuación se muestra una representación pictórica de BST:

Observamos que la clave del nodo raíz (27) tiene todas las claves de menor valor en el subárbol izquierdo y las claves de mayor valor en el subárbol derecho.

Operaciones básicas

Las siguientes son las operaciones básicas de un árbol:

  • Search - Busca un elemento en un árbol.

  • Insert - Inserta un elemento en un árbol.

  • Pre-order Traversal - Atraviesa un árbol en forma de reserva.

  • In-order Traversal - Atraviesa un árbol de manera ordenada.

  • Post-order Traversal - Atraviesa un árbol de manera posterior a la orden.

Nodo

Defina un nodo que tenga algunos datos, referencias a sus nodos secundarios izquierdo y derecho.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

Operación de búsqueda

Siempre que se deba buscar un elemento, comience a buscar desde el nodo raíz. Luego, si los datos son menores que el valor clave, busque el elemento en el subárbol izquierdo. De lo contrario, busque el elemento en el subárbol derecho. Siga el mismo algoritmo para cada nodo.

Algoritmo

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
	
   while(current->data != data){
	
      if(current != NULL) {
         printf("%d ",current->data);
			
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
			
         //not found
         if(current == NULL){
            return NULL;
         }
      }			
   }
   
   return current;
}

Insertar operación

Siempre que se inserte un elemento, primero ubique su ubicación adecuada. Comience a buscar desde el nodo raíz, luego, si los datos son menores que el valor clave, busque la ubicación vacía en el subárbol izquierdo e inserte los datos. De lo contrario, busque la ubicación vacía en el subárbol derecho e inserte los datos.

Algoritmo

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
			
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
				
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}