Binary Search Tree (BST)

Дерево, Tree, Алгоритм

Binary search tree is a data structure that allows you to maintain a sorted list of numbers.

• A binary (binary) tree is called because each tree node has a maximum of two child elements.
• A search tree because it can be used to search for a number in O(log(n)) time (algorithm with time complexity T(n) = O(log(n))(ed. note)).

Properties that distinguish a binary search tree from a regular binary tree:

1. All nodes of the left subtree are less than the root node.
2. All nodes of the right subtree are greater than the root node.
3. Both subtrees of each node are also BSTs, i.e. they have the above two properties.

The binary tree on the right is not a binary search tree because the right subtree of node "3" contains a value that is less than it.

There are two main operations that you can perform on a binary search tree:

one. Checking if a number is present in a binary search tree.

The algorithm depends on the BST property so that if every left subtree has values below the root, then every right subtree has values above the root.

If the value is lower than the root, we can say with certainty that the value is not in the right subtree, which means we should look for it in the left subtree.
And vice versa, if the value is higher than the root, it is certain that the value is not in the left subtree, which means you need to look in the right one.

Algorithm:

If root == NULL 
    return NULL;
If number == root->data 
    return root->data;
If number < root->data 
    return search(root->left)
If number > root->data 
    return search(root->right)

Let's try to visualize the algorithm with a diagram.

If a value is found, we return the value so that it propagates through each step of the recursion, as shown in the figure below.

You may have noticed that we called the return search (struct node) function four times. When we return either a new node or NULL, the value is returned over and over until search(root) returns the final result.

If no value is found, we eventually reach the left or right child of the end node, which is NULL, and it propagates and returns.

2. Inserting a value into a binary search tree (BST)

Inserting a value in the correct position is similar to searching because we are trying to match the rule that the left subtree is less than the root and the right subtree is greater than the root.

We keep going to either the right or left subtree depending on the value, and when we reach a point where the left or right subtree is zero, we put a new node there.

Algorithm:

If node == NULL 
    return createNode(data)
if (data < node->data)
    node->left  = insert(node->left, data);
else if (data > node->data)
    node->right = insert(node->right, data);  
return node;

The algorithm is not as simple as it seems. Let's try to visualize how we add a number to an existing BST.

We've connected the node, but we still need to exit the function without harming the rest of the tree. This is where the return node at the end comes in handy. In this case NULL, the newly created node is returned and attached to the parent node, otherwise the same node is returned without any changes until we return to the root node.

This ensures that when we go back up the tree, connections to other nodes don't change.

The complete code for inserting and searching in BST in the C programming language is given below:

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

struct node
{
    int data;
    struct node* left;
    struct node* right;
};

struct node* createNode(value){
    struct node* newNode = malloc(sizeof(struct node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}


struct node* insert(struct node* root, int data)
{
    if (root == NULL) return createNode(data);

    if (data < root->data)
        root->left  = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);   

    return root;
}

void inorder(struct node* root){
    if(root == NULL) return;
    inorder(root->left);
    printf("%d ->", root->data);
    inorder(root->right);
}


int main(){
    struct node *root = NULL;
    root = insert(root, 8);
    insert(root, 3);
    insert(root, 1);
    insert(root, 6);
    insert(root, 7);
    insert(root, 10);
    insert(root, 14);
    insert(root, 4);

    inorder(root);
}

Program output

1 ->3 ->4 ->6 ->7 ->8 ->10 ->14 ->