UNIT - IV CHAPTER – 15
BINARY SEARCH TREE CHAPTER – 16
BALANCED SEARCH TREE

Slide 2:

CHAPTER – 15
BINARY SEARCH TREE

CONTENTS :

CONTENTS 1. DEFINITIONS
1.1. BINARY SEARCH TREES
2. ABSTRACT DATA TYPES
3. BINARY SEARCH TREE OPERATIONS
3.1.SEARCHING
3.2.INSERTION
3.3.DELETION
3.4.HEIGHT OF BINARY SERACH TREE
4. BINARY SERACH TREE WITH DUPLICATES
5. INDEXED BINARY SERACH TREE
6. APPLICATIONS

1. DEFINITIONS :

1. DEFINITIONS 1.1. Binary Search Tree
A Binary Search Tree is a binary tree that may be empty. A non-empty binary search tree satisfies the following properties:
1. Every node has a value and no two elements
(nodes) have the same value, therefore all
values are distinct.
2. The values in the left subtree of the root are
smaller than the key in the root.
3. The values in the right subtree of the root
are larger than the key in the root.

Slide 5:

4. The left and right subtrees of the root are
also binary search trees.
EXAMPLE: 20 12 15 25 18 22 It’s not a Binary search Tree, because the right subtree fails to satisfy property – 3 and 4 FIGURE- (a)

Slide 6:

30 The following are Binary Search Trees FIGURE- (b) 40 5 2 30 5 40 FIGURE- (c) 60 65 70 80 FIGURE- (d)

Another Definition :

Another Definition A Binary Search Tree (BST) is an ordered Binary Tree, either it’s an empty tree (or)
- each data value in it’s left subtree is less than
the root value
- each data value in it’s right subtree is greater
than the root value
- Left and Right subtrees are again binary
search tree All < K All > K K

2. ABSTRACT DATA TYPES :

2. ABSTRACT DATA TYPES Abstract Data Type BSTree
{
instance:
binary trees, each node has an element
with a key fields; all keys are distinct;
keys in the left subtree of any node are
smaller than the key in the node; those in
the right subtree are larger.
operations:
Create( ): create an empty binary search
tree

Slide 9:

Search (K, x): return x th – element with key (or)
value K.
return false if the operations fails.
return true if it success.
Insert (x): insert an element x into the search
tree
Delete (k, e) : delete the element with key (or)
value k and return it in x
Ascend ( ) : Output all element in ascending
order of key (or) value.
}

3. BINARY SEARCH TREE OPERATIONS :

3. BINARY SEARCH TREE OPERATIONS 3.1. SEARCHING
* Suppose we wish to search an element with key
(or) value (k), we begin at the Root. If the root is
NULL, the search tree contains no elements, and
the search is unsuccessful.
* Otherwise, we compare K-with the key/value in
the Root. If K – is less than the key/value in
the root, then no element in the right subtree can
have key/value (k) and only left subtree is to be
searched.

Slide 11:

* If k – is larger than the key in the root, only
the right subtree need to be searched.
* If k – equals to the key/value in the root, then
the search terminates successfully. The subtree
may be searched similarly.

Algorithm for BST - searching :

Algorithm for BST - searching algorithm SearchBST
search a binary search tree for a given value
precondition: root is the root to a binary tree (or)
subtree argument is the key value
requested.
Return: the node address, if the value is found null
if the node is not in the tree.
1. if (root is null)
1. return null
2. end if

Slide 13:

3. if ( argument < root key)
1. return searchBST ( root left, argument)
4. elseif (argument > root key)
1. return searchBST (root right, argument)
5. else
1. return root
6. end if
end if
End searchBST

Example – BST SEARCH :

Example – BST SEARCH Find a given node in a binary search tree, let us consider the following figure: 23 12 18 44 20 52 35 Search Node : 20

Slide 15:

Suppose we are looking for node : 20, we begin by comparing the search argument 20, with the value in the tree “Root”.
Because 20 is less than the Root value 23, and because we know that all values less than the Root lie in it’s Left subtree, we go Left.
Now compare the search argument with the value in the subtree:18. This time the search argument is greater than the tree value:18
We know that values greater than the tree Root must lie in it’s Right Subtree, we go right and find our desired value.

The logic of BST – search work in the following ways: :

