Exploring Trees

Exploring Trees

Trees

A tree is a data structure that stores many elements in a hierarchical manner. Trees are a familiar way of thinking about data as it allows for topics such as organisation and categorisation to influence the storage.

Every element (excluding the node) in a tree will have a parent element and some may have child elements. There is normally some kind of logical relationship between elements, their parent elements and their child elements.

Tree structure Every tree that has contents must have a root node, a root node is the first and cannot have a parent.

If a node has a parent then that node is said to be a child of that node. For example, in the above example, the node SUV is a child of Car. Equally, Car is a parent of the SUV node. Nodes that have the same parent as the target are said to be siblings of that node. For example, Speed boat and inflatable boat are siblings of each other.

Leaf nodes (external nodes) can be found at the bottom of the tree, leaf nodes are elements that do not have any child elements, this relates to how leaves can be found at the end of a branch.

Nodes are said to be an ancestor of another node if they are at a higher level and can be followed down to a descendant. For example, Vehicle is said to be an ancestor of the descendant Longboat.

Ordered Trees

An ordered tree means there is a meaningful order between the children of a parent node that is represented left to right. For example, if we had a tree that represented the tracks on a cd, then the child node ‘track 1’ would be placed to the left of the node ‘track 2’.

It is not always possible to create an ordered tree from a domain area as there might not be any relationships to order. The above vehicle tree demonstrates this – there is no reason why a car would be ordered before boat or vice versa.

Depth

The depth of a node is an important property. The depth of a node is the amount of ancestors before it – this does not include the node itself.

Tree depth n the above example, the node named ‘Chicago’ is at a depth of 3 as it can reach the root node in 3 steps. USA → North America → The World. If the tree only contained the root node then the tree would have a depth of 0.

Pseudocode for Finding Depth

FUNCTION DEPTH(Node node) if node is root return 0 else Return 1 + DEPTH(parent(p)) HEIGHT

Height is a property that is specific to the tree itself rather than a node within the tree. The height of a tree is the maximum depth of the deepest leaf node. Yet again, if the tree only has a root node then the height of the tree will be 0.

In the above figure, the tree has a height of 4 with the ‘Long Beach’ and ‘Santa Monica’ nodes being at the maximum depth.

Pseudocode for Finding Height

Starting at the node, finding the maximum depth, and therefore the height is quite inefficient as the deepest path is not known. Here is the pseudocode for this inefficient method:

FUNCTION HEIGHT() h ← 0 for position in all positions if position is external If position depth > h h ← position depth return h

The reason for this implementation being inefficient is because we have to do a depth first search on the tree, which requires us to go as deep as we can on a path from left to right. There will be a tutorial on searching trees at a later point.

In a worst case scenario, this algorithm will run in O(n2) time complexity.