CS202: Discrete Structures

In the next two sections, we will discuss rooted trees. Our primary foci will be on general rooted trees and on a special case, ordered binary trees.

10.3.1 Definition and Terminology

Figure 10.3.1 A Rooted Tree

List 10.3.2 Informal Definition and Terminology

What differentiates rooted trees from undirected trees is that a rooted tree contains a distinguished vertex, called the root. Consider the tree in Figure 10.3.1. Vertex A has been designated the root of the tree. If we choose any other vertex in the tree, such as M , we know that there is a unique path from A to M . The vertices on this path, (A, D, K, M), are described in genealogical terms:

• M is a child of K (so is L)
• K is M 's parent.
• A, D, and K are M 's ancestors.
• D, K , and M are descendants of A.

These genealogical relationships are often easier to visualize if the tree is rewritten so that children are positioned below their parents, as in Figure 10.3.3.

With this format, it is easy to see that each vertex in the tree can be thought of as the root of a tree that contains, in addition to itself, all of its descendants. For example, D is the root of a tree that contains D, K , L, and M. Furthermore, K is the root of a tree that contains K, L, and M . Finally, L and M are roots of trees that contain only themselves. From this observation, we can give a formal definition of a rooted tree.

Figure 10.3.3 A Rooted Tree, redrawn

Definition 10.3.4 Rooted Tree.

(a) Basis: A tree with no vertices is a rooted tree (the empty tree). (b) A single vertex with no children is a rooted tree.

(c) Recursion: Let T₁, T₂, . . . , T_r, r ≥ 1, be disjoint rooted trees with roots v₁, v₂, . . ., v_r, respectively, and let v₀ be a vertex that does not belong to any of these trees. Then a rooted tree, rooted at v₀, is obtained by making v₀ the parent of the vertices v₁, v₂, . . ., and v_r. We call T₁, T₂, . . . , T_rsubtrees of the larger tree.

The level of a vertex of a rooted tree is the number of edges that separate the vertex from the root. The level of the root is zero. The depth of a tree is the maximum level of the vertices in the tree. The depth of a tree in Figure 10.3.3 is three, which is the level of the vertices L and M . The vertices E, F , G, H , I , J , and K have level two. B, C , and D are at level one and A has level zero.

Example 10.3.5 A Decision Tree. Figure 2.1.2 is a rooted tree with Start as the root. It is an example of what is called a decision tree.

Example 10.3.6 Tree Structure of Data. One of the keys to working with large amounts of information is to organize it in a consistent, logical way. A data structure is a scheme for organizing data. A simple example of a data structure might be the information a college admissions department might keep on their applicants. Items might look something like this:

ApplicantItem = (FirstName, MiddleInitial, LastName, StreetAddress, City, State, Zip, HomePhone, CellPhone, EmailAddress, HighSchool, Major, ApplicationPaid, MathSAT, VerbalSAT, Recommendation1, Recommendation2, Recommendation3)

This structure is called a "flat file".

A spreadsheet can be used to arrange data in this way. Although a "flat file" structure is often adequate, there are advantages to clustering some the information. For example the applicant information might be broken into four parts: name, contact information, high school, and application data:

