Scribd
Upload
10 views

Data - Structure - and - Algorithms - Lecture - 8 Trees

Uploaded by

Hasnain Nisar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views

Data - Structure - and - Algorithms - Lecture - 8 Trees

Uploaded by

Hasnain Nisar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 35

Course Instructor

Engr. Adiba Jafar


CHAPTER #7
TREES
BINARY SEARCH TREE(BST)
BST is a special type of tree in which nodes are assigned
in specific order.
In a binary search tree (BST), each node contains-

• Only smaller values in its left sub tree

• Only larger values in its right sub tree


EXAMPLE
Binary Search Tree Construction-
 Construct a Binary Search Tree (BST) for the
following sequence of numbers-
 50, 70, 60, 20, 90, 10, 40, 100
When elements are given in a sequence,

1. Always consider the first element as the root node.


2. Consider the given elements and insert them in the
BST one by one.
50, 70, 60, 20, 90, 10, 40,
100
50, 70, 60, 20, 90, 10, 40,
100
50, 70, 60, 20, 90, 10, 40,
100
50, 70, 60, 20, 90, 10, 40,
100
50, 70, 60, 20, 90, 10, 40,
100
50, 70, 60, 20, 90, 10, 40,
100
50, 70, 60, 20, 90, 10, 40,
100
EXAMPLE
Application of binary search tree
Consider a collection of n data items A1,A2,A3,……….,An.
Suppose we want to find and delete all duplicates in the
collection.
FIRST WAY
CONTINUE
SECOND WAY
DELETION IN BST
There are three cases
Consider following tree
DELETING IN BST(delete 44)
CASE 1 N has no children
SOLUTION N is deleted from T by simply replacing the
location of N in the parent node P(N) by the NULL pointer.
Case 2
N has exactly one child( delete 75)
SOLUTION
N is deleted from T by simply replacing the location of N
in P(N) by the location of the only child of N.
Case 3
N has two children
SOLUTION
Let S(N) denote the inorder successor of N.(The reader
can verify that S(N) does not have a left child)Then N is
deleted from T by first deleting S(N) from T(by using
Case 1 or Case 2) and then replacing node N in T by the
node S(N).
Case 3 (Delete 25)
B Tree
In computer science, a B-tree is a self-balancing tree
data structure that maintains sorted data and allows
searches, sequential access, insertions, and deletions
in logarithmic time. The B-tree generalizes the binary
search tree, allowing for nodes with more than two
children.
Definition of B Tree
Example of B tree
Constructing a B Tree
Continue
HOME TASKS
Problem-01:
A binary search tree is generated by inserting in order
of the following integers-
 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
How many number of nodes in the left subtree and
right subtree of the root??
Problem 02
Insert the following keys to 5-way B-tree
3,7,9,23,45,1,5,14,25,24,13,11,8,19,4,31,35,56

You might also like