Lecture 7
Basic concepts of Tree
Binary Trees and BST
2
Main content of last six lectures
§ Complexity analysis
§ Big-O notation: measurement of computational
complexity – consider dominating part only and ignore
constant differences.
§ Formal definition of Big-O: f(n) is in O(g(n)) if there is
a constant c and a constant N0 such that f(n)<=cg(n)
when n>=N0.
§ Worst case complexity: by default
§ Benchmarks for complexity measurement:
O(1) < O(log n) < O(n) < O(nlog n) < O(n2) <…< O(2n)
3
Main contents of last six lectures
§ Linear data structures
§ Dynamic array and linked list
§ Stack and queue
§ Priority queue
§ Use of STL: vector, list, stack, queue and priority queue
n Hashed technique: makes search in constant time (O(1)).
n Hashing function: maps a key into an address
n Collision resolution: to avoid more than one items in one address
Ø Closed hashing: all items stored in one data structure (array).
Ø Open hashing: attach a linked list to each address
4
Search algorithms
DFS_Algorithm { Depth-first search: stack
tracking = {start node}; Breadth-first search: queue
visitedList = {}; //vector or list Best-first search: priority queue
while (tracking is not empty) {
Pop a node s from tracking;
Push s into visitedList;
if (s is a goal) {
return true;
} else {
for (each next node s’ of s)
if (s’ is in vistedList) continue;
else Push s’ into tracking;
}
}
return false;
}
5
Main content of last six lecture
§ Algorithms
Under your
§ Sequential search
control
§ Binary search
§ Hashing
§ Recursive algorithms
Major focus of the first six-weeks
Implementation
Learn to use simple structures (STL) to solve
simple but real-world problems
6
Highlight of the second half of the semester
• Data structures
• Trees: General tree, binary tree, binary search tree, heap,
balanced tree, AVL-tree, m-way tree and B-tree
• Graphs: traversal algorithms, spanning tree and shortest paths
• Algorithms:
• Sorting: Shell sort, heap sort and quick sort
Major focus of the second six-weeks
Technologies
Learn highly sophisticated technologies to solve
complicated problems
Reading book
is needed
Main content of this lecture
§ Basic tree concepts
§ Binary trees
§ Traversal strategies for binary trees
§ Convert a general tree into a binary tree
§ Binary Search Tree
§ Complexity of operations in binary search trees
8
Motivation of using tree structures
§ Binary search vs sequential search – how much efficiency
we gain?
n 10 100 1000 10,000 100,000 1,000,000 1,000,000,000
log2n 3 7 10 13 17 20 30
§ How to extend the idea of “dropping half” or “divide and
conquer” to more than binary searching?
Telescope view
9
Motivation of using tree structures
§ Binary search vs sequential search – how much efficiency
we gain?
n 10 100 1000 10,000 100,000 1,000,000 1,000,000,000
log2n 3 7 10 13 17 20 30
§ How to extend the idea of “dropping half” or “divide and
conquer” to more than binary searching?
outdegree is 3
leaves
indegree is 1
A tree consists of a set of
elements, called nodes
and a set of directed
lines, called branches.
§ The number of
branches associated
with a node is the
degree of the node
§ Indegree: directed
toward the node
nodes § Outdegree: directed
branches away from the node
§ Root: indegree is zero
root § Leaf: outdegree is zero
Basic Concepts of Trees
§ Family relationship
§ parent: a node having successor nodes
§ child: a node with predecessors
§ siblings: two or more nodes with the same parent
§ ancestors and descendants
§ A path is a sequence of nodes in
which each node is adjacent to
the next one.
§ Forest: A set of trees in parallel.
Basic Concepts of Trees…
§ Level of a node: its distance from the node to the root.
§ The level of the root is 0;
§ The level of other nodes are always one greater than
its parent Root
Basic Concepts of Trees…
§ Height of a tree: the level of the leaf in the longest path
from the root plus 1.
Some books do not plus 1
§ the height of an empty tree is 0.
Root
the height of
the tree is 3
Recursive definition of trees
§ A tree is a collection of objects called nodes and is defined
recursively as follows:
§ An empty set is a tree, called empty tree
§ If T1, …,Tn are trees and R is a node, then the set T
containing R and the n trees is a tree. Within the tree, R is
called the root of T and the Ti (i=1,…,n) are called subtrees.
R
15
Recursive definition of trees
A
A E B E F
B F H
C D C D G H I
G I
set representation of a tree
T = {A, {B, {C}, {D}}, {E}, {F, {H}, {G}, {I}}}
16
Binary Trees
§ Binary trees are trees where the maximum outdegree
of any node is two, i.e., can’t have more than two
subtrees (designated as the left subtree and the right
subtree)
§ Binary tree node structure What are the differences
between a binary tree
tempate <class Type> and a linked list?
struct binaryTreeNode {
Type data;
binaryTreeNode<Type> *llink;
binaryTreeNode<Type> *rlink; data
};
data data
17
Why use binary trees?
§ Major data structure operations: search, insertion,
deletion.
§ Ordered array: fast in search (binary search), slow in
insertion and deletion (shift elements).
§ Linked list: fast in insertion and deletion at ends, slow in
search (no binary search) and random access.
§ Binary tree: can be relatively faster for all operations.
The major point
18
Height of a well-balanced binary tree
Total nodes: n
k = log2n
The height: k
19
Transforming a linked list to a binary tree
2 10 5 7 25
2 10
10 5 5 25
7 25 2 7
2 5 7 10 25
20
Transforming a general tree to a binary tree
A
B
A
C
B C D E
F D
F G H G E
I H
I J K J
K
21
Search and traversal in a tree
§ Breadth-first traversal: proceed level by level
visiting the whole breadth of a level before going
down to the next level.
§ Depth-first traversal: start at the root and explore
as far as possible along each branch before
backtracking.
A Results are A
not unique
B C D B C D
E F G H I E F G H I
22
Depth-First Traversals of Binary Trees
n In the case of binary trees, there are three different
strategies for depth-first search:
n Pre-order (NLR) : Visit the root first, then its left
subtree, and finally right subtree
n In-order (LNR) : Visit the left subtree first, then the
root, and finally its right subtree
n Post-order (LRN) : visit the left subtree first, the right
subtree, and finally the root
23
Binary Tree Traversals…
Pre-order In-order Post-order
24
Binary Tree Traversals…
template<class TYPE>
void preorder(binaryTreeNode<TYPE> *treePtr) {
if (treePtr == NULL) return;
visit(treePtr->data);
preorder(treePtr->llink);
preorder(treePtr->rlink);
}
25
Binary Tree Traversals…
template<class TYPE>
void inorder(binaryTreeNode<TYPE> *treePtr) {
if (treePtr == NULL) return;
inorder(treePtr->llink);
visit(treePtr->data);
inorder(treePtr->rlink);
}
26
Binary Tree Traversals…
template<class TYPE>
void postorder(binaryTreeNode<TYPE> *treePtr) {
if (treePtr == NULL) return;
postorder(treePtr->llink);
postorder(treePtr->rlink);
visit(treePtr->data);
}
27
Binary tree implementation
§ Tree node
§ Binary tree Operations
§ isEmpty()
No insertion and
§ inorderTraversal() deletion
§ preorderTraversal() operations yet
§ postorderTraversal()
§ treeHeight()
Read code: binaryTree.h
28
Binary Search Trees Elements must be comparable,
typically by their keys
n A binary search tree (BST) is a binary tree with its
nodes arranged in such way so as to maintain a special
order: the element stored in the root is greater than any
elements in its left subtree and less than or equal to any
elements in its right subtree. The same ordering applies
to all its subtrees.
10
5 25
2 7
³
You associate a key to your data to make your data comparable
29
Binary Search Trees
§ The key of the data in each node is
§ Larger than the keys in its left subtree
§ Smaller than the keys in its right subtree
78 60
32 60 46 78
89 46 98 28 53 98
28 53 not 32 89
unique
Binary tree Binary search tree
30
Properties of BSTs: Min and Max
§ The smallest (largest) node: always at the left (right) leaf of
its left-subtree (right-subtree)
Type minElement(binaryTreeNode<Type> *&p) {
if (p->llink != NULL)
return minElement(p->llink); more than just
else ordered
return p->data;
}
Type maxElement(binaryTreeNode<Type> *&p) {
if (p->rlink != NULL)
return maxElement(p->rlink);
else
return p->data;
}
31
Properties of BSTs: to order list
nBST traversal: in-order traversal of a BST produces
an ordered list
This is why BST gains
the advantages of both
BST is a ordered arrays and
representation of linked lists
ordered array
Homework:
Create
another
BST with 12 18 20 23 35 44 52
the same
data In-order traversal of BST
32
Binary Search Trees
§ A binary search tree T={R, LT , RT} is a binary tree,
where
§ R is the root of the tree.
§ LT and RT is the left subtree and the right subtree,
respectively, both are binary search trees.
§ The key in the root node is larger than every key in
the left subtree and smaller than or equal to every
key in the right subtree.
33
Operations on binary Search Trees
§ Typical operations performed on a binary search
tree
§ Check if empty
§ Traversal: pre-order, in-order and post-order
§ Find the height of the binary search tree
§ Search the binary search tree for a particular item
§ Insert an item in the binary search tree
§ Delete an item from the binary search tree
Inherited from binary tree ADT
Read code: binarySearchTree.h
34
Search in a BST and its complexity
§ BST search: the same way as binary search (divide and
conquer)
§ Complexity: the time complexity of searching a BST with
n nodes can be of O(log2n) if the tree is well balanced (as
good as binary search in this case).
target = 20
target = 42
Search time is no
more than the
height of the tree
35
BST node insertion
BST Insert
Go left if
smaller than
the root key
and go right if
higher than
the root key
until reach a
leaf. Insert it
as the child of
that leaf.
36
Insertion Complexity
§ Insert a node: the time complexity of inserting a
node into an n nodes BST can be of O(log2n) if
the tree is well balanced (better than ordered
array).
Finding the
position to insert
takes no more
than the height
of the tree
comparisons
42
37
BST node deletion
delete 44
case 1
case 2
38
BST node deletion
delete 18
case 3
delete 23
case 4
39
Complexity of node deletion
§ Delete a node: the time complexity of deleting a node
from an n nodes BST can be of O(log2n) if the tree is well
balanced (better than ordered array).
§ The worst case is that the node to be deleted has two
subtrees, in this case
n find the largest node in the left subtree (or the
smallest node in the right subtree) to replace the
deleted node. The complexity is O(subtree height).
40
Implementation
§ class bSearchTreeType
§ Illustrates basic operations to implement a binary
search tree
§ Function search
§ Function insert (no duplication)
§ Function deleteNote
Read code: BinarySearchTree.h
41
Practice
Insert the numbers in the following sequence: 89, 27, 65, 34, 12, 90, 76, 38
89
27 90
12 65
34 76
38
Delete 65
42
Reading & Homework
§ Read textbook Chapter 11
§ Assignment 1 is due at 5pm in this Friday 19 April
2024. You must submit your source code via
vUWS by the due date.
43
Reading & Homework
§ Assignment 1 demonstration is due in week 9. You
must go to your own registered practical class to
demonstrate your work to us. We will check your
work one by one. If you do not submit, you will
receive NSF. If you have submitted but do not
demonstrate your code during your practical
session, you will receive zero marks for this
assignment. If you demonstrate your code but fail
to pass, you have one more week to improve your
code (maximal 50% marks in this case).
