Transcript 1 - FER

Algorithms and data structures
26.3.2016.
Protected by http://creativecommons.org/licenses/by-nc-sa/3.0/hr/
Creative Commons

You are free to:
share — copy and redistribute the material in any medium or format
 adapt — remix, transform, and build upon the material


Under the following terms:



Attribution — You must give appropriate credit, provide a link to the license, and
indicate if changes were made. You may do so in any reasonable manner, but
not in any way that suggests the licensor endorses you or your use.
NonCommercial — You may not use the material for commercial purposes.
ShareAlike — If you remix, transform, or build upon the material, you must
distribute your contributions under the same license as the original.
No additional restrictions — You may not apply legal terms or technological
measures that legally restrict others from doing anything the license permits.
Notices:
You do not have to comply with the license for elements of the material in the public domain or where your use is
permitted by an applicable exception or limitation.
No warranties are given. The license may not give you all of the permissions necessary for your intended use. For
example, other rights such as publicity, privacy, or moral rights may limit how you use the material.
Text copied from http://creativecommons.org/licenses/by-nc-sa/3.0/
Algorithms and data structures, FER
26.3.2016.
2 / 31
Trees
26.3.2016.
Tree properties


Tree is a finite set of nodes with properties:

There is a special node called root

The other nodes are divided among k disjunctive subsets T1..Tk, where
each of them is a tree. T1..Tk are called subtrees
Example:
a
b
d
h
Algorithms and data structures, FER
c
e
i
f
g
j
26.3.2016.
k
4 / 31
Basic terms - I


a is the root of the tree
Degree of the node a is 2 (degree is the
number of subtrees originating
from a node, e.g. the node c
is of degree 3)


a
b
d
h
c
e
i
f
g
j
k
The set {h,i,e,f,j,k} is the set of terminal nodes (leaves)
Roots of node subtrees are children of that node (e.g. the nodes
e,f,g are children of c), and that node is called parent (e.g. g is the
parent of j).

Similar terms are used for other relationships (grandparent, siblings,
ancestors)
Algorithms and data structures, FER
26.3.2016.
5 / 31
Basic terms - II



a
Degree of a tree is the maximum degree of
b
c
a node in the tree, in this example 3
d
e
f
g
Level of a node is determined
from the definition that the root is on h
i
j
k
the level 1, and that the levels
of node children from the level k are k+1
Depth of a tree equals to the maximum level of a node in that tree
Algorithms and data structures, FER
26.3.2016.
6 / 31
Recursive trees in nature
The largest dragon tree in the world...
Algorithms and data structures, FER
26.3.2016.
7 / 31
Binary tree - I

Binary tree is a tree consisting of none, one or more nodes of the
second degree
There can be left and/or right subtree of each node
 The terminology introduced for trees applies also to the binary trees

a
Skewed tree
b
Algorithms and data structures, FER
c
b
c
d
a
Complete tree
d
h
e
f
g
i
26.3.2016.
8 / 31
Binary tree - II
Level
1
1
2
2
4
3
2k-1
k
k+1
3
2k
2k-1+1
2k+1
Algorithms and data structures, FER
6
i/2
i
2i
2i+1
26.3.2016.
i+1
... 2k-2
7
2k-1
...
9 / 31
Binary tree - III

It follows from the binary tree definition:
 The maximum number of nodes on level k is 2k-1
 The maximum number of nodes in a binary tree of depth k is 2k 1 for k>0
 A tree of depth k with 2k -1 nodes is called full binary tree
 A binary tree of depth k with n nodes is complete iff its nodes
correspond to the nodes of a full binary tree of depth k numbered
from 1 to n
–
As a consequence, the difference of levels between leaves of a
complete tree cannot be larger than one.
Algorithms and data structures, FER
26.3.2016.
10 / 31
Binary tree – static structure array representation

A complete binary tree can be simply represented with one
dimensional array, without any data for linking, obeying the rules for
trees


