Trees

Московский Государственный ниверситет

им. Циолковского

Студент : Заливнов Олег

Групп : МС-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

│

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 ─── 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 if there

is a directed edge from A to B. When vertex Aа isа parentа of

vertex B, vertex B is called a CHILD of vertex A.

Vertices with the same parentа areа calledа SIBLINGS. The

ANCESTORS ofа a vertex other then th eroot are the vertices in

аthe path 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 those vertices which haveа A

as an ancestor.

If a vertex of a tree has no children it is calle aа LEAF.

If a vertex has children it is called INTERNAL VERTEX.

If A is a vertex in a tree, the subgraph of a treeа which

consists ofа Aа and 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 rootedа treeа isа called an M-ARY TREE if every internal

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 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 vertexа in

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 calledа RIGHT

CHILD.

If a subtree has a left child of a vertex as aа rootа then

such subtree is called LEFT SUBTREE OF A VERTEX. 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 tree the

length of the unique path from the root to the vertex V.

The level of root equal 0.

The HEIGHTа ofа a 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'llа justа 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а fullа m-aryа treeа with

(a) n verticesа hasа 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.

i = (l-1)/(m-1) internal vertices.

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 more ways 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 are equalent.

There isа oneа veryа importantа applicationа ofа treesа in

encoding systems.

The task of encoding system is to enter codes of wordsа or

frase soа that message could be recoded. The main requirement

is the ability to synonymously restore the original textа with

the help of codes.

So for exampleа weа haveа a аbinaryа messageа andа aа code

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а thatа inа such

vocabularu no one word begins from another.

So our task is to divide message into symbolsа andа encode

them.

Example 10 :

We have the message : 11001

and the prefix full vocabulary : 1 E

01 L

001 G

And so this message can be divided into four symbols :

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 binaryа treeа representsа a

full,prefix coding vocabulary.

So in such way trees are used in encoding systems.

Blog

Trees