Árboles de búsqueda binaria: BST explicado con ejemplos

Programación

¿Qué es un árbol de búsqueda binaria?

Un árbol es una estructura de datos compuesta por nodos que tiene las siguientes características:

  1. Cada árbol tiene un nodo raíz en la parte superior (también conocido como nodo principal) que contiene algún valor (puede ser cualquier tipo de datos).
  2. El nodo raíz tiene cero o más nodos secundarios.
  3. Cada nodo secundario tiene cero o más nodos secundarios, y así sucesivamente. Esto crea un subárbol en el árbol. Cada nodo tiene su propio subárbol compuesto por sus hijos y sus hijos, etc. Esto significa que cada nodo por sí solo puede ser un árbol.

Un árbol de búsqueda binaria (BST) agrega estas dos características:

  1. Cada nodo tiene un máximo de hasta dos hijos.
  2. Para cada nodo, los valores de sus nodos descendientes izquierdos son menores que los del nodo actual, que a su vez es menor que los nodos descendientes derechos (si los hay).

El BST se basa en la idea del algoritmo de búsqueda binaria, que permite una rápida búsqueda, inserción y eliminación de nodos. La forma en que se configuran significa que, en promedio, cada comparación permite que las operaciones salten aproximadamente la mitad del árbol, de modo que cada búsqueda, inserción o eliminación lleva un tiempo proporcional al logaritmo del número de elementos almacenados en el árbol.   O(log n). Sin embargo, algunas veces puede suceder el peor de los casos, cuando el árbol no está equilibrado y la complejidad del tiempo es   O(n)  para las tres funciones. Es por eso que los árboles autoequilibrados (AVL, rojo-negro, etc.) son mucho más efectivos que el BST básico.

Ejemplo del peor de los casos:  esto puede suceder cuando sigue agregando nodos que siempre son    más grandes que el nodo anterior (su padre), lo mismo puede suceder cuando siempre agrega nodos con valores más bajos que sus padres.

Operaciones básicas en un BST

  • Crear: crea un árbol vacío.
  • Insertar: inserta un nodo en el árbol.
  • Buscar: busca un nodo en el árbol.
  • Eliminar: elimina un nodo del árbol.
  • Inorder: recorrido en orden del árbol.
  • Preorder: recorrido del árbol por preorden.
  • Postorder: recorrido posterior al pedido del árbol.

Crear

Inicialmente se crea un árbol vacío sin nodos. La variable / identificador que debe apuntar al nodo raíz se inicializa con un   NULL  valor.

Buscar

Siempre comienzas a buscar en el árbol en el nodo raíz y bajas desde allí. Compara los datos de cada nodo con el que está buscando. Si el nodo comparado no coincide, proceda al hijo derecho o al hijo izquierdo, lo que depende del resultado de la siguiente comparación: Si el nodo que está buscando es más bajo que el que lo estaba comparando, pasa al niño izquierdo, de lo contrario (si es más grande) va al niño derecho. ¿Por qué? Debido a que el BST está estructurado (según su definición), el hijo derecho siempre es más grande que el padre y el hijo izquierdo siempre es menor.

Búsqueda primero en amplitud (BFS)

La primera búsqueda de amplitud es un algoritmo que se utiliza para atravesar una BST. Comienza en el nodo raíz y se desplaza lateralmente (de lado a lado), buscando el nodo deseado. Este tipo de búsqueda se puede describir como O (n) dado que cada nodo se visita una vez y el tamaño del árbol se correlaciona directamente con la duración de la búsqueda.

Búsqueda en profundidad (DFS)

Con un enfoque de búsqueda en profundidad, comenzamos con el nodo raíz y recorremos una sola rama. Si el nodo deseado se encuentra a lo largo de esa rama, genial, pero si no, continúe hacia arriba y busque los nodos no visitados. Este tipo de búsqueda también tiene una notación O grande de O (n).

Insertar

Es muy similar a la función de búsqueda. De nuevo comienzas en la raíz del árbol y bajas de forma recursiva, buscando el lugar adecuado para insertar nuestro nuevo nodo, de la misma forma que se explica en la función de búsqueda. Si un nodo con el mismo valor ya está en el árbol, puede elegir insertar el duplicado o no. Algunos árboles permiten duplicados, otros no. Depende de la implementación determinada.

Supresión

Hay 3 casos que pueden ocurrir cuando intenta eliminar un nodo. Si tiene

  1. Sin subárbol (sin hijos): este es el más fácil. Simplemente puede eliminar el nodo, sin necesidad de realizar acciones adicionales.
  2. Un subárbol (un hijo): debe asegurarse de que después de eliminar el nodo, su hijo se conecte al padre del nodo eliminado.
  3. Dos subárboles (dos hijos): debe buscar y reemplazar el nodo que desea eliminar con su sucesor en orden (el nodo más a la izquierda en el subárbol derecho).

La complejidad del tiempo para crear un árbol es   O(1). La complejidad del tiempo para buscar, insertar o eliminar un nodo depende de la altura del árbol   h, por lo que el peor de los casos es   O(h)  en el caso de árboles sesgados.

Predecesor de un nodo

Los predecesores pueden describirse como el nodo que vendría justo antes del nodo en el que se encuentra actualmente. Para encontrar el predecesor del nodo actual, mire el nodo hoja más a la derecha / más grande en el subárbol izquierdo.

Sucesor de un nodo

Los sucesores pueden describirse como el nodo que vendría inmediatamente después del nodo actual. Para encontrar el sucesor del nodo actual, mire el nodo hoja más a la izquierda / más pequeño en el subárbol derecho.

