Trees
| Разделы | Иностранные языки |
| Тип | |
| Формат |
 Microsoft Word
|
| Язык | Английский |
| Загрузить архив: | |
| Файл: 240-1576.zip (6kb [zip], Скачиваний: 29) скачать |
Московский Государственный Университет
им. Циолковского
Студент : Заливнов Олег
Группа: 5МС-II-23
Лекция: 8
Тема : Деревья
TREES
Plan:
1) The tree presenation of data constructions.
2) What is tree?
a) definition
b) the terminology
c) types of trees
3) Tree applications in encoding systems.
Elementar datacan havedifferent types (string,integer
and so on).But if to talk about complex data construction-
it have no type.Complex data constructions consist of simple
data, and CDC are stored as data searching algorithm. and that
is why CDCarethe "selectors" - mechanism of searching and
accesing of data.
Such kindsof data as complex data constructions are need
to organize search.
We can describe CDC in different ways.For example we can
describe it in the way asit describedinthe 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 inbrackets(e.g. (Oleg) means the
elementary data construction).
The most powerful way of description a CDC is a tree.
NOW WHAT IS TREE ?
Tree isa connectedundirectedgraph withnosimple
circuits. So a tree cannot contain multile edges 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 path A-B-C-D is a loop;
Example 3 :
A ─────── B
│
D ────┼──── E ────── F
│
C
it is notthetree toobecausethis graphis not
connected;
Also we can select a special vertex and call it a root and
assign the direction to each edge.And we call suchtreea
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 uniquevertex A is called PARENT of vertex B if there
is a directed edge from A to B.When vertex A isparentof
vertex B, vertex B is called a CHILD of vertex A.
Vertices with the same parentare calledSIBLINGS.The
ANCESTORS ofa vertex other then th eroot are the vertices in
the path from root to this vertix, excluding the vertex itself
(that is itsparents,parents of its parents and so on...).
The DESCENDANTS of a vertex A are those vertices which haveA
as an ancestor.
If a vertex of a tree has no children it is calle aLEAF.
If a vertex has children it is called INTERNAL VERTEX.
If A is a vertex in a tree,the subgraph of a treewhich
consists ofAand all its descendants and all edges incident
to these descendants is called a SUBTREE with 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 rootedtree iscalled an M-ARY TREE if every internal
vertex has no more then M children.The tree is called a FULL
M-ARY tree ifeveryinternal vertex has exactly M children.
And if M = 2 then such M-ary tree is called 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 root C.
Also we can order the children of each internal vertexin
the rooted tree.Such trees are called ORDERED ROOTED TREES.
In such trees children are drawn in order from left to right.
In an ordered binary tree,if an internal vertex has two
children, first is called LEFT CHILD,second is calledRIGHT
CHILD.
If a subtree has a left child of a vertex as arootthen
such subtree is called LEFT SUBTREE OF A VERTEX.If a root of
a subtree is a right child ofa vertexthenwe callsuch
subtree RIGHT SUBTREE OF A VERTEX.
We willcall the LEVEL of a vertex V in a rooted tree the
length of the unique path from the root to the vertex V.
The level of root equal 0.
The HEIGHTofa rooted 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 about trees. I'lljust name
them :
1) An undefined graph is a tree if and only if there is a
unique simple path between any two vertices.
2) A tree with N vertices has N-1 edges.
3) A full m-ary tree with i internal vertices contains
n = mi + 1 vertices.
4) A fullm-arytree with
(a) n verticeshas i=(n-1)/m internal vertices
and l = [(m - 1)n + 1]/m leaves.
(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) internal vertices.
5) Thereare atmostm^h leavesin any m-ary tree of
height = h.
There are several ways of drawing a tree.
First one to draw a trer as adiagram waspresentedin
previous examples, but there are some more ways to do it.
Second wayof representing a tree is a brackets
representation. Inthis waytheinternal 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 are equalent.
There isone veryimportantapplication oftreesin
encoding systems.
The task of encoding system is to enter codes of wordsor
frase so that message could be recoded. The main requirement
is the ability to synonymously restore the original textwith
the help of codes.
So for examplewe havea binary messageandacode
vocabulary. I must say that not every vocabulary can be a code
vacabulary. The requirements to it are the following :
1) it must be full
2) it must be prefix vocabulary,it means thatinsuch
vocabularu no one word begins from another.
So our task is to divide message into symbolsandencode
them.
Example 10 :
We have the message : 000011001
and the prefix full vocabulary : 1 E
01 L
001 G
000 O
And so this message can be divided into four symbols :
000 01 1 001
and then can be encoded as OLEG.
It is not difficult to mention that this vocabulary can be
presented as a binary tree.
Then we can mention that every binarytreerepresents a
full,prefix coding vocabulary.
So in such way trees are used in encoding systems.