Transcript tree

GRIFFITH
COLLEGE
DUBLIN
Data Structures, Algorithms &
Complexity
Tree Algorithms
Lecture 8
1
Introduction




Trees are a mathematical abstraction that play a central role in
the design and analysis of algorithms
We use trees to describe dynamic properties of algorithms
We build and use explicit data structures that are concrete
realisations of trees
Definition of Trees
 Tree
 Rooted tree
 Ordered tree
 M-ary tree and binary tree
Lecture 8
2
Tree






A tree is a non-empty collection of vertices and edges that
satisfies certain requirements.
A vertex (or node) is a simple object that can have a name and
can carry other associated information
An edge is a connection between two vertices
A path in a tree is a list of distinct vertices in which successive
vertices are connected by edges in the tree
The defining property of a tree is that there is precisely one
path connecting any two nodes.
A disjoint set of trees is called a forest
Lecture 8
3
Rooted Tree






A Rooted Tree is one where we designate one node as the
root
In computer science we normally reserve the term tree to refer
to rooted trees. The more general structure is a free tree
In a rooted tree, any node is the root of a subtree consisting of
it and the nodes below it
There is exactly one path between the root and each of the
other nodes in the tree
Each node except the root has exactly one node above it in the
tree, called its parent, and we extend the family analogy
talking of children, siblings, or grandparents
Nodes with no children are leaves or terminal nodes
Lecture 8
4
Ordered Tree





An ordered tree is a rooted tree in which the order of the
children at every node is specified.
If each node must have a specific number of children appearing
in a specific order, then we have an M-ary tree
The simplest type of M-ary tree is the binary tree
A binary tree is an ordered tree consisting of nodes that can
have at most two children
As with any Abstract Data Structure we can implement a binary
tree in a number of ways, using arrays, strings, or structures
and pointers
Lecture 8
5
Examples of Trees
 A free tree
A rooted binary tree
A forest
Lecture 8
6
Mathematical Properties

Nodes on a tree are internal or external

An internal node is a node in the tree

An external node is a node that could be added to the existing
nodes

A binary tree with N internal nodes has N+1 external nodes

A binary tree with N internal nodes has 2N links

N-1 links to internal nodes and N+1 links to external nodes
internal nodes
external nodes
Lecture 8
7
Terminology




The level of a node in a tree is one higher than the level of
its parent (with the root at level 0)
The height of a tree is the maximum of the levels of the
tree’s nodes
The height of a complete binary tree with N internal nodes
is lg N 
The path length of a tree is the sum of the levels of all the
trees nodes
Lecture 8
8
Tree Traversal



Given a tree we want to process each node in the tree
systematically
For binary trees, we have two links, and we therefore have
three basic orders in which we might visit the nodes:
 Preorder, where we visit the node, then visit the left and
right subtrees
 Inorder, where we visit the left subtree, then visit the node,
then visit the right subtree
 Postorder, where we visit the left and right subtrees, then
visit the node
These can be implemented easily using a recursive
implementation
Lecture 8
9
Pre-Order Traversal
Preorder(T)
if (T <> nil) then
visit(T)
Preorder(left(T))
Preorder(right(T))
endif
endalg

Assuming that ‘visit’ means print and we have the following
tree:
5
3
2

7
5
8
The output of the call Preorder(T) will be,
5
3
2
5
Lecture 8
7
8
10
Post and In order




Changing to Postorder or Inorder simply involves
changing the order of the calls
Preorder visits the root before calling the function for
either subtree
Postorder visits the root after calling the function for
the subtrees
Inorder calls the function for the left subtree, then
visits the root, and then calls the function for the right
subtree
Lecture 8
11
Postorder and Inorder Algorithms
Postorder(T)
Inorder(T)
if (T <> nil) then
if (T <> nil) then
Postorder(left(T))
Inorder(left(T))
Postorder(right(T))
visit(T)
visit(T)
Inorder(right(T))
endif
endif
endalg
endalg
Lecture 8
12
Traversal Example

Given the following tree above the traversals will give output as
shown
E
D
B
A
H
F
C
G

Preorder :
E D B A C H F G

Inorder :
A B C D E F G H

Postorder:
A C B D G F H E
Lecture 8
13
Binary Search Tree



A binary search tree is a binary tree in which every item in the
left subtree is less than or equal to the item at the root, and
every item in the right subtree is greater than the item in the
root.
5
3
7
2
5
8
An inorder traversal of a binary search tree will print the nodes
in sorted order
The most common operation performed on a binary search tree
is searching for a key.
Lecture 8
14
Binary Search Tree Algorithms

Let x be a reference to the root of the tree, and k be
the key we are looking for
Tree-Search(x, k)
if x = nil or k = key[x] then
return x
endif
if k < key[x] then
return Tree-Search( left[x], k)
else
return Tree-Search( right[x], k)
endif
endalg
Lecture 8
15
Binary Search Tree Algorithms

Tree Minimum and Maximum are simple procedures
on a binary search tree
Tree-Minimum(x)
while left[x] <> nil
x = left[x]
endwhile
return x
endalg
Tree-Maximum(x)
while right[x] <> nil
x = right[x]
endwhile
return x
endalg
Lecture 8
16
Summary







Trees are a mathematical abstraction that play a central role in
the design and analysis of algorithms
We build and use explicit data structures that are concrete
realisations of trees
Trees can be free, rooted, ordered or M-ary
Trees have height, level and path length, all of which are
defined
Tree Traversal is an important operation
For a binary tree we looked a preorder, postorder and inorder
traversal
Introduced a binary search tree and some simple algorithms.
Will return to this.
Lecture 8
17