For simplicity of expressions, array index starts at 1
Difficult insertion and deletion of nodes is the problem in array
representation of the tree, as it may require displacement of many
nodes
Skewed tree
Complete tree
Algorithms and data structures, FER
a b
c
d
a b c d e f g h i
26.3.2016.
e
j
k
l m n o p
11 / 31
Skewed and complete tree
Skewed tree a
Complete tree a
Algorithms and data structures, FER
b
c
d
b c d e f g h i
26.3.2016.
e
j
k
l m n o p
12 / 31
Binary tree – rules for array representation
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16
a b c d e f g h i j k l m n o p
Rules for a complete binary tree with n nodes, for the i-th node are:
Complete tree


parent (i)= i/2 for i 1; when i=1, node i is the root and has no
parents

left_child (i)=2*i if 2*i n;when 2*i>n the node i has no left child
right_child (i)=2*i+1 if 2*i+1n; when 2*i+1>n the node i has no
right child
All binary trees might be represented in this way, but the memory use would
not be efficient
 The worst case are skewed trees using only k locations out of 2k -1
locations allocated for that tree


Algorithms and data structures, FER
26.3.2016.
13 / 31
Binary tree - dynamic structure representation

The problem is solved using the structure with pointers


This structure is often used and it satisfies the majority of requirements
A pointer at the parent can be added
struct node{
type data;
struct node *left_child;
struct node *right_child;
/* if required: */
struct node *parent;
};
Algorithms and data structures, FER
26.3.2016.
a
14 / 31
Skewed tree
a
root
b
c
d
Algorithms and data structures, FER
26.3.2016.
15 / 31
Complete tree
a
root
b
d
h
Algorithms and data structures, FER
c
e
f
g
i
26.3.2016.
16 / 31
k-trees

A natural generalisation of binary trees are the k-trees
 k is the tree degree, k>2, with the same representation
possibilities

General trees, having different degrees, can be
transformed into binary trees
 It results with shorter and more efficient algorithms and with less
memory requirements
Algorithms and data structures, FER
26.3.2016.
17 / 31
Search tree

A search tree can be formed (sorted, ordered tree) according to the
key value stored in each node. Insertion of a new node starts with
the search from the root of the tree. The key value of the new node
is compared with already stored key values:
 If the key of the new node is smaller than the key of the stored
node, the comparisons continue along the left subtree
 If the key of the new node is larger than the key of the stored
node, the comparisons continue along the right subtree
 If the stored node has no subtree in the required direction, the
new node becomes a child of the stored node
 SortiranoStablo (SortedTree)
Algorithms and data structures, FER
26.3.2016.
18 / 31
Tree – element addition
If the tree is empty, return the new
node (write it for exercise!)
struct node* add(struct node* node, type elem) {
if (node == NULL) {
return (NewNode(elem));
Else, descend recursively along
}
the tree, to the left or right
else {
if (elem <= node->data)
What if the
node->left = add (node->left, elem);
element is
else
already
node->right = add (node->right, elem);
stored?
return (node);
}
}
Algorithms and data structures, FER
Return the unchanged pointer to the node
26.3.2016.
19 / 31
Searching the tree
Basic case – empty tree, the searched
value not found, return 0
int search (struct node* node, int looked_for) {
if (node == NULL) {
return 0;
Return1 if found
}
else {
if (looked_for == node->data) return 1;
else {
Else, descend along the corresponding subtree
if (looked_for < node->data)
return (serch(node->left, looked_for));
else return (search(node->right, looked_for));
}
}
}
Algorithms and data structures, FER
26.3.2016.
21 / 31
Tree traversal

There are 3 standard ways of tree traversal, ensuring that every
node has been visited





left subtree → root → right subtree
root → left subtree → right subtree
left subtree → right subtree → root
These are recursive procedures reaching the tree leaves; then the
returns from recursion present progressing towards the tree root
An example for inorder from right to left: SortiranoStablo


