An introduction to trees
Tree structures
Another dynamic data structure is known as a ‘tree structure’. Data items are organised according to some rules. Once in this structure, the data can then be sorted. Suppose, for example, we wanted to organise the following list of fruit into a binary tree structure so that they can then be sorted into alphabetical order.
mango, banana, pineapple, apple, coconut, pear, grape, strawberry, raspberry.
How would we go about this?
Step 1: The tree doesn’t exist when we want to ‘insert’ the first item, mango, into the tree. The first item is therefore placed at the top of the diagram. This position, or node, is known as the ‘root node’.
Step 2: Alphabetically, the b of banana is less than the m of mango, so we branch left. In binary trees, if a piece of data is less than the current node, we will branch left. If it is greater than the node, we will branch right. (Note that we could reverse the left and right branching if we wanted to. We would get the same tree but as a mirror image). A node will only ever have a maximum of two branches underneath it in a binary tree, one branching left and the other branching right. (You can have trees that are not binary, but that is beyond the scope of our discussion).
Step 3: The p of pineapple is greater than the m of mango, so we branch right.
Step 4: The a of apple is less than m of mango so we branch left. Then it is less than the b of banana so we branch left again. Now there is no node in that position so our new data goes in that position. Apple goes under banana and to the left.
Step 5: The c of coconut is less than mango so branch left. Coconut is greater than banana so branch right.
Step 6: Pear is alphabetically greater than mango, so branch right. It is less than pineapple so branch left.
Step 7: Grape is less than mango so branch left. It is greater than banana, so branch right. It is greater than coconut so branch right again.
Step 8: Strawberry is greater than mango so branch right. It is also greater than pineapple, so branch right again.
Step 9: Raspberry is greater than mango, so branch right. It is greater than pineapple, so branch right again and it is less than strawberry, so now branch left.
Note that mango is known as the ‘root node’. The nodes with no nodes underneath them are known as the ‘terminal nodes’. In this case, the terminal nodes are apple, grape, pear and raspberry. Each node can have a maximum of two nodes branching underneath it if the tree is a special kind of tree called a ‘binary tree’. We can formalise a little more the insertion of each new data item using the following pseudocode.
Insertion algorithm
To inset an item into a tree structure, we follow this algorithm for each item in turn. The CURRENT NODE is the position we are currently at. The DATA ITEM is the new item we want to insert into the tree.
If the tree doesn't exist yet, make the DATA ITEM = ROOT NODE and finish.
Let CURRENT NODE = ROOT NODE.
Repeat until CURRENT NODE is null.
If DATA ITEM is less than CURRENT NODE
go to the left.
Else
go to the right.
EndIf
CURRENT NODE = value of node reached so far. (Node reached so far = null if there is no node at that position).
Create new node and add DATA ITEM to that position.
End Repeat
Deletion algorithm
Deleting items from a tree structure is quite complicated. There are a number of ways to do it. Here’s one way:
-
- Traverse the tree until you find the item that you want to delete.
- Call that item the root node.
- Copy all of the items underneath the root node to another data structure, perhaps using a stack, for example.
- Delete the root node.
- Use the insertion algorithm to re-enter each data item in turn from the stack into the tree.
Suppose we wanted to delete 'pineapple' from the fruit binary tree we used above. We find pineapple, copy all the items underneath it to a stack and then delete the pineapple node. The tree and stack data structures would look like this.
We then pop the data items from the stack and use the insertion algorithm to re-enter data into the tress structure. The tree will then look like this.
Amending data
Trees are used because they maintain an order between a number of data items. Amending the data would result in the order of the data in the tree changing. Algorithms for amending the data in trees are therefore beyond the scope of this course.