Binary Search Tree

In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree.
A binary tree is a type of data structure for storing data such as numbers in an organized way. Binary search trees allow binary search for fast lookup, addition and removal of data items, and can be used to implement dynamic sets and lookup tables. The order of nodes in a BST means that each comparison skips about half of the remaining tree, so the whole lookup takes time proportional to the binary logarithm of the number of items stored in the tree.
This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables. Several variants of the binary search tree have been studied.

Methods' costs

As mentioned in the introduction, a great advantage of binary search trees is the fact they are very compact and easy to find data, what makes its operations fast. You can check on the table bellow the cost of each method:

Insertion

The insertion cost in average is proportional to log₂(n) and in worst case it is proportional to (n), in which n is the number of nodes

Search

The insertion cost in average is proportional to log₂(n) and in worst case it is proportional to (n), in which n is the number of nodes

Removal

The insertion cost in average is proportional to log₂(n) and in worst case it is proportional to (n), in which n is the number of nodes

Code in C language

bst.h

bst.c

main.c

bst.h

#include >stdio.h>
#include >stdlib.h>

#ifndef INC_11_BST_BST_H
#define INC_11_BST_BST_H

typedef struct node {
    int key;
    struct node *parent; // ascendent in the tree
    struct node *left; // left child in the tree
    struct node *right; // right child in the tree
} node;

typedef struct tree {
    node *root;
} tree;

/*
 * Frees all the tree's nodes.
 */
void free_nodes(node* p);

/*
 * Frees all the tree's nodes and the tree itself.
 */
void bst_free(tree* T);

/*
 * If the pointer is equal to NULL it allocates a tree, otherwise it frees the current
 * tree and nodes that belong to it and allocates a new tree with no nodes.
 * Returns a pointer to the tree allocated. In case of fail returns NULL.
 */
tree *create(tree *T);

/*
 * Searches for a key in the tree nodes.
 * In case it founds a node containing the key, it returns a pointer to this node,
 * otherwise it returns NULL.
 */
node *search(node *p, int number);

/*
 * Inserts a key into the BST. Returns 1 on success.
 * In case of memory insuficiency, returns 0.
 * In case the key already exists in the tree, it doesn't insert another key and returns 1.
 */
int insert(tree *T, int data);

/*
 * Prints the keys in the order they are visited by a pre-order deep path.
 */
void pre_order_print(node *n);

/*
 * Prints the keys in the order they are visited by a pre-order deep path.
 * In case there are no keys, it prints "arvore vazia".
 */
void pre_order(tree *T);

/*
 * Prints the keys in the order they are visited by a in-order deep path.
 */
void in_order_print(node *n);

/*
 * Prints the keys in the order they are visited by a in-order deep path.
 * In case there are no keys, it prints "arvore vazia".
 */
void in_order(tree *T);

/*
 * Prints the keys in the order they are visited by a post-order deep path.
 */
void post_order_print(node *n);

/*
 * Prints the keys in the order they are visited by a post-order deep path.
 * In case there are no keys, it prints "arvore vazia".
 */
void post_order(tree *T);

/*
 * Returns the node that contains the minimum key of a tree.
 * In case the tree is empty it returns 0.
 */
node *minimum(node *n);

/*
 * Returns the successor of a key in the BST.
 * In case there is no successor or this key in the BST it returns 0.
 */
node *successor(tree *T, int key);

/*
 * Returns the maximum key of a tree.
 * In case the tree is empty it returns 0.
 */
node *maximum(node *n);

/*
 * Returns the predecessor of a key in the BST.
 * In case there is no predecessor or this key in the BST it returns 0.
 */
node *predecessor(tree *T, int key);

/*
 * Removes a node from the BST and places its successor in that position instead.
 * In case there is no node with the referred key in the BST, keeps running the program.
 */
void delete(tree *T, int key);

#endif //INC_11_BST_BST_H

bst.c

#include >stdio.h>
#include >stdlib.h>
#include "bst.h"

/*
 * Frees all the tree's nodes
 */
void free_nodes(node* p) {

    if (p == NULL)
        return;

    free_nodes(p->left);
    free_nodes(p->right);
    free(p);
}

/*
 * Frees all the tree's nodes and the tree itself.
 */
void bst_free(tree* T) {
    free_nodes(T->root);
    free(T);
}

/*
 * If the pointer is equal to NULL it allocates a tree, otherwise it frees the current
 * tree and nodes that belong to it and allocates a new tree with no nodes.
 * Returns a pointer to the tree allocated. In case of memory allocation failure returns NULL.
 */
