íÏÓËÏ×ÓËÉÊ çÏÓÕÄÁÒÓÔ×ÅÎÎÙÊ õÎÉ×ÅÒÓÉÔÅÔ ÉÍ. ãÉÏÌËÏ×ÓËÏÇÏ
ššš óÔÕÄÅÎÔ : úÁÌÉ×ÎÏ× ïÌÅÇ
ššš çÒÕÐÐÁš : 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 dataš canš haveš different 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šššššš CDCš areš the "selectors" - mechanism of searching and
accesing of data.
ššš Such kindsš of 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 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 a CDC is a tree.
ššš NOW WHAT IS TREE ?
ššš Tree isš aš connectedš undirectedš graphš withš noš simple 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š notš theš treeš tooš becauseš thisš graphš isšš not connected;
ššš Also we can select a special vertex and call it a root and assign the direction to each edge.š And we call suchš treeš a ROOTED tree.
ššš Example 4 :
šššššš A ---- Bššššš ššššššš A ---