Реферат: Trees

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

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

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

        Группа  : 5МС-II-23

        Лекция  : 8

         Тема    : Деревья



         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



         it is not  the  tree too  because  this graph  is   not


         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


         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


         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


         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


         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


         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.

еще рефераты
Еще работы по иностранным языкам