tree *create(tree *T) {
    if (T != NULL) {
        bst_free(T);
    }

    T = (tree *) calloc(1, sizeof(tree));
    if (T == NULL)
        return NULL;

    T->root = NULL;

    return T;
}

/*
 * Searches for a key in the tree nodes.
 * In case it founds a node containing the key, it returns a pointer to this node,
 * otherwise it returns NULL.
 */
node *search(node *p, int number) {

    if (p == NULL)
        return NULL;

    if (p->key == number)
        return p;

    if (p->key < number)
        return search(p->right, number);
    else
        return search(p->left, number);
}

/*
 * Inserts a key into the BST. Returns 1 on success.
 * In case of memory insuficiency, returns 0.
 * In case the key already exists in the tree, it doesn't insert another key and returns 1.
 */
int insert(tree *T, int data) {
    node* n = calloc(1,sizeof(node));
    if (!n) {
        return 0;
    }

    n->key = data;

    if (T->root == NULL) {
        n->parent = NULL;
        T->root = n;
        return 1;
    }

    if (search(T->root, data) != NULL)
        return 1;

    node* p = T->root;
    node* pp = NULL;

    while (p != NULL) {
        if (p->key == data)
            return 1;
        pp = p;
        if (p->key > data)
            p = p->left;
        else
            p = p->right;
    }


    if (pp->key > data)
        pp->left = n;
    else
        pp->right = n;

    n->parent = pp;

    return 1;
}

/*
 * Prints the keys in the order they are visited by a pre-order deep path.
 */
void pre_order_print(node *n) {
    if (n != NULL) {
        printf("%d ", n->key);
        pre_order_print(n->left);
        pre_order_print(n->right);
    }
}

/*
 * Prints the keys in the order they are visited by a pre-order deep path.
 * In case there are no keys, it prints "arvore vazia".
 */
void pre_order(tree *T) {
    if (T->root == NULL) {
        printf("arvore vazia\n");
        return ;
    }

    printf("pre-ordem: ");
    pre_order_print(T->root);
    printf("\n");
}

/*
 * Prints the keys in the order they are visited by a in-order deep path.
 */
void in_order_print(node *n) {
    if (n != NULL) {
        in_order_print(n->left);
        printf("%d ", n->key);
        in_order_print(n->right);
    }
}

/*
 * Prints the keys in the order they are visited by a in-order deep path.
 * In case there are no keys, it prints "arvore vazia".
 */
void in_order(tree *T) {
    if (T->root == NULL) {
        printf("arvore vazia\n");
        return ;
    }

    printf("em-ordem: ");
    in_order_print(T->root);
    printf("\n");
}

/*
 * Prints the keys in the order they are visited by a post-order deep path.
 */
void post_order_print(node *n) {
    if (n != NULL) {
        post_order_print(n->left);
        post_order_print(n->right);
        printf("%d ", n->key);
    }
}

/*
 * Prints the keys in the order they are visited by a post-order deep path.
 * In case there are no keys, it prints "arvore vazia".
 */
void post_order(tree *T) {
    if (T->root == NULL) {
        printf("arvore vazia\n");
        return ;
    }

    printf("pos-ordem: ");
    post_order_print(T->root);
    printf("\n");
}

/*
 * Returns the minimum key of a tree.
 * In case the tree is empty it returns 0.
 */
node *minimum(node *n) {
    if (n == NULL) {
        return NULL;
    }

    while (n->left != NULL)
        n = n->left;

    return n;
}

/*
 * Returns the successor of a key in the BST.
 * In case there is no successor or this key in the BST it returns 0.
 */
node *successor(tree *T, int key) {
    if (T->root == NULL)
        return NULL;

    node *p;
    node *n;
    n = search(T->root, key);
    if (n == NULL)
        return NULL;
    if (n->right != NULL)
        return minimum(n->right);
    p = n->parent;
    while (p != NULL && n == p->right) {
        n = p;
        p = p->parent;
    }

    if (!p)
        return NULL;

    return p;
}

/*
 * Returns the maximum key of a tree.
 * In case the tree is empty it returns 0.
 */
node *maximum(node *n) {
    if (n == NULL) {
        return 0;
    }

    while (n->right)
        n = n->right;

    return n;
}

/*
 * Returns the predecessor of a key in the BST.
 * In case there is no predecessor or this key in the BST it returns 0.
 */
