Trees

Binary trees will be examined at the level of diagrams and descriptions. Students are not expected to construct tree algorithms using pseudocode.

Tracing and constructing algorithms are not expected.

 

Sample Question - FORMER CURRICULUM:

(i) Briefly explain how a binary tree could be searched to check if a particular value
is stored in the tree. [3 marks]

JSR Notes:

Trees and General Trees

A tree in computer science terms is a non-linear data structure used to organize data in hierarchical manner. Another term for non-binary trees is "general tree". A general tree is a hierarchical structure whose nodes can have any number of children, not just a maximum of two (like binary trees; see below).

General Tree Quora.com

In terms of how they operate, all trees will need to have nodes that use referential mechanisms; ie. their components are nodes made up of the data they store, along with one or more pointers to other nodes of the same type. It is through sequentially following along a certain path of those, via the pointers that nodes can be found, added, and deleted.

General trees can be useful for modeling real hierarchical structures, such as the hierarchy in a company from the company president on down to the clerk in the mailroom. But such tree structures are not as easy to code and manage as the binary trees, which this assessment statement is primarily about.

Binary (Search) Trees

Binary trees are also called binary search trees; the two terms are interchangeable.

In a binary tree each node has a maximum of two children.

The logic of how binary search trees are organized, and operate, is therefore much more straight-forward and easy to manage than general tree structures. In a binary tree, the data is organized such that data which is "greater" than a certain node is placed to the right of that node, and data which is "lesser" than a certain node is placed to the left of that node.

Binary tree

(For all of the following, refer also the the diagrams and video on 5.1.17. In fact, it may not be a bad idea to do that first.)

Adding to a Binary Tree

When adding to a tree, a piece of data moves down through the branches of the tree asking, at each node, whether it is "greater" or "lesser" than the node it is currently at. If it is greater than any given node it encounters when traveling down through the tree, it continues on to the right, and if it is lesser, it continues on to the left. When it reaches the end of one of the branches, it gets added there, either to the left or right of that last node.

Removing an item from a Binary Tree

Removing data from a binary tree is trickier than adding or searching. A certain sequence of re-linking has to take place, depending on whether the node to be deleted is at the end of a branch, has one child itself, or has two children itself. Refer to the video and diagram in 5.1.17.

Searching for an item in a Binary Tree

When searching through a tree made in a binary way, we ask the question at each node "is what we are looking for greater or lesser than the node at which we presently are?". If the answer is greater than, then we move through the tree along the right branch, and if lesser, along the left branch.

In this way, searching is done in a log2, or binary, way. In a perfectly balanced tree, each step through it to find something, eliminates half of the remaining elements in the search.

 

The problem of an unbalanced tree

Do note that achieving a log2 or close-to-log2 efficiency with a binary search tree is only possible when the tree is balanced, with each node having an equal number of nodes to its right and to its left. Key to coming as close to possible to a perfectly balanced tree is picking a root value that is in the middle of the data set. Note that in the worst case scenario, a tree could end up no different than a linked list - rather than having logarithmic search efficiency it could have only a linear one.