NATIONAL TECHNOLOGICAL UNIVERSITY OF SOUTH LIMA

FACULTY OF ENGINEERING AND MANAGEMENT

SCHOOL OF PROFESSIONAL SYSTEMS ENGINEERING

ALGORITHMS AND DATA STRUCTURES

TREES IN PYTHON

Manuel Alcántara Ramirez

MANSILLA CAMACHO, ELI SANTIAGO

LIMA, 2020

1
 INDEX

INTRODUCTION.3
CHAPTER I: FUNDAMENTAL DEFINITIONS................................................................4
1. DEFINITIONS AND PROPERTIES OF TREES..................................................6
2. TREES BINARIES............................................................................................................8
3. TREES SEARCH BINARIES11
CHAPTER II: TREES IN PYTHON
1. IMPLEMENTATION FROM A BINARY SEARCH TREE...................................13
2. OPERATIONS IN A BINARY SEARCH TREE.........................................13
2.1 Insert...........................................................................................................................13
2.2 Journey and printing15
A. Inorder traversal (IRD)15
B. Preorder traversal (RID).......................................................................................16
C. In post-order (IDR).................................................................................................16
2.3 Search............................................................................................................................17
2.4 Suppress..........................................................................................................................17
3. CODE FOR BINARY SEARCH TREES IN PYTHON........................19
CHAPTER III: EXERCISES
CHAPTER IV: APPLICATIONS...........................................................................................25
CONCLUSIONS. 27
BIBLIOGRAPHY. 28

2
 INTRODUCTION

Trees are one of the most important structures in programming.

They can be applied to the solution of different types of problems, such as the
ordering, searching, mathematical representation, etc. This work
It aims to present a synthesis of the theory of trees and its
applications. Python will be used as the base language for the development of our
explanation. Python is an open-source language, considered as a language
high-level interpreted.

In the first chapter, we will provide an approach to the fundamentals of these.

structures, their properties and characteristics. In the second chapter we will propose
some exercises within the language discussed to exemplify the theory. Finally,
In a third chapter, we will present some applications of trees in
concrete programs.

3
 CHAPTER I: FUNDAMENTAL DEFINITIONS

Data structures are classified into static and dynamic, based on their capacity.
to change shape and size. They can also be classified as linear and non-linear.
linear, according to the distribution of their elements.

Trees are nonlinear and dynamic structures of vital importance within the
computation. They are hierarchical structures, applied to elements called
nodes.

We can define a tree as follows: a tree is a finite set of

nodes and branches, so that:

There is a node called the root node.

The branches connect the nodes, in such a way that a relationship is imposed.
hierarchical among them.
Each node of the tree is the root of some subtree contained in the main tree.

Trees are recursive structures, as each subtree is itself a tree.

They can be used to represent mathematical formulas, to record history.

from a football championship, to construct a family tree, to enumerate
sections of a book, etc.

Let's think of a book that has the following structure:

TITLE

1. CHAPTER1
a. Section1
i. Subsection
b. Section2
i. Subsection1
ii. Subsection2

4
 iii. Subsection3
2. CHAPTER2
a. Section1
i. Subsection
b. Section2
i. Subsection1
ii. Subsection2
c. Section3
i. Subsection

We can represent this information as follows:

Illustration 1: Graph representation

Illustration 2: Venn Diagram

( A ( B ( D ( I ), E ( J, K, L )), C ( F ( O ), G ( M, N ), H ( P ))))

Nesting of parentheses

5
1. DEFINITIONS AND PROPERTIES OF TREES

a) Each node is the root of a tree.

b) In a tree with n nodes, the number of edges is n-1.
c) If there is a branch that extends from n to h, it is said that n is the parent of h.
therefore, h is the son of n.

Each node has a unique parent, except for the root.

e) Siblings are those who have the same father.
f) The nodes that have no children, that is, do not present branches, are
node calls sheet.
g) Node degree: it is the number of direct descendants of a certain
node.
h) Degree of the tree: it is the maximum degree of all the nodes in the tree.

i) Level or depth of a node: it is the number of edges that must be

traversals to reach a certain node. The depth of the root is 0. The
the depth of a node is equal to the depth of its parent + 1.
j) Height of a node length of the longest path, starts at the node and ends
in a leaf. The height of a leaf node is 0. The height of a node is equal to the
greater height of their children + 1

Height of the tree is the maximum number of levels of all the nodes of the tree.
The descendants of a node (c in the diagram) are those accessible nodes.
through a path that starts at the node.
m) The ancestors of a node are the nodes on the path from the root to it.

6
 Illustration 3: Height of the tree. Illustration 4: Depth of the tree.

A. Length of internal road

It is the sum of the path lengths of all the nodes in the tree. It is calculated
by means of the formula:

h
LCI=¿ ∑
i=1
∗I
I

