程序代写代做代考 Excel algorithm data structure PowerPoint Presentation

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