M.E - Computer Science and Engineering-Data structure-bst-and-threaded

BINARY SEARCH TREE
(BST)
OR
ORDERED BINARY TREE
OR
SORTED BINARY TREE

Binary Search Trees
• A binary search tree (BST) is a binary tree in which all nodes in the
left sub-tree have a value less than that of the root node and all
nodes in the right sub-tree have a value either equal to or greater
than the root node.
• The same rule is applicable to every sub-tree in the tree.
• Due to its efficiency in searching elements, BSTs are widely used in
dictionary problems where the code always inserts and searches the
elements that are indexed by some key value.

Binary Search Trees
Various operation can be performed on BST
• Insertion
• Deletion
• Search
• Find min
• Find max

Algorithm to Insert a Value in a BST
Insert (TREE, VAL)
Step 1: IF TREE = NULL, then
Allocate memory for TREE
SET TREE->DATA = VAL
SET TREE->LEFT = TREE ->RIGHT = NULL
ELSE
IF VAL < TREE->DATA
Insert(TREE->LEFT, VAL)
ELSE
Insert(TREE->RIGHT, VAL)
[END OF IF]
[END OF IF]
Step 2: End

Algorithm to Delete from a BST
Delete (TREE, VAL)
Step 1: IF TREE = NULL, then
Write “VAL not found in the tree”
ELSE IF VAL < TREE->DATA
Delete(TREE->LEFT, VAL)
ELSE IF VAL > TREE->DATA
Delete(TREE->RIGHT, VAL)
ELSE IF TREE->LEFT AND TREE->RIGHT
SET TEMP = findLargestNode(TREE->LEFT)
SET TREE->DATA = TEMP->DATA
Delete(TREE->LEFT, TEMP->DATA)
ELSE
SET TEMP = TREE
IF TREE->LEFT = NULL AND TREE ->RIGHT = NULL
SET TREE = NULL
ELSE IF TREE->LEFT != NULL
SET TREE = TREE->LEFT
ELSE
SET TREE = TREE->RIGHT
[END OF IF]
FREE TEMP
[END OF IF]
Step 2: End

searchElement (TREE, VAL)
Step 1: IF TREE->DATA = VAL OR TREE = NULL, then
Return TREE
ELSE
IF VAL < TREE->DATA
Return searchElement(TREE->LEFT, VAL)
ELSE
Return searchElement(TREE->RIGHT, VAL)
[END OF IF]
[END OF IF]
Step 2: End
Algorithm to Search a Value in a BST

Finding the Smallest Node in a BST
• The basic property of a BST states that the smaller value will occur
in the left sub-tree.
• If the left sub-tree is NULL, then the value of root node will be
smallest as compared with nodes in the right sub-tree.
• So, to find the node with the smallest value, we will find the value
of the leftmost node of the left sub-tree.
• However, if the left sub-tree is empty then we will find the value of
the root node.
findSmallestElement (TREE)
Step 1: IF TREE = NULL OR TREE->LEFT = NULL, then
Return TREE
ELSE
Return findSmallestElement(TREE->LEFT)
[END OF IF]
Step 2: End

Finding the Largest Node in a BST
• The basic property of a BST states that the larger value will occur
in the right sub-tree.
• If the right sub-tree is NULL, then the value of root node will be
largest as compared with nodes in the left sub-tree.
• So, to find the node with the largest value, we will find the value of
the rightmost node of the right sub-tree.
• However, if the right sub-tree is empty then we will find the value
of the root node.
findLargestElement (TREE)
Step 1: IF TREE = NULL OR TREE->RIGHT = NULL, then
Return TREE
ELSE
Return findLargestElement(TREE->RIGHT)
[END OF IF]
Step 2: End

Threaded Binary Trees
• A threaded binary tree is same as that of a binary tree but with a
difference in storing NULL pointers.
• In the linked representation of a BST, a number of nodes contain a
NULL pointer either in their left or right fields or in both. This space
that is wasted in storing a NULL pointer can be efficiently used to
store some other useful piece of information.
• The NULL entries can be replaced to store a pointer to the in-order
predecessor, or the in-order successor of the node. These special
pointers are called threads and binary trees containing threads are
called threaded trees.
• In the linked representation of a threaded binary tree, threads will
be denoted using dotted lines.

• In one way threading, a thread will appear either in the right field or
the left field of the node.
• If the thread appears in the left field, then it points to the in-order
predecessor of the node. Such a one way threaded tree is called a left
threaded binary tree.
• If the thread appears in the right field, then it will point to the in-
order successor of the node. Such a one way threaded tree is called a
right threaded binary tree.
1
3
2
4
8
5 6 7
1
2
1
0
1
1
9
1
2 3
4 X 5 6 X 7
X 8 X 9 X 10 X 11 X 12 X
Binary tree with one way threading

• In a two way threaded tree, also called a doubled threaded tree,
threads will appear in both the left and right fields of the node.
• While the left field will point to the in-order predecessor of the node,
the right field will point to its successor.
• A two way threaded binary tree is also called a fully threaded binary
tree.
1
3
2
4
8
5 6 7
1
2
1
0
1
1
9
1
2 3
4 5 6 7
X 8 9 10 11 12 X
Binary tree with two way threading

ADVANTAGES
•Enables linear traversal of elements in the tree
•Linear traversal eliminates the use of stacks which in turn consume a
lot of memory space and computer time
•Enables to find the parent of given element without explicit use of
parent pointers
•Enable forward and backward traversal of the nodes

M.E - Computer Science and Engineering-Data structure-bst-and-threaded

Recommended

More Related Content

Similar to M.E - Computer Science and Engineering-Data structure-bst-and-threaded (20)

More from poonkodiraja2806 (7)

Recently uploaded (20)

M.E - Computer Science and Engineering-Data structure-bst-and-threaded