Level: Bachelor 2 Algorithms & Data Structures

Academic year: 2019/2020 Binary trees

Chapter 4:
Binary trees
1. Introduction
A tree is a structure composed of nodes and leaves (terminal nodes) connected by
branches.

B C D

E F G H

I J K

Fig.1: Example of a tree

 Node A is the root of the tree.

 The nodes E, I, J, K, G, and H are leaves.
 Nodes B, C, D, and F are intermediate nodes.
 If a branch connects a nodeito a nodejlocated lower down, we say quenIis an ancestor
denj.
 In a tree, a node has only one parent (direct ancestor).
 A node can contain one or more values.

1.1. The size of a tree: the size of a tree is the total number of its nodes.
1.2. Node level: each node is associated with a level such that:
- The level of the root=0.
- The level of the other nodes is incremented by 1 from the node of which it
depends.
1.3. Height (or depth) of a tree: the height of a tree is equal to
maximum of the levels of its leaves (i.e. the length of the path that connects it to the root).
1.4. Degree of a node: the degree of a node is defined as the number of sub-nodes it has.
content.
1.5. Degree of a tree: the degree of a tree is equal to the highest degree of its nodes.

1 Dr. KHOULALENE
Level: Bachelor's degree 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

Example:

In the tree above (Fig.1):

The size=11
Level(A)=0 Degré (A)=3
Niveau (C)=1 Degré (B)=2
Level (H)=2 Degree (D)=1
Level (K)=3 Degree (J)=0
Hauteur de l’arbre=3 Degree of the tree=3

2. Typology of trees:
2.1. Ordered tree: a tree is said to be ordered if the order of its nodes is important.
- -
and

A B B A

≠
The two trees above are different because (A-B) (B-A)

2.2. Binary trees: a binary tree is a tree whose degree < = (2the nodes have at
plus two wires: left and right).

B D

E F G H

I J

Fig. 2: Example of a binary tree.

2.3. Balanced tree: a binary tree is said to be balanced if every path from the root
to all the leaves of the tree is of the same length (the path is equal to the height
from the tree).

2 Dr. KHOULALENE
Level: Bachelor's degree 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

B D

E F G H

I L m n
j k

Fig.3: Example of a balanced binary tree

2.4. Complete tree: a balanced binary tree is said to be complete if all its levels are
of degree 2 except the last one which is of degree 0.

B D

E F G H

j L o p
i k m n

Fig.4: Example of a complete balanced binary tree

3. Transformation of any tree into a binary tree:

It is often useful to transform any tree whose nodes can
to have multiple successors (i.e. multiple children) in an equivalent binary tree.

Transformation rules:
To transform any tree into a binary tree, one begins by introducing
the two following concepts:

 The son of a node: it is the node to which the node in question points.
 The sibling of a node: it is a node at the same level as the node in question.

For the transformation, we proceed as follows:

Each node of the tree will point to one of its children (the leftmost), which will be its child.
left, and his closest brother, who will be his rightful son.

3 Dr. KHOULALENE
Level: Bachelor's Degree 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

Example:

A A

Transformation
B C D B

E F G H E C

F H D

Fig. 5: Transformation of any tree into a binary tree.

4. Treatments on trees:
Different treatments can be performed on a tree. We will, in what
suit, addressing the problem of traversing a tree (any method allowing to go through
through all the nodes of the tree). There are three main methods:

4.1. Prefixed path (RGD): Preorder

- Visit the root;
- Visit the left subtree;
- Visit the right sub-tree.
-
4.2. Fixed Path (GRD): Transversal
- Visit the left subtree;
- Visit the root;
- Visit the right subtree.
-
4.3. Postfixed path (GDR): postorder
- Visit the left subtree;
- Visit the right sub-tree;
- Visit the root.

4 Dr. KHOULALENE
Level: Bachelor's Degree 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

Example: Let the tree on the side be: =

8 +
1) Prefixed path: =8 + / + X Y 4 Z
2) Infix path: 8 = X + Y / 4 + Z Z
/
3) Postfix expression: 8 X Y + 4 / Z + =

+ 4

x y

5. Implementation of a binary tree:

5.1. Definition of the type
To implement a binary tree, we use the following type:

Record
type-a
↑
Right: Knot;
Left ↑
End;
↑
Tree: Node;
Var Tree

5.2. Operations on trees:

1) EmptyFunction(A): it allows to check if a tree is empty or not.

FunctionEmpty (A : Tree) : Boolean ;

Start

If(A=None)Then

See ←True;

Otherwise

See ←False;

End;

End;

5 Dr. KHOULALENE
Level: Bachelor's 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

Function Sheet (A): this function returns (-1) if the tree is empty, 1 if the
node is a leaf and 0 otherwise (intermediate node).

