CS计算机代考程序代写 data structure c# algorithm INN701 Lecture 3

INN701 Lecture 3

Queensland University of Technology
CRICOS No. 00213J

CAB301 Algorithms and Complexity

Lecture 5 – Binary tree, binary search tree
and algorithms

Maolin Tang
School of Computer Science

Queensland University of Technology

CRICOS No. 00213J

a university for the worldreal R 2

Aims of this lecture

• This lecture introduces tree data structures and algorithms
– Binary tree and algorithms
– Binary search tree and algorithms

CRICOS No. 00213J

a university for the worldreal R

References

• A. Levitin. Introduction to the Design and Analysis of Algorithms.
Addison-Wesley, third edition, 2012. Sections 1.4, 5.3

• Thomas H. Cormen etc. Introduction to Algorithms. MIT Press,
Third Edition, 2009. Chapter 12.

3

CRICOS No. 00213J

a university for the worldreal R

Binary tree

 A binary tree is a non-linear data structure in which each node
has at most two children.

4

CRICOS No. 00213J

a university for the worldreal R

Binary tree

 A binary tree is a set T of nodes
such that either
– T is empty, or
– T is partitioned into three

disjoint subsets:
• A single node root, the root
• Two possibly empty sets

that are binary trees, called
left and right subtrees of
root.

5

CRICOS No. 00213J

a university for the worldreal R

item lchild rchild

Binary tree implementation

lchild: left child pointer
rchild: right child pointer

The structure of a binary tree node (BTNode):

6

CRICOS No. 00213J

a university for the worldreal R

Binary tree implementation

^  null

A

D ^ ^

C ^

G ^

B

E ^ ^

H ^ ^

F ^

root

7

CRICOS No. 00213J

a university for the worldreal R

Traversal of a binary tree

• Often one wishes to visit each of the nodes in a binary tree and
examine the value there.

• There are three common orders in which the nodes can be
visited, and each has useful properties that are exploited in
algorithms based on binary trees.

– Pre-order
– In-order
– Post-order

8

CRICOS No. 00213J

a university for the worldreal R

Pre-order traversal

• Pre-order traversal is recursively
defined as follows:

– visit the root first, then
– traverse the left subtree in

pre-order, and then
– traverse the right subtree in

pre-order.

A B D E C F G H

 

9

CRICOS No. 00213J

a university for the worldreal R

Pre-order traversal algorithm

ALGORITHM Pre-order (root)
if root ≠ null

visit root.item
Pre-order(root.lchild)
Pre-order(root.rchild)

10

CRICOS No. 00213J

a university for the worldreal R

In-order traversal

• In-order traversal is recursively
defined as follows:

– traverse the left subtree in in-
order, then

– visit the root, and then
– traverse the right subtree in

in-order.

D B E A C G H F

11

CRICOS No. 00213J

a university for the worldreal R

In-order traversal algorithm

ALGORITHM In-order (root)
if root ≠ null

In-order(root.lchild)
visit root.item
In-order(root.rchild)

12

CRICOS No. 00213J

a university for the worldreal R

Post-order traversal

• Post-order traversal is
recursively defined as follows:

– traverse the left subtree
in post-order, and then

– traverse the right subtree
in post-order, and then

– visit the root.

D E B H G F C A

 

13

CRICOS No. 00213J

a university for the worldreal R

Post-order traversal algorithm

ALGORITHM Post-order (root)
if root ≠ null

Post-order(root.lchild)
Post-order(root.rchild)
visit root.item

14

CRICOS No. 00213J

a university for the worldreal R

Efficiency of the binary tree traversal
algorithms

• Pre-order: O(n), where n is the number of nodes in the binary tree
• In-order: O(n), where n is the number of nodes in the binary tree
• Post-order: O(n), where n is the number of nodes in the binary tree

15

CRICOS No. 00213J

a university for the worldreal R

Binary search tree
 A binary search tree is a binary tree, where every node’s left subtree

contains values that are less than or equal to the node’s value,
every node’s right subtree contains values that are greater than or
equal to the node’s value, and both left and right binary trees and
binary search trees.

binary search tree

60

50 70

30 65
80

75

55

60

50 70

30 65
75

80

55

not a binary search tree

16

CRICOS No. 00213J

a university for the worldreal R

Search

 Searching a binary search tree for a specific item is a recursive
process due to the property of binary search trees.

 We begin by examining the root.
– If the given item equals to the item at the root, return true;
– If it is less than the item at the root, we recursively search

the left subtree in the same manner.
– Similarly, if it is greater than the item at the root, we

recursively search the right subtree in the same manner.

17

CRICOS No. 00213J

a university for the worldreal R

Search

60