ApplicantItem = ((FirstName, MiddleInitial, LastName), ((StreetAddress, City, State, Zip), (HomePhone, CellPhone), EmailAddress), HighSchool, (Major, ApplicationPaid, (MathSAT, VerbalSAT), (Recommendation1, Recommendation2, Recommendation3))

The first item in each ApplicantItem is a list (FirstName, MiddleInitial, LastName), with each item in that list being a single field of the original flat file. The third item is simply the single high school item from the flat file. The application data is a list and one of its items, is itself a list with the recommendation data for each recommendation the applicant has. The organization of this data can be visualized with a rooted tree such as the one in Figure 10.3.7.

Figure 10.3.7 Applicant Data in a Rooted Tree

In general, you can represent a data item, T, as a rooted tree with T as the root and a subtree for each field. Those fields that are more than just one item are roots of further subtrees, while individual items have no further children in the tree.

10.3.2 Kruskal's Algorithm

An alternate algorithm for constructing a minimal spanning tree uses a forest of rooted trees. First we will describe the algorithm in its simplest terms. Afterward, we will describe how rooted trees are used to implement the algorithm. Finally, we will demonstrate the SageMath implementation of the algorithm. In all versions of this algorithm, assume that G = (V, E, w) is a weighted undirected graph with |V| = m and |E| = n.

Algorithm 10.3.8 Kruskal's Algorithm - Informal Version.

(1) Sort the edges of G in ascending order according to weight. That is,

i ≤ j ⇔ w (e_j) ≤ w (e_j).

(2) Go down the list from Step 1 and add edges to a set (initially empty) of edges so that the set does not form a cycle. When an edge that would create a cycle is encountered, ignore it. Continue examining edges until either m − 1 edges have been selected or you have come to the end of the edge list. If m − 1 edges are selected, these edges make up a minimal spanning tree for G. If fewer than m − 1 edges are selected, G is not connected.

Step 1 can be accomplished using one of any number of standard sorting routines. Using the most efficient sorting routine, the time required to perform this step is proportional to n log n. The second step of the algorithm, also of n log n time complexity, is the one that uses a forest of rooted trees to test for whether an edge should be added to the spanning set.

Algorithm 10.3.9 Kruskal's Algorithm.

(1) Sort the edges of G in ascending order according to weight. That is,

i ≤ j ⇔ w(e_j) ≤ w(e_j).

(2) (a) Initialize each vertex in V to be the root of its own rooted tree.

(b) Go down the list of edges until either a spanning tree is completed or the edge list has been exhausted. For each edge e = {v₁, v₂}, we can determine whether e can be added to the spanning set without forming a cycle by determining whether the root of v₁'s tree is equal to the root of v₂'s tree. If the two roots are equal, then ignore e. If the roots are different, then we can add e to the spanning set. In addition, we merge the trees that v₁and v₂belong to. This is accomplished by either making v₁′s root the parent of v₂′s root or vice versa.

Note 10.3.10

(a) Since we start the Kruskal's algorithm with m trees and each addition of an edge decreases the number of trees by one, we end the algorithm with one rooted tree, provided a spanning tree exists.

(b) The rooted tree that we develop in the algorithm is not the spanning tree itself.

10.3.3 SageMath Note - Implementation of Kruskal's Algorithm

Kruskal's algorithm has been implemented in Sage. We illustrate how the spanning tree for a weighted graph in can be generated. First, we create such a graph.

We will create a graph using a list of triples of the form (vertex, vertex, label). The weighted method tells Sage to consider the labels as weights

edges=[(1, 2, 4) , (2 , 8 , 4) , (3 , 8 , 4) , (4 , 7 , 5) , (6 , 8 ,
5) , (1 , 3 , 6) , (1 , 7 , 6) , (4 , 5 , 6) , (5 , 10 , 9) , (2 , 10 ,
7) , (4 , 6 , 7) , (2 , 4 , 8) , (1 ,8 , 9) , (1 , 9 , 9) , (5 , 6 ,
9) , (1 , 10 , 10) , (2 , 9 , 10) , (4 , 9 , 10) , (5 , 9 , 10) , (6 ,
9, 10) ]
G = Graph ( edges )
G . weighted ( True )
G . graphplot ( edge_labels = True , save_pos = True ) . show ()

Figure 10.3.11 Weighed graph, SageMath output

Next, we load the kruskal function and use it to generate the list of edges in a spanning tree of G.

from s a g e
. g r a p h s . s p a n n i n g _ t r e e i m p o r t k r u s k a l
E = k r u s k a l ( G , c h e c k = T r u e ) ; E

[( 1 , 2 , 4 ) , (1 , 7 , 6 ) , (1 , 9 , 9 ) , (2 , 8 , 4 ) , (2 , 10 , 7 ) , (3 , 8 , 4 ) , (4 , 5 , 6 ) , (4 , 7 , 5 ) , (6 , 8 , 5 ) ]

To see the resulting tree with the same embedding as G, we generate a graph from the spanning tree edges. Next, we set the positions of the vertices to be the same as in the graph. Finally, we plot the tree.

T = G r a p h ( E )
T . s e t _ p o s ( G . g e t _ p o s ( ) )
T . g r a p h p l o t ( e d g e _ l a b e l s = T r u e ) . s h o w ( )

Figure 10.3.12 Spanning tree, SageMath output

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.