Objectives of the week
Upon completion of this week work , you should be able
To understand binary trees and binary search trees (BST for short)
To be familiar with algorithms of search, insertion and deletion in a BST and their complexity
To understand algorithms for in-order, pre-order and post-order traversal of binary trees
To appreciate and to use Java implementations of the algorithms in applications
Lecture
In the previous weeks you have studied the array and linked list data structures and the use of these data structures for implementing ADTs such as stacks and queues. Basically arrays and linked lists are suitable for implements data types that are a sequence of data elements, which are linked together in a linear fashion. For some other data types, their elements (of the data set) have no linear relationship or more complex relationships. For example, consider a family tree, in which grand-children not only have links to their parents but also to their uncles, aunts, and grandparents. In the other end of the complexity spectrum of the links between elements, elements of a set have no specific link to each other. The only relationship held between the elements of a set is that they all belong to that set. Thus there is a need for having appropriate data structures in order to implement those non-sequential, unbounded and/or unordered data types. Trees data structures, in particular binary trees are useful in this regard.
In this lecture, several trees data structures, namely binary trees, balanced binary trees and binary search trees will be considered. Then operations such as searching, insertion, deletion, traversal and merging are inspected in terms of algorithm design and their implementation in Java.
Lab/Tutorial
At the end of this practical you should be able:
To consolidate your understanding of binary trees.
To consolidate your understanding of binary trees algorithms.
To implement operations that are performed on BST elements.
To utilise BST algorithms in application.
Exercises are given in the lab notes of this week.
Reading and addition learning resources