Tipos especiales de BT

  • Montón
  • Árbol rojo-negro
  • Árbol B
  • Árbol de extensión
  • Árbol n-ario
  • Trie (árbol Radix)

Tiempo de ejecución

Estructura de datos: BST

  • Rendimiento en el peor de los casos:  O(n)
  • Rendimiento en el mejor de los casos:  O(1)
  • Rendimiento medio:  O(log n)
  • Complejidad de espacio en el peor de los casos:  O(1)

¿Dónde   n  está el número de nodos en la BST? El peor de los casos es O (n), ya que BST puede estar desequilibrado.

Implementación de BST

Aquí hay una definición para un nodo BST que tiene algunos datos, haciendo referencia 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 de la 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.

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

Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

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

Delete Operation

void deleteNode(struct node* root, int data){ if (root == NULL) root=tempnode; if (data key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { if (root->left == NULL) { struct node *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct node *temp = root->left; free(root); return temp; } struct node* temp = minValueNode(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); } return root; }

Binary search trees (BSTs) also give us quick access to predecessors and successors. Predecessors can be described as the node that would come right before the node you are currently at.

  • To find the predecessor of the current node, look at the rightmost/largest leaf node in the left subtree. Successors can be described as the node that would come right after the node you are currently at.
  • To find the successor of the current node, look at the leftmost/smallest leaf node in the right subtree.

Let's look at a couple of procedures operating on trees.

Since trees are recursively defined, it's very common to write routines that operate on trees that are themselves recursive.

So for instance, if we want to calculate the height of a tree, that is the height of a root node, We can go ahead and recursively do that, going through the tree. So we can say:

  • For instance, if we have a nil tree, then its height is a 0.
  • Otherwise, We're 1 plus the maximum of the left child tree and the right child tree.
  • So if we look at a leaf for example, that height would be 1 because the height of the left child is nil, is 0, and the height of the nil right child is also 0. So the max of that is 0, then 1 plus 0.

Height(tree) algorithm

if tree = nil: return 0 return 1 + Max(Height(tree.left),Height(tree.right))

Here is the code in C++

int maxDepth(struct node* node) { if (node==NULL) return 0; else { int rDepth = maxDepth(node->right); int lDepth = maxDepth(node->left); if (lDepth > rDepth) { return(lDepth+1); } else { return(rDepth+1); } } }

We could also look at calculating the size of a tree that is the number of nodes.

  • Again, if we have a nil tree, we have zero nodes.
  • Otherwise, we have the number of nodes in the left child plus 1 for ourselves plus the number of nodes in the right child. So 1 plus the size of the left tree plus the size of the right tree.

Size(tree) algorithm

if tree = nil return 0 return 1 + Size(tree.left) + Size(tree.right)

Here is the code in C++

int treeSize(struct node* node) { if (node==NULL) return 0; else return 1+(treeSize(node->left) + treeSize(node->right)); }

Traversal

There are 3 kinds of traversals that are done typically over a binary search tree. All these traversals have a somewhat common way of going over the nodes of the tree.

In-order

This traversal first goes over the left subtree of the root node, then accesses the current node, followed by the right subtree of the current node. The code represents the base case too, which says that an empty tree is also a binary search tree.

void inOrder(struct node* root) { // Base case if (root == null) { return; } // Travel the left sub-tree first. inOrder(root.left); // Print the current node value printf("%d ", root.data); // Travel the right sub-tree next. inOrder(root.right); }

Pre-order

This traversal first accesses the current node value, then traverses the left and right sub-trees respectively.

void preOrder(struct node* root) { if (root == null) { return; } // Print the current node value printf("%d ", root.data); // Travel the left sub-tree first. preOrder(root.left); // Travel the right sub-tree next. preOrder(root.right); }

Post-order

This traversal puts the root value at last, and goes over the left and right sub-trees first. The relative order of the left and right sub-trees remain the same. Only the position of the root changes in all the above mentioned traversals.

void postOrder(struct node* root) { if (root == null) { return; } // Travel the left sub-tree first. postOrder(root.left); // Travel the right sub-tree next. postOrder(root.right); // Print the current node value printf("%d ", root.data); }

Relevant videos on freeCodeCamp YouTube channel

And Binary Search Tree: Traversal and Height

Following are common types of Binary Trees:

Full Binary Tree/Strict Binary Tree: A Binary Tree is full or strict if every node has exactly 0 or 2 children.

 18 / \ / \ 15 30 / \ / \ 40 50 100 40

In Full Binary Tree, number of leaf nodes is equal to number of internal nodes plus one.

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

 18 / \ / \ 15 30 / \ / \ 40 50 100 40 / \ / 8 7 9

Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.

 18 / \ / \ 15 30 / \ / \ 40 50 100 40

Augmenting a BST

Sometimes we need to store some additional information with the traditional data structures to make our tasks easier. For example, consider a scenario where you are supposed to find the ith smallest number in a set. You can use brute force here but we can reduce the complexity of the problem to O(lg n) by augmenting a red-black or any self-balancing tree (where n is the number of elements in the set). We can also compute rank of any element in O(lg n) time. Let us consider a case where we are augmenting a red-black tree to store the additional information needed. Besides the usual attributes, we can store number of internal nodes in the subtree rooted at x(size of the subtree rooted at x including the node itself). Let x be any arbitrary node of a tree.

x.size = x.left.size + x.right.size + 1

While augmenting the tree, we should keep in mind, that we should be able to maintain the augmented information as well as do other operations like insertion, deletion, updating in O(lg n) time.

Since, we know that the value of x.left.size will give us the number of nodes which proceed x in the order traversal of the tree. Thus, x.left.size + 1 is the rank of x within the subtree rooted at x.