inorder:
preorder:
postorder:
right subtree → root → left subtree
(SortedTree)
Retrieval of data from the tree with calculations
 ProsjekUStablu (AverageInTree)
Algorithms and data structures, FER
26.3.2016.
22 / 31
Tree – leaf deletion

The simplest case of deletion is deleting a leaf, e.g. 6.
5
5
3
1
3
7
4
6
1
Delete
7
4
6
Algorithms and data structures, FER
26.3.2016.
Release
23 / 31
Tree – deletion of a node with single child

Deleting a node with single child is also simple, e.g. 7
5
5
4
1
7
3
4
Delete
1
6
7
Release
3
6
Algorithms and data structures, FER
26.3.2016.
24 / 31
Tree – deletion of a node with two children

More complex is deletion of a node with two children, e.g. 5
5
3
1
3
Delete
6
Release
4
7
4
5
7
1
6
 BrisanjeCvoraStabla (DeletionOfNodeInTree)
Algorithms and data structures, FER
26.3.2016.
25 / 31
Exercises

Write the programs to:
a.
b.
c.
d.
e.
print out the number of nodes in a tree
print the tree’s depth
print the values of the smallest and of the largest integer stored in
the nodes of a tree
construct and print out a mirror copy of a given tree
for two given trees check whether they are identical or not
Algorithms and data structures, FER
26.3.2016.
26 / 31
Exercises

In a formatted sequential file students on disk there are
records with the following contents:
–
–
–


ID
Family name and name
Grades for 10 courses
8 digits
40+1 characters
10*1 digits
Write a program to create a new unformatted direct access file index. To
enable quick retrieval according to the ID, file records are stored as an
ordered binary tree.
For a given ID, the ordinal number, and the new grade value write a
program that keeps updating the grade as long as the entered ID is greater
than zero.
Algorithms and data structures, FER
26.3.2016.
27 / 31
Exercises

Write a function to print out the elements of a memory resident
already existent sorted binary tree with contents in nodes:
Article price (integer)
 Article name (15+1 characters)

The tree is sorted according to the article price; left node cheaper,
right node more expensive. Input argument is the pointer to the root
of the tree. Print out should be ordered from the cheapest to the
most expensive article.
Algorithms and data structures, FER
26.3.2016.
28 / 31
Exercises

The sequence of data is stored into a binary tree:
12, 15, 5, 3, 7, 2, 18, 11
a)
b)
c)
d)
e)
Draw the sorted binary tree (left smaller, right bigger), if the tree was filled
in in the sequence the data are listed
Reorder the input data to cause a worst case
Sketch the binary tree for the best case
What is the a priori execution time for retrieval of a node in case b)
What is the a priori execution time for retrieval of a node in case c)
Algorithms and data structures, FER
26.3.2016.
29 / 31
Exercises


The codes of length 10+1 characters are stored in a memory
resident binary tree. Write a function to check the presence of a
given code. Input arguments are the pointer to the tree root and a
given code. Output is 0 if the code is not present, and 1 if it is. A
node contains the code and pointers to the left and the right child.
ID numbers (integer and key) and the persons’ weights (float) are
stored in a memory resident sorted binary tree (left smaller, right
bigger). Write a function to calculate the total weights of the
recorded persons. The function prototype is:
float weight(struct node* root);
Algorithms and data structures, FER
26.3.2016.
30 / 31
Exercises

In a memory resident binary tree, there are stored persons’ IDs
(integer) and weights (float). Write a function to calculate the
average weight of the recorded persons, the maximum weight and
the number of recorded persons. The function prototype is:
float average(struct node *root, float
*weight, int *number, float *maxweight);

In a memory resident binary tree, there are stored the codes
(integer) and the names of courses (15+1 characters). The names of
the courses should be printed out so that the tree structure is visible.
Level of a node should correspond to the distance from the left
margin. The function prototype is:
void write (node *root, int level);
Algorithms and data structures, FER
26.3.2016.
31 / 31