The logic of BST – search work in the following ways: To search a particular node in the BST, we use the procedure similar to “ Insertion”.
Beginning at the root node, the current node & the entered node are compared.
If the values are equal, SUCCESS is output. If the entered value is less than the value in the node then it must be in the left-child of subtree.
If there’s no left child subtree, the value is not in the tree, (i.e. a failure is reported).
If the entered value is greater than the value in the current node, the right child is searched.

LOGIC FOR BST-SEARCH :

LOGIC FOR BST-SEARCH find-key (key-value, node)
{
if ( two values are same)
{
print value stored in node;
return (SUCCESS);
}
else if( key-value stored in current node)
{
if ( left child exists)
{
find-key ( key-value, left hand);
}
else

Slide 18:

{ there is no left subtree;
return( string not found)
}
}
else if ( key-value stored in current node)
{ if ( right child exists)
{
find-key( key-value, right child);
}
else
{ there is no right subtree;
return (string not found)
}
}
}

3.2.insertion :

3.2.insertion All BST-insertion take place at a Leaf (or) Leaf like node.
Inserting a Node to the Tree:
* To insert a node in a BST, we must check whether
the tree already contains any nodes.
* If the tree is empty, the node is placed in the
Root node. If the tree is not empty, then the proper
location is found and the added node becomes either
a Left (or) a Right child of an existing node.

The logic of BST – insert work in the following ways: :

