CS计算机代考程序代写 prolog data structure Java file system algorithm ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II
Binary search tree: concept

by

Marcel Turcotte

Version March 27, 2020

Preamble

Preamble

Overview

Overview

Binary search tree: concept

We begin with an overview of the applications of trees in computing: to represent
hierarchical data, for compression, and efficient access to elements. We examine the
linked implementation of trees. We pay particular attention to binary search trees.

General objective:
This week you will be able to design and modify computer programs based on the
concept of a binary search tree.

1 44

Preamble

Learning objectives

Learning objectives

Name applications of binary search trees.
Describe the essential properties of binary search trees.

Readings:
Pages 257-268 and 282-296 of E. Koffman and P. Wolfgang.

2 44

Preamble

Plan

Plan

1 Preamble

2 Theory

3 Implementation

4 Methods

5 Traversing a tree

6 Prologue

3 44

Theory

Definition
A binary tree is a hierarchical data structure such that each node stores one value and
has at most two children, called left and right.

5

8

15

9 29

11

4 44

Theory

Applications

Applications (general trees)

Represent hierarchical information such as hierarchical file systems (HFS)
(directories and subdirectories), programs (parse tree);
Huffman trees are used to compress information (files);
The binary tree is an efficient data structure for implementing abstract data types
such as heaps, priority queues, associative structures and sets.

5 44

Source: [1] Figure 6.5.

Theory

Definitions

Definitions

5

8

15

9 29

11

All nodes have only one parent, except for one node that has no parent, and is
called the root (this is the node at the very top of the diagram);
Each node has either 0, 1 or 2 children;
The childless nodes are the leaves of the tree (or outer nodes);
The links between the nodes are the branches of the tree.

7 44

Definitions

5

8

15

9 29

11

A node and its descendants are a sub-tree;
The size of a tree is the number of nodes in the tree. An empty tree has a size 0;
Since we will only deal with binary trees, I will sometimes use the term tree to refer
to a binary tree.

8 44

Definitions

We can give a recursive definition:
A binary tree is empty, or;
A binary tree consists of a value and two subtrees (left and right).

9 44

Definitions

The node depth represents the number of links you have to follow from the root in order
to access that node. The root is the most accessible node.

5

8

15

9 29

11

What’s the depth of the root? The root is always at depth 0.

10 44

Definitions

The node depth represents the number of links you have to follow from the root in order
to access that node. The root is the most accessible node.

5

8

15

9 29

11

The depth of a tree is the maximum depth of a node in the tree.

11 44

Discussion
All the trees shown here have a property in common. What is it?

5

8

15

12 292 7

1 4 5013

12 44

Definition

5

8

15

12 292 7

1 4 5013

A binary search tree is a binary tree whose nodes satisfy the following properties:
all the nodes of its left subtree have smaller values than this node (or the left
subtree is empty);
all the nodes of its right subtree have greater values than this node (or this subtree
is empty).

Corollary: the values are unique.

13 44

Implementation

Implementation

How are we going to implement this class?
Indeed, we’ll use a “nested” and “static” class, Node.
What are its instance variables?

The instance variables are: value, left and right;
What is the type of these variables?

value is of type Comparable, left and right are of type Node.

14 44

Implementation

A static nested class to save a value and create the structure of the tree.
pub l i c c l a s s BinarySearchTree > {

p r i v a t e s t a t i c c l a s s Node {
p r i v a t e T v a l u e ;
p r i v a t e Node l e f t ;
p r i v a t e Node r i g h t ;

}

}

15 44

Implementation

What are the instance variables of the BinarySearchTree?
pub l i c c l a s s BinarySearchTree > {

p r i v a t e s t a t i c c l a s s Node {
p r i v a t e T v a l u e ;
p r i v a t e Node l e f t ;
p r i v a t e Node r i g h t ;

}

p r i v a t e Node r o o t ;
}

16 44

Memory diagram

8

root
Node

BinarySearchTree

rightleft
value

Comparable

17 44

8

9 15

115

root Node

BinarySearchTree

Representations
8

9 15

115

root

5

8

11

9 15

19 44

Observations
A leaf is a node such that its two descendants are both null.
The variable root can be null, so the tree is empty and of size 0.
For the sake of simplicity, I will often use the more abstract representation on the
right.

8

9 15

115

root

5

8

11

9 15

20 44

Methods

Methods

contains

boolean contains(E element)

5

8

11

9 15

1. Empty tree? element is not found;
2. The local root contains element? element is found; Otherwise? Where are we

looking for?
3. If element is smaller than the value stored in the current node? Look for element in

the left subtree;
4. Otherwise (element is necessarily greater than the value in the current node.)? Look

for element in the right subtree.

21 44

boolean contains(E element)

5

8

11

9 15

Exercises: apply the algorithm to find the values 8, 9 and 7 in the tree above.

22 44

public boolean contains(E element)

The presentation suggests a recursive algorithm.
What will be the signature of the method?
pub l i c boolean c o n t a i n s (E e lement ) {

i f ( e l ement == nu l l ) {
throw new N u l l P o i n t e r E x c e p t i o n ( ) ;

}
re tu rn c o n t a i n s ( root , e l ement ) ;

}

Like the recursive processing of linked lists, our methods will have two parts, a
public part, and a private part whose signature has a parameter of type Node.

23 44

boolean contains(Node current, E
element)

Base case:
i f ( c u r r e n t == nu l l ) {

r e s u l t = f a l s e ;
}

but also
i f ( e l ement . e q u a l s ( c u r r e n t . v a l u e ) ) {

r e s u l t = t rue ;
}

24 44

boolean contains(Node current, E
element)