node *predecessor(tree *T, int key) {
    if (!T->root)
        return 0;

    node *p;
    node *n;
    n = search(T->root, key);
    if (!n)
        return 0;
    if (n->left)
        return maximum(n->left);
    p = n->parent;
    while (p != NULL && n == p->left) {
        n = p;
        p = p->parent;
    }

    if (!p)
        return 0;

    return p;
}

/*
 * Removes a node from the BST and places its successor in that position instead.
 * In case there is no node with the referred key in the BST, keeps running the program.
 */
void delete(tree *T, int key) {
    node *n;
    n = search(T->root, key);

    if (!n)
        return ;

    if (!n->right && !n->left) {
        if (n == T->root) {
            T->root = NULL;
            free(n);
            return ;
        }
        if (n == n->parent->left)
            n->parent->left = NULL;
        if (n == n->parent->right)
            n->parent->right = NULL;
        free(n);
        return ;
    }

    if (n->right && !n->left) {
        if (n == T->root) {
            T->root = n->right;
            n->right->parent = NULL;
            free(n);
            return ;
        }
        if (n == n->parent->right) {
            n->parent->right = n->right;
            n->right->parent = n->parent;
            free(n);
            return ;
        }
        if (n == n->parent->left) {
            n->parent->left = n->right;
            n->right->parent = n->parent;
            free(n);
            return ;
        }
    }

    if (n->left && !n->right) {
        if (n == T->root) {
            T->root = n->left;
            n->left->parent = NULL;
            free(n);
            return ;
        }
        if (n == n->parent->right) {
            n->parent->right = n->left;
            n->left->parent = n->parent;
            free(n);
            return ;
        }
        if (n == n->parent->left) {
            n->parent->left = n->left;
            n->left->parent = n->parent;
            free(n);
            return ;
        }
    }

    if (n->right && n->left) {
        node *y = successor(T, key);
        n->key = y->key;
        if (y == n->right) {
            n->right = y->right;
            if (y->right)
                y->right->parent = n;
            free(y);
            return ;
        }
        if (!y->right) {
            y->parent->left = NULL;
        }
        else {
            y->parent->left = y->right;
            y->right->parent = y->parent;
        }
        free(y);
        return ;
    }
}

main.c

#include >stdlib.h>
#include >stdio.h>
#include >errno.h>
#include >string.h>
#include "bst.h"
#define MAX 50

int main() {
    char cmd[MAX];
    int keep_running = 1;
    int number;
    tree *T = NULL;
    node *n;

    while (keep_running) {
        scanf("%s%*c", cmd);
        if (strcmp(cmd, "inserir") == 0 || strcmp(cmd, "remover") == 0 || strcmp(cmd, "buscar") == 0 ||
            strcmp(cmd, "sucessor") == 0 || strcmp(cmd, "predecessor") == 0)
            scanf(" %d", &number);

        if (strcmp(cmd, "criar") == 0) {
            T = create(T);
            if (!T)
                exit(errno);
        }

        if (strcmp(cmd, "buscar") == 0) {
            n = search(T->root, number);
            if (!n)
                printf("%d nao esta na arvore\n", number);
            else
                printf("%d esta na arvore\n", number);
        }

        if (strcmp(cmd, "inserir") == 0) {
            keep_running = insert(T, number);
            if (!keep_running) {
                printf("memoria insuficiente");
                keep_running = 1;
            }
        }

        if (strcmp(cmd, "pre-ordem") == 0)
            pre_order(T);

        if (strcmp(cmd, "em-ordem") == 0)
            in_order(T);

        if (strcmp(cmd, "pos-ordem") == 0)
            post_order(T);

        if (strcmp(cmd, "sucessor") == 0) {
            n = successor(T, number);
            if (!n)
                printf("nao ha sucessor de %d\n", number);
            else
                printf("sucessor de %d: %d\n", number, n->key);
        }

        if (strcmp(cmd, "predecessor") == 0) {
            n = predecessor(T, number);
            if (!n)
                printf("nao ha predecessor de %d\n", number);
            else
                printf("predecessor de %d: %d\n", number, n->key);
        }

        if (strcmp(cmd, "remover") == 0)
            delete(T, number);

        if (strcmp(cmd, "terminar") == 0) {
            bst_free(T);
            keep_running = 0;
        }
    }

    return 0;
}

Contact me

First name

Last name

E-mail

Message

About me

This page was developed as a front-end project. It is a first contact project with HTML and CSS, it comes to explaining a little classic data structure called Binary Search Tree (BST), showing some methods involved by the structure, giving examples and showing some code developed in C language for it by me.
In case you get interested in checking other data structures' code click here or in viewing other of my projects, you can access my GitHub by clicking the photo!