The logic of BST – insert work in the following ways: Add-node (node, value)
{
if (two values are same)
{
duplicate;
return (FAILURE)
}
else if (value < value stored in current node)
{
if (left child exists)
{
add-node (left child, value);
}

Slide 21:

else
{
allocate new node and make left child point to it;
return (SUCCESS);
}
}
else if (value > value stored in current node)
{
if (right child exists)
{
add-node (right child, value);
}

Slide 22:

else
{
allocate new node and make right child point to it;
return (SUCCESS);
}
}

Algorithm for BST - insertion :

Algorithm for BST - insertion Algorithm addBST
insert node containing new data into BST using
recursion
Precondition : root is address of current node
in a BST.
new is address of node containing data
to be inserted.
Postcondition : new is address of node containing
data to be inserted.

Slide 24:

1. if ( root is null)
1. root = new
2. else
location for new node found
1. if (new key < root key)
1. addBST ( root left, new)
2. else
1. addBST ( root right, new)
3. end if
3. end if
4. return
end addBST

Example – BST INSERTION :

Example – BST INSERTION Let us assume the following BST: 23 12 18 44 20 52 35 New node 19 is going to be added, to the existing BST

Slide 26:

Suppose if we want to insert the element 19, it will first compared to the Root node 23.
The element 19 is less than the root node 23, so insertion will take place left child of the Root node 23
(19 < 23).
The left side tree of root node 23 is: 23 12 18 20

Slide 27:

Again the new node 19 is compared with the left side tree root 18. Hence new node 19 is greater than the root 18. so node insertion is going to take place “Right side of the root 18”. ( 18 > 19).
The right side of node 18 contains the element 20. Hence new node 19 is less than the node 20. (19 < 20).
so the new node 19 is inserted into left side of the node 20. 18 20

Slide 28:

23 12 18 44 20 52 35 19

Slide 29:

Suppose if w want to insert the new node 38., it’s inserted right side of the existing node 35. 23 12 18 44 20 52 35 19 38

3.3.Deletion :

3.3.Deletion METHOD-I
To delete a node from a binary search tree there are
four possible cases when we delete a node:
1. If node is a leaf node (or) node has no children, it
can be deleted by making it’s parent to null.
EXAMPLE:
Consider the following figure, to remove 35 from the tree, the left child field of its parent is set to null, and the node is discarded. The resulting tree will appear as follow 30 40 5 2 30 40 5 2 35 80 80

Slide 31:

2. If the node has one child, it’s parent pointer needs to
be adjusted.
EXAMPLE:
consider the following tree:
if node (1) is deleted, the right child of node(1) (that’s node (4)) become the left child of node (6). The new BST will be as follow: 8 9 6 1 7 4 8 9 6 4 7

Slide 32:

3. If the node to be deleted has two children, the node
value is replaced by the
(i) Smallest value in the Right subtree (or)
(ii) Largest value in the Left subtree
Example:
consider the following tree: 10 12 6 5 9 7 4 11 8

Slide 33:

If the node(6) is to be deleted, then it’s value is replaced by smallest value in the right subtree (i.e. by 7). The new BST will be; 10 12 7 5 9 8 4 11

Algorithm for BST - deletion :

Algorithm for BST - deletion Algorithm deleteBST ( ref root < pointer>,
val dltkey < key>)
precondition: root is pointer to tree containing data to
to be deleted.
dltkey is key of node to be deleted.
postcondition: node deleted & memory recycled, if
dltkey not found, root unchanged.
return : true if node deleted,
false if not found
1. if ( root null)
1. return false

Slide 35:

2. end if
3. if (dltkey < root data.key)
1. return deleteBST (root left, dltkey)
4. elseif (dltkey > root data.key)
1. return deleteBST (root right,dltkey)
5. else
delete node found, test for leaf node
1. if (root left null)
1. dltptr = root
2. root = root right
3. recycle (dltptr)
4. return true

Slide 36:

2. elseif (root right null)
1. dltptr = root
2. root = root left
3. recycle (dltptr)
4. return true
3. else
node to be deleted not a leaf. Find largest node on
left subtree
1. dltptr = root left
2. loop (dltptr right not null)
1. dltptr = dltptr right

Slide 37:

node found, move data and delete leaf node
3. root data = dltptr data
4. return deleteBST ( root left,
dltptr data, key)
4. end if
6. end if
End deleteBST

4. BINARY SERACH TREE WITH DUPLICATES :

4. BINARY SERACH TREE WITH DUPLICATES Definition
The BST is permitted to contain two (or) more elements that have the same key is called “ Duplicate Binary Search Tree” (DBST). 6 3 6 1 2 20 5 1 1 8

Slide 39:

We can remove the requirement that all elements in a BST need “distinct keys”. Now we can make smaller changes in property-2 and property-3 (refer slide-4).
Property-2:
the value in the left subtree of the root are smaller than and equal to (<=) key in the root.
propety-3:
the value in the right subtree of the root are greater than and equal to(>=) the key in the root.
The resulting tree is called “DBST”.

5. INDEXED BINARY SERACH TREE :

5. INDEXED BINARY SERACH TREE An Indexed BST, is derived from an ordinary BST-by adding the field “leftsize” to each tree node. This fields gives the number of elements in the nodes left subtree. 20 12 15 25 18 30 3 1 0 0 0 0 3- nodes

Slide 41:

30 40 5 2 2 1 0 0 2- nodes The above figures shows a Indexed BST. The number inside a node is the element key, the outside value of the node is the value of Leftside. Notice that the leftside also gives the index of an element with respect to the elements in its subtree.
For (e.g.) from the above figures, the element (in sorted order) in the subtree with root 20 are (12,15,18,25,30). The index of the root is 3, which is equal to its Leftsize value.

Slide 42:

In the subtree with root 15, the elements (in sorted order) are 12,18. so the index of root element 15 is 1, and its leftsize value is also 1.
ADT for Indexed Binary Search Tree
Abstract Data Type Indexed BST
{
instances: same as for BST, except that each node
has a leftsize field
operations:
get (k): return the element with key (k)
get (index) : return the index th element

Slide 43:

put (k, x): put element ‘x’ with key (k) into the
search tree.
remove (k): remove the element with key (k) and
return it.
remove (index) : remove the index th element and
return it.
ascend ( ) : output all elements in ascending order of
key
}

6. APPLICATIONS :

6. APPLICATIONS 1. Histogramming
2. Best-fit Bin packing
3. Crossing Distribution

Algorithm to find the smallest node in a BST :

Algorithm to find the smallest node in a BST precondition : root is a pointer to a nonempty BST
(or) subtree.
Return : address of smallest node
1. if ( root left null)
1. return (root)
2. end if
3. return smallestBST( root left)
end

Algorithm to find largest node in a BST :

Algorithm to find largest node in a BST precondition : root is a pointer to a nonempty BST
(or) subtree.
Return : address of largest node
1. if ( root right null)
1. return (root)
2. end if
3. return largestBST( root right)
end

Slide 47:

Construction of Binary
Search Tree

Slide 48:

Represent the following numbers in a BST form:
32,41,12,16,19,45,28,18,14
and parse the tree in
(i) pre-order
(ii) in-order
(iii) post-order
Step-1
Step-2 32 32 41

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.

By: fanaah (58 month(s) ago)

plz send this ppt to gloryfanaah@gmail.com