in

Estructura de datos: árbol de búsqueda binaria

binary search tree

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:

Árbol de búsqueda binaria

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:

  • Buscar – Busca un elemento en un árbol.

  • Insertar – Inserta un elemento en un árbol.

  • Preordenar Traversal – Atraviesa un árbol en forma de reserva.

  • Recorrido en orden – Atraviesa un árbol de manera ordenada.

  • Recorrido posterior al pedido – 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;
            }
         }
      }            
   }
}        

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Compilador Java en línea | Editor de Java

apple touch icon@2

diccionario – Estructura similar a un mapa en C: use int y struct para determinar un valor