Where:

i: tree level
altura
ni: number of nodes at level i

Average length of internal path: for this, the LCI is divided by the
number of nodes of the tree (n).

LCI
LCIM=
n

B. Length of external path

Extended tree: it is a tree where the number of children of each node is equal to the
grade of the tree. If any of the trees do not comply, as many must be incorporated.
special nodes as required.

Special node: their goal is to replace empty or null branches

7
Then the length of the external path is the sum of the lengths of the path of
all the special nodes of the tree. It is calculated by the formula.

h +1
LCE=¿ = ∑
I=2
n∗I
hey

Where:

tree level
h: height
nei: number of special nodes at level i

Average length of external path (LCEM): divide the LCE by the number of
special nodes of the tree () n e

LCE
LCEM=
ne

Where:

e: number of arcs that must be traversed in

average to arrive, starting from the root, at a
any special node of the tree.

2. BINARY TREES

It is a tree where each node can have at most two subtrees, not
left and another right. An empty tree is a special type of binary tree. The
The height of an empty tree is -1.

Binary trees are used to represent the solution to a two-part problem.

alternatives, to represent family trees, the history of a championship of
tennis, etc.

8
 Illustration 5: Examples of binary trees

Illustration 6: Representation of the history of a championship using a binary tree.

A. Different trees: when their structures are different.

a) b)
a and b are distinct trees

B. Similar trees: when their structures are identical, but the information
of its nodes is different from each other.

9
 a) b)
a and b are similar trees

C. Equivalent trees: they are similar trees and their nodes have the same
information.

a) b)
a and b are equivalent trees

D. Complete binary trees: All its nodes, except those of the last level,
they have 2 children: left and right subtrees.

a)

10
 b)
a and b are complete trees

Number of nodes in a complete tree of height h:

h
Number of nodes (ABC=2−1
)

3. BINARY SEARCH TREES

For every node T of the tree, it must be fulfilled that all the values of the nodes of the
The left subtree of T must contain values smaller than or equal to the value of node T. In this way

similar, all the values of the nodes of the right subtree of T must be
greater than or equal to the value of node T.

An in-order traversal of the tree visits the elements in ascending order.

mayor.
The minimum element is the first node without a left child in a descent by
leftist children from the root.
The maximum element is the first node without a right child in a descent by
children's rights from the root.
In a search tree, you can perform the operations of: search,
insertion, deletion, and printing. We will detail them in the next chapter.

11
Illustration 7: Distribution of elements in a binary search tree.

Illustration 8: Graph of a binary search tree.

12
 CHAPTER II: TREES IN PYTHON

IMPLEMENTATION OF A BINARY SEARCH TREE

To implement a binary search tree, we will use a class. In Python,

Classes provide a way to package data and functionality. When creating
a new class, a new type of object is created, allowing to create
new instances of that type. Each class instance can have attributes
attachments to maintain their state. Class instances can also have
methods (defined by their class) to modify their state.

For this case, we will use the Node class, as we will see below.

class Node:
def __init__(self, data):
[Link] = None
[Link] = None
[Link] = data

Once the Node class is created, we need to define the basic functions for it.
Insert, traverse and print, search and delete.

2. OPERATIONS IN A BINARY SEARCH TREE

2.1 Insert

Build the nodes and insert them into the binary tree of
Function
search.

Entry Node information.

Exit No exit.

13
 Conditions of The tree contains a node with information, located at
exit agreement with its key value and the rule defined in the function.

The insert function introduces the node's information and places it in the tree according to its
value and the conditions established in the function. To insert an element you
the following steps are taken:

1.- The key to be inserted must be compared with the root of the tree. If it is greater, it must

move towards the right subtree. If it is less, it should move towards the
left subtree.

2.- Repeat step 1 successively until one of the following is met.

conditions:

The right subtree is equal to empty, or the left subtree is equal to empty;
in which case the item will be inserted in the place that corresponds to it
corresponds.
The key to be inserted is equal to the root of the tree; in which case it does not
perform the insertion.

We show the code in Python to perform this operation:

def insert(root, node):

if root is None:
root = node
else:
if [Link] < [Link]:
if [Link] is None:
[Link] = node
else:
insert([Link], node)
else:
if [Link] is None:
[Link] = node
else:
insert([Link], node)

2.2 Route and printing

14
 Traverse and print all the elements of the binary tree
Function
search in the indicated order.

Entry Type of traversal (preorder, inorder, postorder).

Exit Show all the elements of the tree.

Conditions of The tree does not suffer changes.

exit

A very important operation when working with trees is their traversal. This consists of
by visiting the nodes in an orderly manner; so that all nodes are
visited only once. There are three types of tours:

Inorder traversal
Preorder traversal
Post-order traversal

A. In-Order Traversal (IRD)

