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
p r i v a t e Node
}
}
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
p r i v a t e Node
}
p r i v a t e Node
}
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
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
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
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
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
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
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
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
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