Prepared By : Uday Shah (HOD-IT)
Contact No : 7600044051
E-Mail : rupareleducation@gmail.com
Binary Search
Tree
A Binary
Search Tree (BST) is a tree in which all the nodes follow the below-mentioned
properties
·
The
left sub-tree of a node has a key less than or equal to its parent node's key.
·
The
right sub-tree of a node has a key greater than to its parent node's key.
Thus,
BST divides all its sub-trees into two segments; the left sub-tree and the
right sub-tree
BST is a
collection of nodes arranged in a way where they maintain BST properties. Each
node has a key and an associated value. While searching, the desired key is
compared to the keys in BST and if found, the associated value is retrieved.
We
observe that the root node key (27) has all less-valued keys on the left
sub-tree and the higher valued keys on the right sub-tree.
Insert Operation
Whenever
an element is to be inserted, first locate its proper location. Start searching
from the root node, then if the data is less than the key value, search for the
empty location in the left subtree and insert the data. Otherwise, search for
the empty location in the right subtree and insert the data.
Delete Operation
If we
want to delete a node from BST, we basically have 3 different situations:
DELETE A LEAF NODE
For
example, if we want to delete 19 from the above BST example, we can just simply
wipe out the link and reclaim the memory by deleting the node and making its
parent pointing to NULL (cut the link and wipe out the memory).
The BST
will still be valid after this node removed. The properties are still
conserved.
DELETE A NODE WITH ONLY 1 CHILD
It is
clearly obvious that we can’t just delete/remove a node that is not a leaf
node. Because we would abandon its sub tree as well. To delete a node with only
1 child, we can link its parent node to its only child.
For example,
if we want to delete 7 in the above BST, we can link 5 to its only child 9, and
remove the node 7. In other words, the sub tree of the to-be-deleted node will
be re-attached and the properties of BST will be still valid.
DELETE A NODE WITH 2 CHILDREN
The
most complex situation is to delete a node with 2 children. If we want to
delete 15 from the above BST, we can do some tricks to reduce the situation to
either case 1 or case 2.
1. Find The
Minimal Value Of Its Right Subtree
2. Find The
Maximum Value Of Its Left Subtree
B-Tree
In a binary search tree,
AVL Tree, Red-Black tree etc., every node can have only one value (key) and
maximum of two children but there is another type of search tree called B-Tree
in which a node can store more than one value (key) and it can have more than
two children. B-Tree was developed in the year of 1972 by Bayer and McCreight with the
name Height Balanced m-way Search Tree. Later it was named as B-Tree.
Insertion Operation in B-Tree
In a
B-Tree, the new element must be added only at leaf node. That means, always the
new key Value is attached to leaf node only. The insertion operation is
performed as follows...
Step
1: Check whether tree is Empty.
Step
2: If tree is Empty, then create a new node with new key value and insert
into the tree as a root node.
Step
3: If tree is Not Empty, then find a leaf node to which the new key
value cab be added using Binary Search Tree logic.
Step
4: If that leaf node has an empty position, then add the new key value to
that leaf node by maintaining ascending order of key value within the node.
Step
5: If that leaf node is already full, then split that leaf node
by sending middle value to its parent node. Repeat tha same until sending value
is fixed into a node.
Step
6: If the spilting is occuring to the root node, then the middle value
becomes new root node for the tree and the height of the tree is increased by
one.
Best Of Luck
Please give your comment and share it... Thank You.
