Trees — страница 2

  • Просмотров 1018
  • Скачиваний 190
  • Размер файла 6
    Кб

─── 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.