It is also called a symmetric method. It is described as follows:

Move to the left subtree until reaching the maximum depth.

Visit the current node.
Return to the previous node in the tree and visit it.
Always move to the right subtree of the previously visited node
that exists and has not been previously visited, otherwise, return to the
previous node.
Repeat the previous steps until all nodes have been
processed.

def inorder(root):
if root is not None:
inorder([Link])
print([Link], end=" ")
inorder([Link])

15
 B. Pre-order traversal (RID)

In pre-order traversal, the current node is visited before traversing the subtree.
left.

Visit the root

Traverse the left tree in pre-order
Traverse the right tree in pre-order

def preorder(root):
if root is not None:
print([Link], end=" ")
preorder([Link])
preorder([Link])

C. In postorder (IDR)

The postorder traversal visits the node after traversing the left and right subtrees.
law respectively. The procedure that implements this type of journey
is the following:

Traverse the left subtree in postorder

Traverse the right tree in postorder
Visit the root

def postorder(root):
if root is not None:
postorder([Link])
postorder([Link])
print([Link], end=" ")

16
 2.3 Search

Take a key value and search for it in the information of the

Function
nodes.
Entry Key value.

Exit Returns a node that contains the key value.

Conditions of
The tree does not undergo changes.
exit

With this operation, it explores within the tree, according to the requested key; it returns
None if not found. Below, we show an implementation of this
function follows below:

def search_data(root, data):

if root is None:
The element does not exist!
elif [Link] == data:
Element found!
elif data < [Link]:
return search_data([Link], data)
else:
return search_data([Link], data)

2.4 Suppress

Function Delete the node that contains the specified key value.

Entrance Key value.

Exit None.

Conditions of
The node that contained the key value is not in the tree.
output

17
To remove a value in a binary search tree, the following cases can arise:
following cases:

a) That the element is a leaf node.

b) That the element is a node without a left or right child. In this case,
its only sub-tree climbs to take the place of the node.
c) That the element has two subtrees. The removal can be by
successor or predecessor. If it is by successor, the successor does not have a child.

left, then it can be moved from its position to that of

element to be removed, but the node that will free the memory will be the
successor.

Algorithm to remove an element

a) Check that the tree is not empty

b) Introduce the element to be removed
c) Find the element
d) Call the delete function, sending the parameter with the key value.
e) The delete function must consider the three cases of deletion.
f) When deleting it, free the memory of the element and display the tree without it.
element.

def delete(root, data):

if root is None:
...The element does not exist...
elif [Link] == data:
if ([Link] is None and [Link] is None):
[Link]
...Element deleted...
elif ([Link] is None and [Link] is not None):
[Link] = [Link]
[Link]
elif ([Link] is not None and [Link] is None):
[Link] = [Link]
[Link]
...Element deleted...
elif data < [Link]:
return delete([Link], data)
else:
return remove([Link], data)

18
Before closing the chapter, we will present the code to implement a tree.
binary search, where we will find the operations we have described
previously.

3. CODE FOR BINARY SEARCH TREES IN PYTHON

Next, we present the code in Python for the implementation of a tree.

binary search and the basic operations that can be performed on it.

class Node: We create the

def __init__(self, data): class Node
[Link] = None
[Link] = None
[Link] = data

def insert(root, node): The is created

if root is None: insert function
root = node node and it
else: define the
if [Link] < [Link]: conditions for
if [Link] is None: fill the tree
[Link] = node binary
else:
insert(right_node, node)
else:
if [Link] is None:
[Link] = node
else:
insert([Link], node)

def inorder(root): Each is defined

if root is not None: one of the
inorder([Link]) tours of
print([Link],end=" ") reading of the
inorder([Link]) tree.

def preorder(root):
if root is not None:
print([Link], end=" ")
preorder([Link])

19
preorder([Link])

def postorder(root):
if root is not None:
postorder([Link])
postorder([Link])
print([Link], end=" ")

def search_data(root, data): The is defined

if root is None: search function.
The element does not exist!
elif [Link] == data:
Element found!
elif data < [Link]:
return search_data([Link], data)
else:
return search_data([Link], data)

def delete(root, value): #It is defined the

