Tree structure

A tree structure makes it possible to organize the data in memory or on disc, in a logical and hierarchical way. It is a practical case of use of the algorithmic structure of tree. This organization makes more effective the consultation and the handling of the data stored. The most current uses are:

the tree structure of files, which is the hierarchical organization file S on a partition, and in certain cases of partitions between them, for example: virtual partitions (“logical readers”) in real partitions.
the Tri arborescent in memory
files in Sequential mode indexed

Use for management of the discs

At the base of a tree structure a repertory is called the root. This repertory can contain files and repertories, which themselves can contain the same thing.

If the files and the repertories are placed in a coherent way, the search for file is relatively easy and fast.

Various ways of linearizing a tree structure

The big problem is that a tree structure is often represented in the shape of a graphic tree and that the language and the traditional writing are linear. For a long time, various types of representation coexist, according to the method of course used and the scope of application.

Arite

More simply, arite indicates the number of arguments or children useful or necessary to a function or a relative. Thus in 10+20 , the addition (+) needs a term on the left (10) then of another on the right (20), its arite is thus of 2. In ABS (mavar) , the absolute value needs only one argument (mavar), its arite east is of 1. In Prolog, the clause father (Alain, Bernard). has an arite of 2 because the relation " pere" require a relative and fatally a child.

Arite can be fixed as it can be variable. Thus the operator * is of arite fixed with 2 in 90% of the data-processing languages, one writes 2*3 to express a calculation. On the other hand, in Lisp, one can write (* 2 3 4) to express 2*3*4 or (* 2 3 4 5) what is a variable arite.

Types of course

Prefixes

In this mechanism, the relative is put in first, then follow his children. The order/order is by front, the complementary elements then. See also the linguistic example VSO. Example: + 2 3

This notation is simple to include/understand for the human being and is programmed easily.

Infix

In this mechanism, the relative is inserted between his children. Mathematics and human logic proceed often thus. Subject Verb Complement. Example: 2 + 3

The big problem of infix is ambiguity and one must often resort to brackets. Thus 10+20*30 must you it be analyzed like (10+20) *30 or 10+ (20*30)? To raise part of the difficulties, there exists a priority of the operators in good number of languages.

Suffix

The relative is put after his children. This logic seems well not very human but it is very much used in data processing, pile, Forth, virtual machine Java, Postscript and others. Example: 2 3 +

This notation is difficult for the human being but very easy to set up from a data-processing point of view or automat.

Notation

; Arite fixes

Préfixe, arite fixes

+ 2 3
father Alain Bernard
eats cat mouse

Infixe, arite fixes

2 + 3
Alain est_le_père_de Bernard
cat eats mouse

Suffixe, arite fixes

2 3 +
Alain Bernard father
cat mouse eats

; Variable arite

Prefix, variable arite

(+ 2 3 4)
add (2,3,4)
printf (" %d %d %s" , N, m, T)
begin… end
add: 3 20 30 40 (one indicates the no. of arguments)
add 3 20 30 40 (the 1st argument indicates useful arite)

Infixe, variable arite

a-b (subtraction) - B (negative)
a*b (multiplication) *b (contained pointer in language C)

Suffixe, variable arite

(2 3 4 +)
marqueurpile 2 3 4 add
20 30 40 add: 3
20 30 40 3 add (the last argument indicates useful arite)

Another system

\ : to go down, indicates the 1st child
/: to go up, indicates the last child
-: to remain on the same level, the intermediate children, implicitly the 1st relative
|: arite 1, to go down then to go up (in the event of single child)
Example: 2*3*4+5*6 → préfixage - add \ mul \ 2-3/4 \ mul \ 5/6

See too

Graph theory

Random links: