6.3. Vocabulário e Definições

Agora que demos uma olhada em alguns exemplos de árvores, nós iremos definir formalmente o que é uma árvore e seus componentes.

Um nó é uma parte fundamental de uma árvore. Ele pode ter um nome, algo que denominamos “chave”. Um nó também pode conter informação adicional. Nós chamamos essa informação adicional de “carga”. Embora a informação da carga não seja relevante para muitos algoritmos de árvores, ela costuma ser muito importante em aplicações que façam uso de árvores.

Aresta

Uma aresta é outra parte fundamental de uma árvore. Uma aresta conecta dois nós para mostrar que há uma relação entre eles. Cada nó (exceto a raiz) recebe precisamente uma única aresta de entrada vinda de outro nó, mas cada nó pode ter várias arestas de saída.

Raiz

A raiz de uma árvore é o único nó que não possui arestas de entrada. Na Figura Figure 2, / é a raiz da árvore.

Caminho

Um caminho é uma lista ordenada de nós que estão conectados por arestas. Por exemplo, Mamífero \(\rightarrow\) Carnivora \(\rightarrow\) Felidae \(rightarrow\) Felis \(\rightarrow\) Domestica é um caminho.

Filhos

Os nós de um conjunto \(c\) que possuem arestas de entrada que vêm de um mesmo nó são ditos filhos desse nó. Na Figura Figure 2, os nós log/, spool/ e yp/ são filhos do nó var/.

Pai

Um nó é considerado pai de todos os nós com os quais se conecta por meio de suas arestas de saída. Na Figure 2, o nó var/ é o pai dos nós log/, spool/ e yp/.

Sibling

Nodes in the tree that are children of the same parent are said to be siblings. The nodes etc/ and usr/ are siblings in the filesystem tree.

Subtree

A subtree is a set of nodes and edges comprised of a parent and all the descendants of that parent.

Leaf Node

A leaf node is a node that has no children. For example, Human and Chimpanzee are leaf nodes in Figure 1.

Level

The level of a node \(n\) is the number of edges on the path from the root node to \(n\). For example, the level of the Felis node in Figure 1 is five. By definition, the level of the root node is zero.

Height

The height of a tree is equal to the maximum level of any node in the tree. The height of the tree in Figure 2 is two.

With the basic vocabulary now defined, we can move on to a formal definition of a tree. In fact, we will provide two definitions of a tree. One definition involves nodes and edges. The second definition, which will prove to be very useful, is a recursive definition.

Definition One: A tree consists of a set of nodes and a set of edges that connect pairs of nodes. A tree has the following properties:

Figure 3 illustrates a tree that fits definition one. The arrowheads on the edges indicate the direction of the connection.

image

Figure 3: A Tree Consisting of a Set of Nodes and Edges

Definition Two: A tree is either empty or consists of a root and zero or more subtrees, each of which is also a tree. The root of each subtree is connected to the root of the parent tree by an edge. Figure 4 illustrates this recursive definition of a tree. Using the recursive definition of a tree, we know that the tree in Figure 4 has at least four nodes, since each of the triangles representing a subtree must have a root. It may have many more nodes than that, but we do not know unless we look deeper into the tree.

image

Figure 4: A recursive Definition of a tree

Next Section - 7. Graphs and Graph Algorithms