if root is None: function
...The element does not exist... remove, according to
elif [Link] == data: the different
if([Link] is None and [Link] is cases.
None):
[Link]
...Element removed...
elif([Link] is None and [Link]
is not None):
[Link] = [Link]
[Link]
elif ([Link] is not None and
[Link] is None:
[Link] = [Link]
[Link]
elif data < [Link]:
return delete([Link], data)
else:
return delete([Link], data)

20
 CHAPTER III: EXERCISES

1. Create a program that implements a binary search tree.

Ingresar los siguientes elementos: 7, 5, 9, 2, 6, 8, 12, 3, 10.

To insert the elements into the tree, the function is called and the
parameters for each case.

root = Node(7) The ones that are entered

insert(root, Node(5)) elements
insert(root, Node(9)) manually for
insert(root, Node(2)) the construction
insert(root, Node(6)) from the tree.
insert(root, Node(8))
insert(root, Node(12))
insert(root, Node(3))
insert(root, Node(10))

2. Print the elements of the tree, starting from the three types of traversal.

Based on the data entered in the previous exercise, we can show the three
types of routes studied.

::::::: FIRST OPERATION #Se makes the

(TOUR) :::::: call of the
functions what
A. INORDER Traversal: they will show the
inorder(root) three types of
routes del
B. PREORDER Traversal: tree
preorder(root)

C. Postorder Traversal:
postorder(root)

21
 Illustration 9: Program output.

3. Based on the traversals of the entered tree, create its representation.

graphic.

The tree built from the different traversals is presented.

program.

Illustration 10: Graphical representation of the entered tree.

4. Search the tree for the following elements: 5, 10, 20, 100.

We will look for the following elements: #Se makes the

Searched element: 5 --> call for the
search_data(root, 5) search function and
print("\nSearched element: 10 --> ",end=" ") himself enter the
search_data(root, 10) elements in the
Search element: 20 --> same program.
search_data(root, 8)
print("\nSearched element: 100 --> ", end=" ")
search_data(root, 20)

22
 Illustration 11: The output of the program is shown.

5. Remove the following values: 6, 20, 12.

The elements to be deleted are entered into the program. The 6 is a leaf node, so
that the suppression is direct. The 12 has a son on the left, in this case it is carried out
the replacement.

:::::::::::: THIRD OPERATION #Se makes the

(SUPPRESS):::::::::::::::: call a the
function delete
Remove the element: 6 y it they enter
remove(root, 6) the elements.
print("Remaining data --> ", end=" ")
inorder(root)

Remove the element: 20

remove(root, 20)
print('Remaining data --> ', end=' ')
inorder(root)

Print("\n\nRemove the element: 12")

remove(root, 12)
print("Remaining data --> ", end=" ")
inorder(root)

23
Illustration 12: The program output is shown.

24
 CHAPTER IV: APPLICATIONS

As we have seen in previous chapters, binary trees are structures

very useful when models are needed to represent processes where
they must make decisions or it is necessary to organize large amounts of information
efficiently.

Next, we will provide synthetic information about the areas where there are
they take advantage of the functions of binary search trees:

Binary Space Partition (BSP): is a very efficient method for calculating the
visibility relationships between a static group of polygons in 3D, viewed
from an arbitrary point of view. It is used in almost all games of
3D video to determine which objects should be lent.
Binary Handling: it is used in almost all high bandwidth routers to
store tables-routers.
Hash Trees: also known as Merkle tree, is a data structure
stratified which aims to relate each node to a root
only associated with this one. They are used in p2p programs.

Mounds: it is a complete binary tree that is used to manage

efficiently queues, widely used for programming in many
operating systems. It is also used in the search for algorithms
used in AI applications, such as robotics and video games.
Huffman Coding Tree (Chip Unit): is a particular type of code of
optimal prefix commonly used for lossless data compression
lossy, such as those used by .jpeg and .mp3 (file formats).
Treap: random data structure used in wireless networks and the
memory allocation.
GGM trees: It is used in cryptographic applications to generate a tree of
pseudo-random numbers.

25
Syntax tree - Built by compilers and (implicitly)
calculators to analyze expressions.
T-trees: are often used by databases that store the majority of
your data in memory.
Binary trees are used more frequently than n-ary trees
because these are generally more complex and do not offer an advantage in
As for speed.

26
 CONCLUSIONS

Trees are very important structures within languages of

programming, as they provide quite effective methods when needed
organizing information in large quantities. However, this type of tree is
really beneficial when it comes to self-balancing or complete trees, already
that the distribution of the data would facilitate search operations. This
means saving time and system resources, as many times we
we will encounter degenerate trees, that is, a parent node only has a
child node, which is why we would be closer to a linked list.

As we have seen in the applications chapter, a large part of programming

contemporary makes use of binary trees, as they are really useful for
the efficient use of information.

27
 BIBLIOGRAPHY

Cairo, O. and Guadarti, S. (2006). Data Structures. (3rd ed.). Mexico: MacGrawHill.

Vaca, R. (2011). Data structures and algorithms. Topic 4: trees. [Slides

of Power Point. Recovered the 7 of July, 2020, of
Unable to access external URLs or documents. Please provide the text you want translated.

VALIENTE, G. (2002). Algorithms on Trees and Graphs (1st ed.). Berlin: Springer.

Marzal, A. and Gracia, I. (2014). Introduction to Programming with Python (1st ed.)
Spain: Jaume University.

28