PowerPoint Presentation
Data Structures: A Pseudocode Approach with C, Second Edition
1
Binary search trees provide an excellent structure for searching a list and at the same time for inserting and deleting data into the list.
Binary Search Trees
Data Structures: A Pseudocode Approach with C, Second Edition
2
3
A Binary Search Tree is a binary tree with the following
properties:
All items in the left subtree are less than the root.
All items in the right subtree are greater than or equal to the root.
Each subtree is itself a binary search tree.
Data Structures: A Pseudocode Approach with C, Second Edition
4
Data Structures: A Pseudocode Approach with C, Second Edition
5
6
Draw all possible binary search trees for three data elements:
5, 9, and 12.
7
All possible binary search trees for 5, 9, and 12:
9
12
5
8
All possible binary search trees for 5, 9, and 12:
9
12
5
9
12
5
9
All possible binary search trees for 5, 9, and 12:
9
12
5
9
12
5
9
12
5
10
All possible binary search trees for 5, 9, and 12:
9
12
5
9
12
5
9
12
5
12
9
5
11
All possible binary search trees for 5, 9, and 12:
9
12
5
9
12
5
9
12
5
12
9
5
5
12
9
12
Which of the trees below is a valid binary search tree and which one is not?
13
Traverse the binary search tree using the inorder traversal.
Data Structures: A Pseudocode Approach with C, Second Edition
14
Find smallest – iterative algorithm
15
Iterative Approach
algorithm findSmallestBST( root )
Finds the node with the smallest value in a BST
Pre : root – pointer to the root of a BST
Return: pointer to the node with the smallest value (the leftmost node in the tree).
parent = NULL
pWalk = root
loop( pWalk NOT NULL )
parent = pWalk
pWalk = pWalk -> left
end loop
return parent
end findSmallestBST
16
algorithm findSmallestBST( root )
Finds the node with the smallest value in a BST
Pre : root – pointer to the root of a non-empty BST
Return: pointer to the node with the smallest value (the leftmost node in the tree).
pWalk = root
loop( pWalk -> left NOT NULL )
pWalk = pWalk -> left
end loop
return pWalk
end findSmallestBST
Iterative Approach
17
Recursive Approach
algorithm findSmallestBST( root )
Finds the node with the smallest value in a BST
Pre : root – pointer to the root of a non-empty BST
Return: pointer to the node with the smallest value (the leftmost node in the tree).
if( root -> left is NULL )
return root
end if
return findSmallestBst( root -> left )
end findSmallestBST
Data Structures: A Pseudocode Approach with C, Second Edition
18
BST Operations
We discuss four basic BST operations: traversal, search, insert, and delete; and develop algorithms for searches, insertion, and deletion.
Traversals
Searches
Insertion
Deletion
Data Structures: A Pseudocode Approach with C, Second Edition
19
Breadth-first traversal
Data Structures: A Pseudocode Approach with C, Second Edition
20
23, 18, 44, 12, 20, 35, 52
Breadth-first traversal
Data Structures: A Pseudocode Approach with C, Second Edition
21
Depth-first traversal: preorder
Data Structures: A Pseudocode Approach with C, Second Edition
22
23, 18, 12, 20, 44, 35, 52
Depth-first traversal: preorder (Root – Left – Right)
Data Structures: A Pseudocode Approach with C, Second Edition
23
Depth-first traversal: postorder
Data Structures: A Pseudocode Approach with C, Second Edition
24
Depth-first traversal: postorder (Left – Right – Root)
12, 20, 18, 35, 52, 44, 23
Data Structures: A Pseudocode Approach with C, Second Edition
25
Depth-first traversal: inorder
Data Structures: A Pseudocode Approach with C, Second Edition
26
Depth-first traversal: inorder (Left – Root – Right)
12, 18, 20, 23, 35, 44, 52
27
Breadth-first
Depth-first:
Root – Left – Right (preorder)
Root – Right – Left
Left – Right – Root (postorder)
Right – Left – Root
Left – Root – Right (inorder)
Right – Root – Left
Binary Tree Traversals
Data Structures: A Pseudocode Approach with C, Second Edition
28
BST Operations
Traversals
Searches
Insertion
Deletion
Data Structures: A Pseudocode Approach with C, Second Edition
29
Data Structures: A Pseudocode Approach with C, Second Edition
30
Data Structures: A Pseudocode Approach with C, Second Edition
31
Data Structures: A Pseudocode Approach with C, Second Edition
32
Data Structures: A Pseudocode Approach with C, Second Edition
33
Search: 20
Data Structures: A Pseudocode Approach with C, Second Edition
34
Search: 20
20 < 23 go left
Data Structures: A Pseudocode Approach with C, Second Edition
35
Search: 20
20 > 18 go right
Data Structures: A Pseudocode Approach with C, Second Edition
36
Search: 20
20 equal to 20 found!
Data Structures: A Pseudocode Approach with C, Second Edition
37
Search: 30
Data Structures: A Pseudocode Approach with C, Second Edition
38
Search: 30
30 > 23 go right
Data Structures: A Pseudocode Approach with C, Second Edition
39
Search: 30
30 < 44 go left
Data Structures: A Pseudocode Approach with C, Second Edition
40
Search: 30
30 < 35 go left:
STOP – not found!
41
STRUCTURE CHART: Recursive searchBST
searchBST
searchBST
searchBST
(+)
Data Structures: A Pseudocode Approach with C, Second Edition
42
BST Operations
Traversals
Searches
Insertion
Deletion
Data Structures: A Pseudocode Approach with C, Second Edition
43
44
algorithm insertBST( root, newNode )
Inserts a new node into a BST
Pre : root – pointer to the root of a BST
newNode – the address of the node to be inserted
Post: new node inserted into the tree
Return: nothing
Insert BST – iterative approach
45
algorithm insertBST( root, newNode )
if( root is NULL )
root = newNode
else
pWalk = root
loop( pWalk NOT NULL )
parent = pWalk
if( newNode->data.key < pWalk->data.key )
pWalk = pWalk->left
else
pWalk = pWalk->right
end if
end loop
if( newNode->data.key < parent->data.key )
parent->left = new
else
parent->right = new
end if
end if
return
end insertBST
46
19
root
19
root
Insert BST – iterative approach
47
parent
pWalk
23
18
root
20
12
19
19 < 23 go left
Insert BST – iterative approach
48
parent
pWalk
23
18
root
20
12
19
19 < 23 go left
Insert BST – iterative approach
49
parent
pWalk
23
18
root
20
12
19
19 > 18 go right
Insert BST – iterative approach
50
parent
pWalk
23
18
root
20
12
19
19 > 18 go right
Insert BST – iterative approach
51
pWalk
23
18
root
20
12
19
19 < 20 go left
parent
Insert BST – iterative approach
52
pWalk
23
18
root
20
12
19
19 < 20 go left
parent
Insert BST – iterative approach
53
pWalk
23
18
root
20
12
19
19 < 20 go left
parent
NULL
Insert BST – iterative approach
54
algorithm insertBST( root, newNode )
if( root is NULL )
root = newNode
else
pWalk = root
loop( pWalk NOT NULL )
parent = pWalk
if( newNode->data.key < pWalk->data.key )
pWalk = pWalk->left
else
pWalk = pWalk->right
end if
end loop
if( newNode->data.key < parent->data.key )
parent->left = new
else
parent->right = new
end if
end if
return
end insertBST
55
pWalk
23
18
root
20
12
19
19 < 20
parent
Insert BST – iterative approach
56
Insert BST – recursive approach
algorithm addBST( root, newNode )
if( root is NULL )
root = newNode
else
if( newNode->data.key < root->data.key )
addBst( root->left, newNode )
else
addBst( root->right, newNode )
end if
end if
return
end addBST
57
20
30
root
50
60
root
60 > 20 go right
Insert BST – recursive approach
58
20
30
root
50
root
60 > 30 go right
root
60
Insert BST – recursive approach
59
20
30
root
50
root
60 > 50 go right
root
root
60
Insert BST – recursive approach
60
20
30
root
50
root
root
root
60
root
NULL
Insert BST – recursive approach
61
algorithm addBST( ref root
val new
if( root is NULL )
root = new
else
if( new->data.key < root->data.key )
addBst( root->left, new )
else
addBst( root->right, new )
return
end addBST
Insert BST – recursive approach
62
20
30
root
50
root
root
root
60
root
Insert BST – recursive approach
63
STRUCTURE CHART: Recursive addBST
addBST
addBST
addBST
(+)
64
Create a BST using the following data entered as a sequential set:
14, 23, 7, 10, 33, 56, 80, 66, 70
65
readData
insertBST
buildNode
buildBST
66
14, 23, 7, 10, 33, 56, 80, 66, 70
14
67
14, 23, 7, 10, 33, 56, 80, 66, 70
14
23
68
14, 23, 7, 10, 33, 56, 80, 66, 70
14
23
7
69
14, 23, 7, 10, 33, 56, 80, 66, 70
14
23
7
10
70
14, 23, 7, 10, 33, 56, 80, 66, 70
14
23
7
10
33
71
14, 23, 7, 10, 33, 56, 80, 66, 70
14
23
7
10
33
56
72
14, 23, 7, 10, 33, 56, 80, 66, 70
14
23
7
10
33
56
80
73
14, 23, 7, 10, 33, 56, 80, 66, 70
14
23
7
10
33
56
80
66
74
14, 23, 7, 10, 33, 56, 80, 66, 70
14
23
7
10
33
56
80
66
70
Data Structures: A Pseudocode Approach with C, Second Edition
75
The BST below was created starting with a null tree and entering data from the keyboard. In what sequence were the data entered?
Figure 8-28
76
(A): 25, 28, 27, 35, 45
(B): 25, 28, 35, 27, 45
(C): 25, 28, 35, 45, 27
Data Structures: A Pseudocode Approach with C, Second Edition
77
BST Operations
Traversals
Searches
Insertion
Deletion
78
Delete BST
Delete a node that has no children (leaf).
Delete a node that has one child (leaf-like).
Delete a node that has two children.
79
Delete a node that has two children:
1. Find the data to be deleted.
2. In the left subtree of the located node, find the largest
3. Replace the data to be deleted with the largest.
4. Remove the largest (which is a leaf or a leaf-like node).
Data Structures: A Pseudocode Approach with C, Second Edition
80
Delete 60.
Figure 8-30
Data Structures: A Pseudocode Approach with C, Second Edition
81
1. Find the data to be deleted.
Data to be deleted
Data Structures: A Pseudocode Approach with C, Second Edition
82
2. In the left subtree of the located node, find the largest
Data to be deleted
Largest in the left subtree
Data Structures: A Pseudocode Approach with C, Second Edition
83
3. Move its data (55 ) into the node to be deleted (60).
Largest in its left subtree
55
55
Data Structures: A Pseudocode Approach with C, Second Edition
84
4. Remove the largest from the left subtree.
Largest in its left subtree
55
Data Structures: A Pseudocode Approach with C, Second Edition
85
55
86
Delete a node that has two children:
1. Find the data to be deleted.
2. In the right subtree of the located node, find the smallest
3. Replace the data to be deleted with the largest.
4. Remove the largest (which is a leaf or a leaf-like node).
Data Structures: A Pseudocode Approach with C, Second Edition
87
Delete 70.
78
Data Structures: A Pseudocode Approach with C, Second Edition
88
Data to be deleted
78
Smallest in its right subtree
Data Structures: A Pseudocode Approach with C, Second Edition
89
78
Smallest in its right subtree
75
75
Data Structures: A Pseudocode Approach with C, Second Edition
90
75
78
Data Structures: A Pseudocode Approach with C, Second Edition
91
Delete a node with two children:
Find largest in the left subtree, or
smallest in the right subtree;
Copy its data over the data to be deleted, then
Remove largest/smallest.
Prove that either of these moves will preserve the integrity of
the BST.
Data Structures: A Pseudocode Approach with C, Second Edition
92
Data Structures: A Pseudocode Approach with C, Second Edition
93
(continued)
Data Structures: A Pseudocode Approach with C, Second Edition
94
/docProps/thumbnail.jpeg