Binary Search Tree

A.     Binary Search Tree

Binary search tree (BST) are data structure with binary tree concept or known as sorted version of binary tree are made to help fast searching, rapid sorting and easy insertion and deletion.

There are some rules for BST:

·        Every node has a value

·        Left value will always smaller than the root

·        Right value will always bigger than the root

·        Right tree or left tree can be another root or can have child, so BST have recursive function.

These rules are there to made searching process efficient.

B.     Binary Search Tree Operation

BST have three basic operation

1.      Find/Searching

Because BST is sorted searching in BST is easy. We only need to use some rules.

1.      Start searching at root.

2.      If the root contains the value, then we can return the value and stop searching process.

3.      If the value is less than root key then search recursively on left sub tree until the value is found, otherwise if the value is higher than recursively search on right sub tree.

2.      Insertion

As we know inserting is inputting new data into the tree. Insertion in BST is done recursively.

1.      We give the value we want to input.

2.      We begin at root.

3.      If the root value is lower then the value then goes into left sub tree and make the value as root value, otherwise go into right sub tree.

4.      Repeat until we found an empty node to put new value.

3.      Remove/deletion

There are 3 cases which should be considered:

1.      If the deleted node is in a leaf, just delete that node

2.      If the deleted node is in a node which has one child, delete that node and connect its child to its parent

3.      If the deleted node is in a node which has two children, find the right most child of its left sub tree (node P), replace its with P and remove P recursively. (or alternately you can choose the left most child of its right sub tree)