FunctionSheet (A : Tree) : enter ;

Start

If (see (A) = True) Then

Leaf ←−1 ;

Otherwise

↑ . A=Nil) and(Right A=Nil))

If((Left ↑. Then

Leaf ← 1;

Otherwise

Leaf ← 0;

End ;

End;

End;

3) Function size (A): this function allows returning the size of the tree (number
of nodes).

FunctionSize (A : Tree) : Enter ;

Beginning

If(A=None)Then

Size ←0;

Otherwise

Size ←1+ Size ↑(On

. the Left) ↑ . Size
+ (On the Right);

End;

End;

6 Dr. KHOULALENE
Level: Bachelor's Degree 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

4) Infix Function (A): this function allows you to traverse the tree using the method
infected.

InfixProcedure (A: Tree);

Start
If(A<>Nil)Then
↑.
Infix (A Left);
Write (A↑Val);
.
↑.
Infix (A Right);
End;
End;

5) Prefix Function (A): this function allows traversing the tree using the method
Prefixed.

Procedure Prefix (A: Tree);

Start
If(A<>Nil)Then
Write (To↑ Val);
.
Prefix (On↑the
. Left);

Prefix (To↑Right);
.

End;
End;
6) Postfix Function (A): this function allows traversing the tree using the method
Postixed.
PostfixProcedure (A : Tree);
Start
If(A<>Nil)Then
Postixe (On↑ .the Left);
Postfix (A ↑Right);
.

Write (A↑Val);
.

End;
End;

7 Dr. KHOULALENE
Level: Bachelor's 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

7) Function Search (A, V): this function allows you to search for a value V in
a tree A.

FunctionSearch (A : Tree ; V : type-a) : boolean ;

Start
If(A=None)Then
Search ←
False;
Otherwise
If(A ↑Val=V)
. Then
Real ←
Search;
Otherwise
Search ←
Search (On ↑.
the Left) OR Search ↑(On
. the Right);
End;
End;
End;
OU
FunctionSearch (A : Tree; V : type-a) : boolean;
Start
If(A=Nil)Then
Search ←
False;
Otherwise
If(A ↑Val=V)
. Then
Search ←
True;
Otherwise
If (Search (To the↑Left)
. = False) Then

Research ←Research (A ↑ . Right) ;

End;
End ;
End;
End;

8 Dr. KHOULALENE
Level: Bachelor's 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

8) Addition: to add an element to a tree, three cases arise:

 Add as soon as possible;
 Add in such a way as to obtain a balanced tree;
 Add in following a certain logic.

a) Procedure Create: This Procedure allows to create a node of a tree.

Procedure Create (VarA : Tree ; V : types-a);

Beginning
New (A) ;
A↑ . Val← V ;
A↑ . Left ←
Nil ;
A↑ . Right ← Nil;
End;
b) Addition Procedure (as soon as possible):

ProcedureAddP (VarA: Tree; V: type-a);

Var Tree
Start
If(A=Nil)Then
Create (Q,V);
A← Q ;
Release (Q);
Otherwise
↑.
If(Left=Nil) Then
Create (Q,V);
A↑ . Left ← ;
Q
Release (Q);
Otherwise
AddP (To↑the
. Left, V);

End;
End;
End;

9 Dr. KHOULALENE
Level: Bachelor's 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

c) Add Procedure (In order to have a balanced tree):

AddBcProcedure (VarA : Tree ; V : type-a);

Var Tree
Start
If (Video (A) = True) Then

Create (Q,V);
A← Q ;
Release (Q);
Otherwise
↑ . (Right Size)
If (Left Size) ≤ Then↑ .
↑.
If(Left=Nil) Then
Create (Q,V);
A↑ . Left ← ;
Q
Free (Q);
Otherwise
↑.
AddBc(Left, V);
End;
Otherwise
If(A ↑Right=Nil)
. Then
Create (Q,V);
A↑ . Right ← Q;
Release (Q);
Otherwise
AddBc(A ↑ .Right, V);
End;
End
End;
End;

10 Dr. KHOULALENE
Level: Bachelor's 2 Algorithmics & Data Structures
Academic year: 2019/2020 Binary trees

6. Binary Search Trees:

A binary search tree (BST) is a binary tree that has the fundamental property
next :

- All the nodes in the left subtree of a node have a value less than its own.
root of the sub-tree).
- All the nodes of the right subtree of a node have a value greater than or equal to the
sienna.

Example:
Construction of an AVL tree from the following values: 6, 3, 10, 11, 15, 13, 4, 9, 7, 1, 2

3 10

4 9 11
Min 1

2
15 Max
7

13

Fig.1: Example of a binary search tree

7. Implementation of a binary search tree:

