mafulechka
mafulechkaJune 5, 2019, 2:04 p.m.

Binary Search Tree (BST)

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 ->
We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.

Do you like it? Share on social networks!

Comments

Only authorized users can post comments.
Please, Log in or Sign up
B

C++ - Test 002. Constants

  • Result:16points,
  • Rating points-10
B

C++ - Test 001. The first program and data types

  • Result:46points,
  • Rating points-6
FL

C++ - Test 006. Enumerations

  • Result:80points,
  • Rating points4
Last comments
k
kmssrFeb. 9, 2024, 5:43 a.m.
Qt Linux - Lesson 001. Autorun Qt application under Linux как сделать автозапуск для флэтпака, который не даёт создавать файлы в ~/.config - вот это вопрос ))
Qt WinAPI - Lesson 007. Working with ICMP Ping in Qt Без строки #include <QRegularExpressionValidator> в заголовочном файле не работает валидатор.
EVA
EVADec. 25, 2023, 9:30 p.m.
Boost - static linking in CMake project under Windows Ошибка LNK1104 часто возникает, когда компоновщик не может найти или открыть файл библиотеки. В вашем случае, это файл libboost_locale-vc142-mt-gd-x64-1_74.lib из библиотеки Boost для C+…
J
JonnyJoDec. 25, 2023, 7:38 p.m.
Boost - static linking in CMake project under Windows Сделал всё по-как у вас, но выдаёт ошибку [build] LINK : fatal error LNK1104: не удается открыть файл "libboost_locale-vc142-mt-gd-x64-1_74.lib" Хоть убей, не могу понять в чём дел…
G
GvozdikDec. 19, 2023, 8:01 a.m.
Qt/C++ - Lesson 056. Connecting the Boost library in Qt for MinGW and MSVC compilers Для решения твой проблемы добавь в файл .pro строчку "LIBS += -lws2_32" она решит проблему , лично мне помогло.
Now discuss on the forum
AC
Alexandru CodreanuJan. 19, 2024, 10:57 p.m.
QML Обнулить значения SpinBox Доброго времени суток, не могу разобраться с обнулением значение SpinBox находящего в делегате. import QtQuickimport QtQuick.ControlsWindow { width: 640 height: 480 visible: tr…
BlinCT
BlinCTDec. 27, 2023, 7:57 p.m.
Растягивать Image на парент по высоте Ну и само собою дял включения scrollbar надо чтобы был Flickable. Так что выходит как то так Flickable{ id: root anchors.fill: parent clip: true property url linkFile p…
Дмитрий
ДмитрийJan. 10, 2024, 3:18 p.m.
Qt Creator загружает всю оперативную память Проблема решена. Удалось разобраться с помощью утилиты strace. Запустил ее: strace ./qtcreator Начал выводиться весь лог работы креатора. В один момент он начал считывать фай…
Evgenii Legotckoi
Evgenii LegotckoiDec. 12, 2023, 5:48 p.m.
Побуквенное сравнение двух строк Добрый день. Там случайно не высылается этот сигнал textChanged ещё и при форматировани текста? Если решиать в лоб, то можно просто отключать сигнал/слотовое соединение внутри слота и …

Follow us in social networks