Московский Государственный Университет
им. Циолковского
Студент:Заливнов Олег
Группа : 5МС-II-23
Лекция : 8
Тема : Деревья
TREES
Plan:
1) The tree presenation of dataconstructions.
2) What is tree?
a) definition
b) the terminology
c) types of trees
3) Tree applications in encodingsystems.
Elementar data can have different types(string,integer
and so on). But if to talk about complex dataconstruction -
it have no type. Complex data constructions consist of simple
data, and CDC are stored as data searchingalgorithm. and that
is why CDC are the «selectors» — mechanism ofsearching and
accesing of data.
Such kinds of data as complex data constructions areneed
to organize search.
We can describe CDC in differentways. For example we can
describe it in the way as it described in the programming
language Cobol :
1 University
2 (first fac.)
2 (second fac.)
2 (third fac.)
2 (fourth fac.)
2 fifth fac.
3 PM
4 (Pasha)
4 (Andrey)
3 IT
4 (Zhenia)
4 (Olga)
3 MS
4 (Oleg)
4 (Helen)
4 (Artem).
Where the word in brackets (e.g. (Oleg) means the
elementary data construction).
The most powerful way of description aCDC is a tree.
NOW WHAT IS TREE ?
Tree is a connected undirected graph with no simple
circuits. So a tree cannot contain multileedges or loops, and
so tree is a simple graph.
Example 1 :
D─────────── A────────────C
│ │ │
│ │ │
│ B ────F │
│ │
E H──── G ───── I───── J
this is a tree ;
Example 2 :
E────────── A────────── B
│ │ │
│ │ │
F D───────────C
it is not the tree, because pathA-B-C-D is a loop;
Example 3 :
A─────── B
│
D────┼──── E────── F
│
C
it is not the tree too because this graph is not
connected;
Also we can select a special vertexand call it a root and
assign the direction to each edge. And we call such tree a
ROOTED tree.
Example 4 :
A ────B A ───B A ─── B
│ │
│ │
D ──── C──── G D ───C ─── G D ───C ─── G
│ │ │ │ │ │
│ │
F H F H F H
a)Unrooted tree . b) Rooted tree c) Rooted tree
with root A . with root C .
The unique vertex A is called PARENT of vertex B ifthere
is a directed edge from A to B. When vertex A is parent of
vertex B, vertex B is called a CHILD ofvertex A.
Vertices with the same parent are called SIBLINGS. The
ANCESTORS of a vertex other then th eroot are the verticesin
thepath from root to this vertix, excluding the vertex itself
(that is its parents, parents of its parents and so on...).
The DESCENDANTS of a vertex A are thosevertices which have A
as an ancestor.
If a vertex of a tree has no childrenit is calle a LEAF.
If a vertex has children it is calledINTERNAL VERTEX.
If A is a vertex in a tree, the subgraph of a tree which
consists of A andall its descendants and all edges incident
to these descendants is called a SUBTREEwith a root A.
Example 5 :
A ─── B
│
D ───C ─── G D ───C ─── G
│ │ │ │
F H F H
(a) Tree T (b) Subtree T1
A — is a root
A — is a parent of B and C.
C — is a child of A
C and B — are siblings
C — is an ancestor of H
H — is an descendant of A
F — is a leaf
C — is an internal vertex
A rooted tree is called an M-ARY TREE if everyinternal
vertex has no more then M children. The tree is called a FULL
M-ARY tree if every internal vertex has exactly M children.
And if M = 2 then such M-ary tree iscalled BINARY TREE.
Example 6 :
A ───B A
│
│
D ─── C─── G D ───C ─── G ─── E
│ │ │ │
F H F H
a) 3-ary tree b) full 3-ary tree
with root A. with root C.
C ───G ── B
│ │
F H
c) binary tree
with rootC.
Also we can order the children of eachinternal vertex in
the rooted tree. Such trees are calledORDERED ROOTED TREES.
In such trees children are drawn in orderfrom left to right.
In an ordered binary tree, if aninternal vertex has two
children, first is called LEFT CHILD, second is called RIGHT
CHILD.
If a subtree has a left child of avertex as a root then
such subtree is called LEFT SUBTREE OF AVERTEX. If a root of
a subtree is a right child of a vertex then we call such
subtree RIGHT SUBTREE OF A VERTEX.
We will call the LEVEL of a vertex V in a rooted treethe
length of the unique path from the root tothe vertex V.
The level of root equal 0.
The HEIGHT of arooted tree is the length of its longest
path from the root to any vertex.
Example 7 :
D ─── C─── G
│ │
F H
The root is vertex C.
The level of F is 1.
The height of the tree is 2.
There are several theoremes abouttrees. I'll just name
them :
1) An undefined graph is a tree if and only if there is a
unique simple path between any twovertices.
2) A tree with N vertices has N-1edges.
3) A full m-ary tree with i internalvertices contains
n = mi + 1 vertices.
4) A full m-ary tree with
(a) n vertices has i = (n-1)/m internal vertices
and l = [(m — 1)n + 1]/mleaves.
(b) i internal vertices has n =mi+1 vertices and
l = (m-1)i + 1 leaves.
(c) l leaves has n=(ml-1)/(m-1)vertices and
i = (l-1)/(m-1) internalvertices.
5) There are at most m^h leaves in any m-ary tree of
height = h.
There are several ways of drawing a tree.
First one to draw a trer as a diagram was presented in
previous examples, but there are some moreways to do it.
Second way of representing a tree is a brackets
representation. In this way the internal brackets present
sub-trees.
Example 8: (C is a root)
D ─── C─── G
│ │ ====== (C,(D,F,G,(H)))
F H
The third way is to present tree as a consistent numbered
sections.
Example 9 :
D ─── C─── G 1. C
│ │ ========== 1.1. D
1.2. F
F H 1.3. G
1.3.1. H
All the ways of presenting trees areequalent.
There is one very important application of trees in
encoding systems.
The task of encoding system is toenter codes of words or
frase so that message could be recoded. The main requirement
is the ability to synonymously restore theoriginal text with
the help of codes.
So for example we have a binary message and a code
vocabulary. I must say that not everyvocabulary can be a code
vacabulary. The requirements to it are thefollowing :
1) it must be full
2) it must be prefix vocabulary, it means that in such
vocabularu no one word begins fromanother.
So our task is to divide message intosymbols and encode
them.
Example 10 :
We have the message: 000011001
and the prefix full vocabulary : 1 E
01 L
001 G
000 O
And sothis message can be divided into four symbols :
000 01 1001
and thencan be encoded as OLEG.
It is notdifficult to mention that this vocabulary can be
presented as abinary tree.
Then wecan mention that every binary tree represents a
full,prefixcoding vocabulary.
So in suchway trees are used in encoding systems.