General case: . Search left or right (recursively).
i f ( e l ement . compareTo ( c u r r e n t . v a l u e ) < 0) { r e s u l t = c o n t a i n s ( c u r r e n t . l e f t , e l ement ) ; } e l s e { r e s u l t = c o n t a i n s ( c u r r e n t . r i g h t , e l ement ) ; } 25 44 p r i v a t e boolean c o n t a i n s ( Node c u r r e n t , E e l ement ) {

boolean r e s u l t ;

i f ( c u r r e n t == nu l l ) {
r e s u l t = f a l s e ;

} e l s e {
i n t t e s t = e lement . compareTo ( c u r r e n t . v a l u e ) ;
i f ( t e s t == 0) {

r e s u l t = t rue ;
} e l s e i f ( t e s t < 0) { r e s u l t = c o n t a i n s ( c u r r e n t . l e f t , e l ement ) ; } e l s e { r e s u l t = c o n t a i n s ( c u r r e n t . r i g h t , e l ement ) ; } } re tu rn r e s u l t ; } public boolean contains(E element) (take 2) Is the method boolean contains(E element) necessarily recursive? No. Develop a strategy. 1. Use a local variable current of type Node; 2. Initialize the variable to designate the root node of the tree; 3. If current is null then the value is not found, stop; 4. If current.value is the value sought, stop; 5. If the sought value is smaller than current = current.left, goto 3; 6. Else current = current.right, goto 3. 27 44 public boolean contains(E element) (take 2) pub l i c boolean c o n t a i n s 2 (E e lement ) { boolean found = f a l s e ; Node c u r r e n t = r o o t ;
whi le ( ! found && c u r r e n t != nu l l ) {

i n t t e s t = e lement . compareTo ( c u r r e n t . v a l u e ) ;
i f ( t e s t == 0) {

found = t rue ;
} e l s e i f ( t e s t < 0) { c u r r e n t = c u r r e n t . l e f t ; } e l s e { c u r r e n t = c u r r e n t . r i g h t ; } } re tu rn found ; } 28 44 Traversing a tree Traversing a tree Sometimes one has to traverse the tree in order to visit all of its nodes. When visiting a node, you perform certain operations on the node. Pre-order traversal: visit the root, traverse the left subtree, traverse the right subtree; In-order (infix, symmetrical) traversal: traverse the left subtree, visit the root, traverse the right subtree; Post-order (suffix) traversal: traverse the left subtree, traverse the right subtree, visit the root; 29 44 Exercises The simplest operation is to display the value stored in the node. 5 8 15 12 292 7 Give the result displayed for each strategy, pre-order, in-order and post-order. What strategy is displaying the data in ascending order? 30 44 Traversing a tree Pre-order: root, left, right; In-order: left, root, right; Post-order: left, right, root. 31 44 Traversing a tree p r i v a t e vo id v i s i t ( Node c u r r e n t ) {
System . out . p r i n t ( c u r r e n t . v a l u e ) ;

}

pub l i c vo id preOrde r ( ) {
p reOrde r ( r o o t ) ;

}

pub l i c vo id i nOrde r ( ) {
i nOrde r ( r o o t ) ;

}

pub l i c vo id pos tOrde r ( ) {
pos tOrde r ( r o o t ) ;

}

32 44

Traversing a tree

Pre-order

Pre-order

p r i v a t e vo id preOrde r ( Node c u r r e n t ) {

i f ( c u r r e n t != nu l l ) {

v i s i t ( c u r r e n t ) ;
p r eOrde r ( c u r r e n t . l e f t ) ;
p r eOrde r ( c u r r e n t . r i g h t ) ;

}

}

33 44

5

8

15

9 29

11

Traversing a tree

In-order

Infixe

p r i v a t e vo id i nOrde r ( Node c u r r e n t ) {

i f ( c u r r e n t != nu l l ) {

i nOrde r ( c u r r e n t . l e f t ) ;
v i s i t ( c u r r e n t ) ;
i nOrde r ( c u r r e n t . r i g h t ) ;

}

}

35 44

5

8

15

9 29

11

Traversing a tree

Post-order

Post-order

p r i v a t e vo id pos tOrde r ( Node c u r r e n t ) {

i f ( c u r r e n t != nu l l ) {

pos tOrde r ( c u r r e n t . l e f t ) ;
pos tOrde r ( c u r r e n t . r i g h t ) ;
v i s i t ( c u r r e n t ) ;

}

}

37 44

5

8

15

9 29

11

8

9 15

115

root
preOrder()

preOrder( current )

visit( current );
preOrder( current )

visit( current );

preOrder( current )

preOrder( current )

preOrder( current )
visit( current );

preOrder( current )
visit( current );

preOrder( current )

preOrder( current )

preOrder( current )
visit( current );

preOrder( current )

preOrder( current )

Observations

Methods that follow only one path, from the root to a leaf, for example, are easy to
implement without recursive calls, see contains;
Methods that visit several subtrees are often more easily implemented using
recursivity.

40 44

Prologue

Summary

A binary search tree is a binary tree where each node satisfies the following two
properties:

All the nodes in its left subtree have smaller values than this node’s or its left subtree is
empty;
All the nodes of its right subtree have greater values than this node or its right subtree
is empty.

Implemented using linked elements.

41 44

Next module

Binary search trees : removal of an element.

42 44

References I

E. B. Koffman and Wolfgang P. A. T.
Data Structures: Abstraction and Design Using Java.
John Wiley & Sons, 3e edition, 2016.

43 44

Marcel Turcotte
Marcel.

School of Electrical Engineering and Computer Science (EECS)
University of Ottawa

44 / 44

Marcel.

Preamble
Overview
Learning objectives
Plan

Theory
Applications
Definitions

Implementation
Methods
contains

Traversing a tree
Pre-order
In-order
Post-order

Prologue