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