in

Estructura de datos y algoritmos: árbol

binary tree

El árbol representa los nodos conectados por bordes. Discutiremos el árbol binario o el árbol de búsqueda binario específicamente.

El árbol binario es una estructura de datos especial que se utiliza con fines de almacenamiento de datos. Un árbol binario tiene la condición especial de que cada nodo puede tener un máximo de dos hijos. Un árbol binario tiene los beneficios tanto de una matriz ordenada como de una lista vinculada, ya que la búsqueda es tan rápida como en una matriz ordenada y la operación de inserción o eliminación es tan rápida como en una lista vinculada.

Árbol binario

Términos importantes

Los siguientes son los términos importantes con respecto al árbol.

  • Sendero – Ruta se refiere a la secuencia de nodos a lo largo de los bordes de un árbol.

  • Raíz – El nodo en la parte superior del árbol se llama raíz. Solo hay una raíz por árbol y una ruta desde el nodo raíz a cualquier nodo.

  • Padre – Cualquier nodo excepto el nodo raíz tiene un borde hacia arriba hasta un nodo llamado padre.

  • Niño – El nodo debajo de un nodo dado conectado por su borde hacia abajo se llama su nodo hijo.

  • Hoja – El nodo que no tiene ningún nodo hijo se llama nodo hoja.

  • Subárbol – Subárbol representa los descendientes de un nodo.

  • Visitando – Visitar se refiere a verificar el valor de un nodo cuando el control está en el nodo.

  • Atravesar – Atravesar significa atravesar nodos en un orden específico.

  • Niveles – El nivel de un nodo representa la generación de un nodo. Si el nodo raíz está en el nivel 0, entonces su siguiente nodo hijo está en el nivel 1, su nieto está en el nivel 2, y así sucesivamente.

  • teclas – La clave representa un valor de un nodo en función del cual se realizará una operación de búsqueda para un nodo.

Representación del árbol de búsqueda binaria

El árbol de búsqueda binaria exhibe un comportamiento especial. El hijo izquierdo de un nodo debe tener un valor menor que el valor de su padre y el hijo derecho del nodo debe tener un valor mayor que su valor padre.

Árbol de búsqueda binaria

Vamos a implementar un árbol usando un objeto de nodo y conectándolos a través de referencias.

Nodo de árbol

El código para escribir un nodo de árbol sería similar al que se muestra a continuación. Tiene una parte de datos y referencias a sus nodos secundarios izquierdo y derecho.

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

En un árbol, todos los nodos comparten una construcción común.

Operaciones básicas de BST

Las operaciones básicas que se pueden realizar en una estructura de datos de árbol de búsqueda binaria son las siguientes:

  • Insertar – Inserta un elemento en un árbol / crea un árbol.

  • Buscar – Busca un elemento en un árbol.

  • Recorrido de pedidos anticipados – Atraviesa un árbol en forma de reserva.

  • Inorden Traversal – Atraviesa un árbol de manera ordenada.

  • Traslado posterior al pedido – Atraviesa un árbol de manera posterior a la orden.

Aprenderemos a crear (insertar) una estructura de árbol y buscar un elemento de datos en un árbol en este capítulo. Aprenderemos sobre los métodos para atravesar árboles en el próximo capítulo.

Insertar operación

La primera inserción crea el árbol. Luego, 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

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If      

Implementación

La implementación de la función de inserción debería verse así:

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, create root node
   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;
            }
         }
      }            
   }
}

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

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if      

La implementación de este algoritmo debería verse así.

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;
   }  
}

Para conocer la implementación de la estructura de datos de árbol de búsqueda binaria, haga clic aquí.

Deja una respuesta

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

series vs parallel circuits

Diferencia entre circuitos en serie y en paralelo

apple touch icon@2

transparencia – ¿Cómo puedo hacer un borde transparente con CSS?