50 70

30 65
80

75

55

Search for 80

18

CRICOS No. 00213J

a university for the worldreal R

Search

60

50 70

30 65
80

75

55

Search for 79

19

CRICOS No. 00213J

a university for the worldreal R

Search algorithm

ALGORITHM Search (K, root)
if root ≠ null

if root.item = K
return true

else
if root.item < K return Search(K, root.rchild) else return Search(K, root.lchild) else return false 20 CRICOS No. 00213J a university for the worldreal R Insert 60 50 70 30 65 80 75 55 Insert 45    45 21 CRICOS No. 00213J a university for the worldreal R Insert algorithm ALGORITHM Insert (K, root) if root = null ptr ← new BTNode; ptr.item ← K; root ← ptr else if root.item > K
if root.lchild = null

ptr ← new BTNode; ptr.item ← K; root.lchild ← ptr
else Insert(K, root.lchild)

else
if root.rchild = null

ptr ← new BTNode; ptr.item ← K; root.rchild ← ptr
else Insert(K, root.rchild)

22

CRICOS No. 00213J

a university for the worldreal R

Delete

 There are three cases that need to be considered:
– the node to be deleted is a leaf
– the node to be deleted has only one child
– the node to be deleted has two children

23

CRICOS No. 00213J

a university for the worldreal R

Delete

parent

ptr

parent

 Case 1: the node to be deleted is a leaf

24

parent

ptr

parent

CRICOS No. 00213J

a university for the worldreal R

Delete

 Case 2: the node to be deleted has only one child

25

parent

ptr

parent

c

c

CRICOS No. 00213J

a university for the worldreal R

Delete

ptr

The right-most
node in the left
subtree of ptr

 Case 3: the node to be deleted has two children

Transform it into the problem of deleting a
node that has only one child or deleting a leaf:
1. find the right-most node in the left subtree of ptr;
2. copy the item of the right-most node to ptr
3. delete the right-most node

26

CRICOS No. 00213J

a university for the worldreal R

Delete algorithm

ALGORITHM Delete(K, root)
// delete a node whose key is K from a binary search tree
// root is the pointer of the binary search tree
// search for node where K is stored and its parent

ptr ← root
parent ← null // parent of ptr
while ptr ≠ null and ptr.item ≠ K do

parent ← ptr
if ptr.item > K // move to the left subtree of ptr

ptr ← ptr.lchild
else //move to the right subtree of ptr

ptr ← ptr.rchild

27

CRICOS No. 00213J

a university for the worldreal R

if ptr ≠ null // if the search was successful
if ptr.lchild ≠ null and ptr.rchild ≠ null //ptr has two children

// find the right-most node in left subtree of ptr
if ptr.lchild.rchild = null // a special case: the right subtree

// of ptr.lchild is empty
ptr.item ← ptr.lchild.item
ptr.lchild ← ptr.lchild.lchild

else
p ← ptr.lchild
pp ← ptr //parent of p
while p.rchild ≠ null do

pp ← p; p ← p.rchild
ptr.item ← p.item // copy the item at p to ptr
pp.rchild ← p.lchild

28

CRICOS No. 00213J

a university for the worldreal R

else // cases 1 & 2: item has no or only one child
if ptr.lchild ≠ null

c ← ptr.lchild
else

c ← ptr.rchild
// remove node ptr
if ptr = root //need to change root

root ← c
else

if ptr = parent.lchild
parent.lchild ← c

else
parent.rchild ← c

29

CRICOS No. 00213J

a university for the worldreal R

Demo – a binary search tree ADT in C#

• There are three files used in this demo:
– IBSTree.cs – The interface of the binary search tree ADT
– BSTree.cs – The implementation of the binary search tree ADT
– TestBSTreeADT.cs – A program that tests the operations

defined and implemented in the binary search tree ADT. It can
be considered as an application of the binary search tree ADT.

30

CRICOS No. 00213J

a university for the worldreal R

Demo – a binary search tree ADT in C#

31

CAB301 Algorithms and Complexity��Lecture 5 – Binary tree, binary search tree and algorithms
Aims of this lecture
References
Binary tree
Binary tree
Binary tree implementation
Binary tree implementation
Traversal of a binary tree
Pre-order traversal
Pre-order traversal algorithm
In-order traversal
In-order traversal algorithm
Post-order traversal
Post-order traversal algorithm
Efficiency of the binary tree traversal algorithms
Binary search tree
Search
Search
Search
Search algorithm
Insert
Insert algorithm
Delete
Delete
Delete
Delete
Delete algorithm
Slide Number 28
Slide Number 29
Demo – a binary search tree ADT in C#
Demo – a binary search tree ADT in C#