Chapter 3
Trees
3.1 Generalities
3.1.1 Definitions
A tree is a non-linear data storage structure. It is made up of elements called Nodes
or Vertices. These nodes are connected by oriented arcs or edges.
Example: Consider the following tree
3.1.2 Terminology
The node that is not the end point of any arc is called the root.
A node that is not the start point of any arc is called a leaf.
The size of a tree is the number of its nodes.
The parent of a node is the predecessor of this node.
The child(ren) of a node is(are) the successor(s) of this node.
The siblings are the nodes that have the same parent.
The path between two nodes is called a branch.
17
3.2. BINARY TREE
If x and y are two nodes such that x is on the path from the root r to y then:
• x is an ancestor of y
• y is a descendant of x
The height of a node is the length of the longest path from this node to its dependent
leaves plus 1. The height is the number of nodes in the path.
The depth of a node is the length of the path from the root to this node.
The arity of a tree is the maximum number of children it has for a given node. A
tree whose nodes will have at most m children will have an arity of m and it is called
an m-ary tree. In a special case where m = 2 , the tree is called binary tree
3.2 Binary tree
3.2.1 Definition
A binary tree is:
• either empty
• either composed of:
* a root r,
* two binary subtrees LT and RT such that:
• LT is the left subtree,
• RT is the right subtree.
3.2.2 Binary tree creation
3.2.2.1 Using pointers
To define the binary tree, we use two pointers to LT and RT. The tree is defined in
algorithmic as follows:
type Node = Record
E : Element;
LT : pointer Node;
RT : pointer Node;
end.
var N : pointer Node;
18
CHAPTER 3. TREES
3.2.2.2 Using an array
Each element of the array represents a node and should contain three fields : the
node value, the index of the left child and the index of the right child. The tree is
defined in algorithmic as follows:
type Node = Record
E : Element;
IndexLC : integer;
IndexRC: integer;
end.
Const Max = 100;
type ANode = Record
Size : integer;
Arr : array[Max] of Node;
IndexRoot : integer;
end.
var T : ANode;
3.2.3 Tree traversal
3.2.3.1 Depth First Traversal
This involves exploring each branch before moving on to the next one. The traversal
is complete when there is no branch to explore.
• Prefix : Root, then Left subtree, finally Right subtree.
• Infix : Left subtree, then Root, finally Right subtree.
• Postfix : Left subtree, then Right subtree, finally the Root.
3.2.3.2 Breadth First traversal
This involves exploring the nodes by level. In each level the nodes are traversed
from the left to the right.
3.3 Particular binary trees
3.3.1 Perfect binary tree
Each level of the tree is completely filled. This means that every node is either a
leaf or has exactly two children.
19
3.3. PARTICULAR BINARY TREES
3.3.2 Complete binary tree
All levels are completely filled except possibly the last one. In this last level, the
leaves are as far to the left as possible.
3.3.3 Balanced Binary Tree
The height difference between two siblings cannot exceed one.
3.3.4 Binary Search Tree (BST)
In this type, we have :
• every node in the left subtree is less than or equal to the root.
• every node in the right subtree is greater than to the root.
In order to insert a new element in a BST, we follow the steps given bellow:
• Start from the Root.
• If the Root is not empty : if the value to insert is smaller than the current
root’s value, we explore the left subtree else we explore the right subtree.
• If the root is empty, then insert the new element node.
3.3.5 Balanced Binary Search Tree (AVL)
A tree is called AVL if it is a binary search tree and balanced at the same time.
Rotations must be applied when the insertion of a new element makes the tree
unbalanced. Two types of rotations exist: a right rotation and a left rotation.
3.3.6 HEAP Structure
A heap is a complete binary tree where each node respects the heap property. The
heap property distinguish two types of heaps :
A min-heap: each node contains a key less than all the keys of the nodes of
the left and right subtrees.
A max-heap: each node contains a key greater than all the keys of the nodes
of the left and right subtrees.
The elements of a heap can be filled in an array following a breadth first traversal.
Position 0 is not occupied and we start from position 1.
20
CHAPTER 3. TREES
• The root occupies position 1
• A node that is at position i, its left child is at position 2i and its right child is
at position 2i+1.
• The parent node of a node is at position i/2.
To define the Heap structure, we use:
Const Max = 100;
type HEAP = Record
Data[Max] : integer;
size : integer;
end;
var H : HEAP;
In order to insert a new element into the heap, you have to do two steps:
• Insert the element into the first empty cell of the table (size + 1).
• Make parent/child permutations to preserve the heap property.
In order to delete an element from the heap, you have to do two steps:
• replace this element with the last element in the Heap and changing the size.
• Make parent/child permutations to preserve the heap property.
3.3.6.1 Heap Sort
It is possible to sort an array using Heap structure. The Heap and HeapSort func-
tions are given as follows.
Algorithm 3.1: Heap(Arr, n, i)
1 index ← i;
2 if (Arr[index] < Arr[2 ∗ i]) then
3 index ← 2 ∗ i;
4 end
5 if (Arr[index] < Arr[2 ∗ i + 1]) then
6 index ← 2 ∗ i + 1;
7 end
8 if (i <> index) then
9 tmp ← Arr[i];
10 Arr[i] ← Arr[index];
11 Arr[index] ← tmp;
12 Heap(Arr, n, index);
13 end
21
3.3. PARTICULAR BINARY TREES
Algorithm 3.2: HeapSort(Arr, n)
1 for i ← n/2 to 1 do
2 Heap(Arr, n, i);
3 end
4 for i ← n to 2 do
5 tmp ← Arr[i];
6 Arr[i] ← Arr[1];
7 Arr[1] ← tmp;
8 Heap(Arr, n − 1, 1);
9 end
The worst-case complexity of sorting by TAS is O(nlogn). The best-case com-
plexity of sorting by TAS is O(n).
22
