Áàçà çíàíèé ñòóäåíòà. Ðåôåðàò, êóðñîâàÿ, êîíòðîëüíàÿ, äèïëîì íà çàêàç

êóðñîâûå,êîíòðîëüíûå,äèïëîìû,ðåôåðàòû

Trees — Èíîñòðàííûå ÿçûêè

                 Ìîñêîâñêèé Ãîñóäàðñòâåííûé Óíèâåðñèòåò

                            èì. Öèîëêîâñêîãî

         Ñòóäåíò : Çàëèâíîâ Îëåã

         Ãðóïïà  : 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 ─── 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.

            (c) l leaves has n=(ml-1)/(m-1) vertices and

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

     full,prefix coding vocabulary.

         So in such way trees are used in encoding systems.

                 Ìîñêîâñêèé Ãîñóäàðñòâåííûé Óíèâåðñèòåò                             èì. Öèîëêîâñêîãî          Ñòóäåíò : Çàëèâíîâ Îëåã          Ãðóïïà  : 5ÌÑ-II-23          Ëåêöèÿ  : 8          Òåìà    : Äåðåâüÿ                        

 

 

 

Âíèìàíèå! Ïðåäñòàâëåííûé Ðåôåðàò íàõîäèòñÿ â îòêðûòîì äîñòóïå â ñåòè Èíòåðíåò, è óæå íåîäíîêðàòíî ñäàâàëñÿ, âîçìîæíî, äàæå â òâîåì ó÷åáíîì çàâåäåíèè.
Ñîâåòóåì íå ðèñêîâàòü. Óçíàé, ñêîëüêî ñòîèò àáñîëþòíî óíèêàëüíûé Ðåôåðàò ïî òâîåé òåìå:

Íîâîñòè îáðàçîâàíèÿ è íàóêè

Çàêàçàòü óíèêàëüíóþ ðàáîòó

Ñâîè ñäàííûå ñòóäåí÷åñêèå ðàáîòû

ïðèñûëàéòå íàì íà e-mail

Client@Stud-Baza.ru