7.1. Definitions of the type
To implement a binary search tree, we use the following type:

Record
type-a
↑
FG: Node;
Node↑
End;
ABR: ↑Node;

Var A : ABR ;

11 Dr. KHOULALENE
Level: Bachelor 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

7.2. Operations on binary search trees:

1) Adding a node in a binary search tree: the following procedure allows you to add a node
in a binary search tree.

ProcedureAdd (VarA : BST ; V : type-a);

Var ABR
Beginning
New (Q);
Q↑ . Val ← V;
Q↑ . FG ← Nil
Q↑ . FG ← Nil;
If(A = Nil)Then
A← Q ;
Otherwise
B ← A ; Stop False
← ;

TQ(False ¿Stop) Do
If(V ≥B Val)Then
↑.

If (B↑ FD=Nil)
. Then
B↑ . FD← Q ;
Stop ←True;
Otherwise
B← B↑ . FD ;
End;
Otherwise
If(B ↑FG=Nil)
. Then
B↑ . FG ← Q ;
Stop ←True;
Otherwise
B← B↑ . FG;
End ; End ; End ; End ;
Release (Q);
End;

12 Dr. KHOULALENE
Level: Bachelor's 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

2) Deletion of a node in a binary search tree:

The deletion of a key (a value) in a binary search tree (BST) is a complex operation. It
is accompanied by the removal of a node but it is not always the node that holds the key to
delete what will be removed.

Let 'S' be the node that carries the key 'X' to be removed. Three cases must be considered depending on the number of
son of 'S':
- The node 'S' is a leaf;
- The 'S' node has only one child;
- The 'S' node has two threads.
a) Deleting a leaf: If the node 'S' is a leaf then we eliminate it.
Example: The deletion of key 13 is illustrated in the following figure:

b) Deleting a node with a single child: If the node 'S' has a single child, we remove
'S' and we raise his son.
Example: The following figure illustrates the ascent: the node 'S' which holds the key 16 has only one
the only son who is the key node 18. This son becomes the son of the father of 'S', who is the node of
key 20.

13 Dr. KHOULALENE
Level: Bachelor's degree 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

c) Deleting a node with two children: If the node 'S' has two children, we look for the
predecessor 'T' of 'S' in the infixed order. We replace the content of 'S' with the content
from 'T', and we eliminate 'T'.

Example: The key to be deleted is at the root of the tree and it has two
files. In this case, we do not delete the node, but only its key, by replacing the key
by another key. Key 14 is placed at the root of the tree (key 14 is the key of the predecessor
from the root in infix order). We are then brought back to the problem of deletion
of a node having a single child and its key (Node with key 14). The deletion is therefore
covered by one of the first two cases.

The procedure below allows you to remove a node with two children. This procedure does
call to the 'replace' procedure. The latter allows you to place in the node, containing the
value to be deleted, the value of its predecessor in the infixed traversal.

14 Dr. KHOULALENE
Level: Bachelor's degree 2 Algorithms & Data Structures
Academic year: 2019/2020 Binary trees

ProcedureDelete (VarA : ABR ; V : type-a);

Var B : ABR ;

Start
If(A<>Nil)Then
If(A ↑Val=V)
. Then
If(A ↑FG=Nil)
. Then
A ← A↑ . FD ;
Otherwise
If(A ↑FD=Nil)
. Then
A ←↑.
A FG ;
Otherwise
B ←↑.
A FG ;
Replace (A, B);
End;
End;
Otherwise
If(V<A ↑Val). Then
Delete (A FG,↑V);
.
Otherwise
Delete (A FD,↑V);
.
End;
End;
End;
End;

Procedure Replace (VarA : ABR ; B : ABR) ;

Beginning
If(B ↑FD<>Nil)
. Then
↑.
Replace (A, B FD);
Otherwise
A↑ . Val ←↑.
B Val ;
A ←↑. A FG ;
End;
End;

15 Dr. KHOULALENE
Level: second year of undergraduate Algorithmics & Data Structures
Academic year: 2019/2020 Binary trees

4) Search for the Minimum

In a BST, the minimum is the key located in the leftmost node.
infix path.
The algorithm is as follows:
FunctionMinimum ( A : Tree) : enter ;

Beginning
TQ(A ↑. Left <> Nil) Do
A← A↑ . Left ;
End;
Minimum← A.↑ Val;
End ;

5) Search for the Maximum

In a BST, the maximum is the key found in the rightmost node.
infix path. The algorithm is as follows:

FunctionMaximum ( A : Tree ) : enter ;

Start
If(A ↑. Right <> Nil) Do
Maximum← Maximum ↑(A. Right);
Otherwise
Maximum← A.↑ Val;
End;
End;

16 Dr. KHOULALENE