Binary Trees
Data Structures and Abstractions
Trees and Tree Searching
Lecture 28
*
Trees
Trees are ADS where every Node has unidirectional links to one or more nodes underneath it. [1]
An m-tree is a node with 0:m links and 1:m-1 pieces of data in each node. For example a 4-tree (quadtree or 4-way tree) might look something like this:
[1]
Compare this idea of nodes with the one used in linked lists.
There can be a link back from the child to the parent – see section on “Representing rooted trees” and the chapter on “Binary Search Trees” in our reference book, Introduction to Algorithms. The lecture notes and text do not show the link back to parent as a simplification.
There should be no closed loops in the way edges and nodes are connected.
If there are n nodes, there are n-1 edges.
*
Tree Definitions
The top node is called the root. [1]
Any node that is not the root node is a child of some parent.
Any node that has one or more children is a parent.
Nodes connected to same parent are called siblings. [2]
Any node that has no children is called a leaf.
Any part of the tree smaller than the whole is called a subtree.
[1] In this unit we are interested in rooted trees. Rooted trees are trees where one node is special and can serve as the starting point of the tree. Unrooted trees are also called free trees.
[2] The siblings are the same distance away from the parent. Connection can be two-way: parent to child, and child back to parent.
*
Tree Use [1]
The back-ends of databases.
Data stores that are not databases.
Problem solving.
Game playing.
Graphics and virtual reality: for tracking line of sight as well as storing screen objects.
Graph theory (e.g. path finding).
The algorithm used to insert data into the tree will vary from application to application.
[1] There are other applications in other areas like electrical circuits, organic chemistry, .. Etc.
*
Traversal
Traversing a tree involves going to every node.
This needs to be done for processes such as printing, gathering statistics, end-of-month calculations, searching etc.
It can be done either in-order, pre-order or post-order.
The method chosen depends on the application.
In the examples, we look at a 2-way or binary tree, as this is the simplest to understand.
In-Order Traversal
ProcessNode (node) [1]
ProcessNode (leftLink)
Process this node
ProcessNode (rightLink)
End ProcessNode
Examples don’t have the terminating condition for recursion – see note [1]
[1] A routine calling itself is called recursion. It is a kind of looping construct which makes use of the run-time stack (not the same as the ADS stack but the concept is the same – it is a LIFO). An out of control recursion will fill up your run-time stack.
Very important:
In the example algorithm above, there is **no** terminating condition. This will normally lead to out of control recursion but in this case when the leaf node’s link is accessed, the program will be killed. So if the value of the node is null, routine terminates – **this must be added to the algorithm**. See textbook chapter on Binary Trees in the textbook.
*
In-Order Traversal Animation
ProcessNode (node)
ProcessNode (leftLink)
Process this node
ProcessNode (rightLink)
End ProcessNode
END
*
Pre-Order Traversal
ProcessNode (node)
Process this node
ProcessNode (leftLink)
ProcessNode (rightLink)
End ProcessNode
Pre-Order Traversal Animation
ProcessNode (node)
Process this node
ProcessNode (leftLink)
ProcessNode (rightLink)
End ProcessNode
END
Post-Order Traversal
ProcessNode (node)
ProcessNode (leftLink)
ProcessNode (rightLink)
Process this node
End ProcessNode
Post-Order Traversal Animation
ProcessNode (node)
ProcessNode (leftLink)
ProcessNode (rightLink)
Process this node
End ProcessNode
END
Tree Searching
Trees will also need to be searched, and there are many different search algorithms available.
When not using heuristics, there are two main ways in which to do a logical search:
Depth first
which is simply a search done in pre-order stopping when the target data is found;
the aim is to find any match to the target;
this is commonly used when trying to find the one unique match.
Breadth first
where the nodes are searched in layers, down from the top;
this search aims to find the match that is closest to the start;
a common use for this is in game playing: you want to win as soon as possible.
Depth First Search Animation
Search (node) : boolean
boolean found
found = target at this node
IF not found
found = Search (leftLink)
IF not found
found = Search (rightLink)
ENDIF
ENDIF
return found
End Search
X
X
END
Breadth First Animation [1]
Add root to a queue of pointers
WHILE queue is not empty AND not found
Dequeue (current)
If current.data == target
found = true
ELSE
Enqueue (current.left)
Enqueue (current.right)
ENDIF
ENDWHILE
X
X
[1] An additional data structure is used – queue.
*
Breadth First Animation
X
X
Add root to a queue of pointers
WHILE queue is not empty AND not found
Dequeue (current)
If current.data == target
found = true
ELSE
Enqueue (current.left)
Enqueue (current.right)
ENDIF
ENDWHILE
current
Breadth First Animation
X
X
Add root to a queue of pointers
WHILE queue is not empty AND not found
Dequeue (current)
If current.data == target
found = true
ELSE
Enqueue (current.left)
Enqueue (current.right)
ENDIF
ENDWHILE
current
Breadth First Animation
X
X
Add root to a queue of pointers
WHILE queue is not empty AND not found
Dequeue (current)
If current.data == target
found = true
ELSE
Enqueue (current.left)
Enqueue (current.right)
ENDIF
ENDWHILE
current
Breadth First Animation
X
X
Add root to a queue of pointers
WHILE queue is not empty AND not found
Dequeue (current)
If current.data == target
found = true
ELSE
Enqueue (current.left)
Enqueue (current.right)
ENDIF
ENDWHILE
current
Breadth First Animation
X
X
Add root to a queue of pointers
WHILE queue is not empty AND not found
Dequeue (current)
If current.data == target
found = true
ELSE
Enqueue (current.left)
Enqueue (current.right)
ENDIF
ENDWHILE
current
END
Readings
Textbook: Chapter on Binary Trees
Should go through the programming example at the end of the chapter.
Further exploration:
Reference book, Introduction to Algorithms. For further study, there are many tree and tree algorithms described in the reference book. For this unit, the lecture notes, practical work and the textbook is sufficient.