Binary Search Tree (Binary Search Tree)

What is a binary search tree?

A binary search tree (BST Search Tree) is a tree in which all nodes have the following characteristics:

The subtree on the left of a node has a key (key) less than or equal to the key value of the parent node (of this subtree).

The subtree to the right of a node has a key greater than or equal to the key value of the parent node (of this subtree).

So it can be said that a binary search tree (BST) divides all its subtrees into two parts: the left subtree and the right subtree and can be defined as follows:

left_subtree (keys) ? node (key) ? right_subtree (keys)

Representing binary search tree (BST)

Binary search tree (BST) is a set of nodes arranged in such a way that they can maintain or obey the characteristics of the binary search tree. Each node has a key and value associated with it. While searching, the key to be found is compared to the keys in the binary search tree (BST) and, if found, the associated value will be captured.

Example of a binary search tree (BST):

From the example shown above, we see that the key of the root node has a value of 27 and all the keys on the left of the left subtree are worth less than 27 and all the keys on the right of the right subtree all have a value greater than 27.

Basic operation on binary search tree

Here are some basic operations that can be performed on the binary search tree:

Search activity : search for an element in a tree.

Insert operation : insert an element into a tree.

Pre-order browsing activity : browse a tree in a way that approves the order.

Secondary browsing operation : browse a tree in a secondary way to browse the order.

Post-order browsing operation: browse a tree in the order of post-order browsing.

Button (Node) in binary search tree

A node has some data, referring to its left and right child nodes.

 struct node { int data ; struct node * leftChild ; struct node * rightChild ; }; 

Search activity in binary search tree

Every time an element is searched: start searching from the root node, then if the data is smaller than the key value, then find the element in the left subtree; If larger, find the element in the right subtree. Here is the algorithm for each button:

 struct node * search ( int data ){ struct node * current = root ; printf ( "Truy cap cac phan tu: " ); while ( current -> data != data ){ if ( current != NULL ) { printf ( "%d " , current -> data ); //t?i cây con bên trái if ( current -> data > data ){ current = current -> leftChild ; } //else t?i cây con bên ph?i else { current = current -> rightChild ; } //không tìm th?y if ( current == NULL ){ return NULL ; } }	} return current ; } 

Insert operation in binary search tree

Every time an element is inserted: first we need to determine the exact location of this element. Start searching from the root node, then if the data is smaller than the key value, search for the vacant position on the left subtree and insert data into it; If the data is smaller then search for the live position on the right subtree and insert data into it.

 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 ; //N?u cây là tr?ng if ( root == NULL ){ root = tempNode ; } else { current = root ; parent = NULL ; while ( 1 ){ parent = current ; //t?i cây con bên trái if ( data < parent -> data ){ current = current -> leftChild ; //chèn d? li?u vào cây con bên trái if ( current == NULL ){ parent -> leftChild = tempNode ; return ; } } //t?i cây con bên ph?i else { current = current -> rightChild ; //chèn d? li?u vào cây con bên ph?i if ( current == NULL ){ parent -> rightChild = tempNode ; return ; } } } } } 

Next lesson: AVL tree in data structure and algorithm