W8.Tree, Tree_traversals.pdf

(1)

Trees

Kyunghan Lee

Networked Computing Lab (NXC Lab)

Department of Electrical and Computer Engineering

(2)

Introduction to Data Structures, ECE430.217, 2021 FALL SEOUL NATIONAL UNIVERSITY

Outline

□ In this topic, we will cover:

§ Definition of a tree data structure and its components

§ Concepts of:

• Root, internal, and leaf nodes

• Parents, children, and siblings

• Paths, path length, height, and depth

• Ancestors and descendants

• Ordered and unordered trees

• Subtrees

§ Examples

• XHTML and CSS

(3)

The Tree Data Structure

□ Trees are the first data structure different from what

you’ve seen in your first-year programming courses

(4)

Trees

□ A rooted tree data structure stores information in nodes

§ Similar to linked lists:

• There is a first node, or root

• Each node has multiple references to successors

• Each node, other than the root, has exactly one node pointing to it

(5)

Terminology

□ All nodes will have zero or more child nodes or children

§ I has three children: J, K and L

□ For all nodes other than the root node, there is one parent node

§ H is the parent I

(6)

Terminology: Degree

□ The degree of a node is defined as the number of its children: deg(I) = 3

□ Nodes with the same parent are siblings

§ J, K, and L are siblings

(7)

Terminology

□ Phylogenetic trees have nodes with degree 2 or 0:

https://en.wikipedia.org/wiki/Carnivoramorpha

(8)

Terminology: Nodes

□ Nodes with degree zero are also called leaf nodes

□ All other nodes are said to be internal nodes , that is,

they are internal to the tree

(9)

Terminology: Leaf Nodes

□ Leaf nodes:

(10)

Terminology: Internal Nodes

□ Internal nodes:

(11)

Terminology: Ordered Trees

□ These trees are equal if the order of the children is ignored

§ unordered trees

□ They are different if order is relevant (ordered trees)

(12)

Terminology: Root

□ The shape of a rooted tree gives a natural flow from the

root node, or just root

(13)

Terminology: Path

□ A path is a sequence of nodes (a 0 , a 1 , ..., a n ) where a k + 1 is a child of a k

§ The length of this path is n

□ e.g., the path (B, E, G)

has length 2

(14)

Terminology: Path

□ Paths of length 10 (11 nodes) and 4 (5 nodes)

Start of these paths

End of these paths

(15)

Terminology: Depth

□ For each node in a tree, there exists a unique path from the root node to that node

□ The length of this path is the depth of the node, e.g.,

§ E has depth 2

§ L has depth 3

(16)

Terminology: Depth

□ Nodes of depth up to 17

9

14 17 4

0

(17)

Terminology: Height

□ The height of a tree is defined as the maximum depth of any node within the tree

□ The height of a tree with one node is 0

§ Just the root node

□ For convenience, we define the height of the empty tree

to be –1

(18)

Terminology: Height

□ The height of this tree is 17

17

(19)

Terminology: Ancestor/Descendent

□ If a path exists from node a to node b:

§ a is an ancestor (parent) of b

§ b is a descendent (child) of a

□ Thus, a node is both an ancestor and a descendant of itself

§ We can add the adjective strict to exclude equality: a is a strict descendent of b if a is a descendant of b but a ≠ b

□ The root node is an ancestor of all nodes

(20)

Terminology: Ancestor/Descendent

□ The descendants of node B are B, C, D, E, F, and G:

□ The ancestors of node I are I, H, and A:

(21)

□ All descendants (including itself) of the indicated node

(22)

□ All ancestors (including itself) of the indicated node

(23)

Terminology: Subtree

□ Given any node a within a tree

with root r, the collection of a and all of its descendants is said to

be a subtree (of the tree) with

root a

(24)

Example: XHTML and CSS

□ The XML of XHTML has a tree structure

□ Cascading Style Sheets (CSS) use the tree structure to

modify the display of HTML

(25)

□ Consider the following XHTML document

<html>

<head>

<title>Hello World!</title>

</head>

<body>

<h1>This is a <u>Heading</u></h1>

<p>This is a paragraph with some

<u>underlined</u> text.</p>

</body>

</html>

(26)

Example: XHTML and CSS

□ Consider the following XHTML document

<html>

<head>

</head>

<body>

</body>

</html>

heading

underlining paragraph body of page

title

(27)

□ The nested tags define a tree rooted at the HTML tag

<html>

<head>

</head>

<body>

</body>

</html>

(28)

□ Web browsers render this tree as a web page

(29)

Example: XHTML and CSS

□ XML tags <tag>...</tag> must be nested

□ For example, to get the following effect:

1 2 3 4 5 6 7 8 9 you may use

□ You may not use:

(30)

□ Cascading Style Sheets (CSS) make use of this tree structure to describe how HTML should be displayed

§ For example:

h1 { color:blue; }

</style>

indicates all text/decorations descendant from an h1 header

should be blue

(31)

□ For example, this style renders as follows:

h1 { color:blue; }

</style>

(32)

h1 { color:blue; } u { color:red; }

</style>

(33)

□ Suppose you don’t want underlined items in headers (h1) to be red

§ More specifically, suppose you want any underlined text within paragraphs to be red

□ That is, you only want text marked as <u>text</u> to be

underlined if it is a descendant of a <p> tag

(34)

h1 { color:blue; } p u { color:red; }

</style>

(35)

□ You can read the second style

h1 { color:blue; } p u { color:red; }

</style>

as saying “text/decorations descendant from the

underlining tag (<u>) which itself is a descendant of a

paragraph tag should be coloured red”

(36)

Summary

□ In this topic, we have:

§ Introduced the terminology used for the tree data structure

§ Discussed various terms which may be used to describe the properties of a tree, including:

• root node, leaf node

• parent node, children, and siblings

• ordered trees

• paths, depth, and height

• ancestors, descendants, and subtrees

§ We looked at XHTML and CSS

[1] Donald E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3

^rd

Ed., Addison Wesley, 1997, § 2.2.1, p.238.

References

(37)

Abstract Trees

Kyunghan Lee

Department of Electrical and Computer Engineering

(38)

Outline

□ This topic discusses the concept of an abstract tree:

§ Hierarchical ordering

§ Description of an Abstract Tree/Hierarchy

§ Applications

§ Implementation

§ Local definitions

(39)

Abstract Trees

□ An abstract tree (or abstract hierarchy) does not restrict the number of nodes

Degree Nodes

0 D, F, G, J, K, L, M

1 C

2 A, B, E, H

3 I

(40)

Abstract Trees: Design

□ We implement an abstract tree or hierarchy by using a class that:

§ Stores a value

§ Stores a parent pointer

§ Stores children pointers in a linked-list

(41)

Implementation

□ The class definition would be:

(42)

Implementation

□ The tree with six nodes would be stored as follows:

(43)

Implementation

□ Much of the functionality is similar to that of the List

class:

(44)

Implementation

□ Much of the functionality is similar to that of the List

class:

(45)

Implementation

□ Accessing the n th child requires a for loop ( Q (n) ):

(46)

Implementation

□ Attaching a new object to become a child is similar to a

linked list:

(47)

Implementation

□ Suppose we want to find the size of a tree :

§ An empty tree has size 0, a tree with no children has size 1

§ Otherwise, the size is one plus the size of all the children

(48)

Implementation

□ Suppose we want to find the height of a tree :

§ An empty tree has height –1 and a tree with no children is height 0

§ Otherwise, the height is one plus the maximum height of any sub tree

(49)

Summary

□ In this topic, we have looked at one implementation of a general tree:

§ Store the value of each node

§ Store all the children in a linked list

§ Size and height of a tree

(50)

Tree Traversals

Kyunghan Lee

Department of Electrical and Computer Engineering Seoul National University

https://nxc.snu.ac.kr

[email protected]

(51)

Outline

□ This topic will cover tree traversals:

§ A means of visiting all the objects in a tree data structure

§ We will look at

• Breadth-first traversals

• Depth-first traversals

§ Applications

§ General guidelines

(52)

Background

□ All the objects stored in an array or linked list can be accessed sequentially

□ Question

§ How can we iterate through all the objects in a tree in a predictable and efficient manner?

§ Requirements: Q (n) run time and o(n) memory

(53)

Types of Traversals

□ We have already seen one traversal:

§ The breadth-first traversal visits all nodes at depth k before proceeding onto depth k + 1

§ Easy to implement using a queue

□ Another approach is to visit always go as deep as

possible before visiting other siblings: depth-first

traversals

(54)

Breadth-First Traversal

□ Breadth-first traversals visit all nodes at a given depth

§ Can be implemented using a queue

§ Run time is Q (n)

§ Memory is potentially expensive: maximum nodes at a given depth

§ Order: A B H C D G I E F J K

(55)

Breadth-First Traversal

□ The implementation was already discussed:

§ Create a queue and push the root node onto the queue

§ While the queue is not empty:

• Push all of its children of the front node onto the queue

• Pop the front node

(56)

Backtracking

□ To discuss depth-first traversals, we will define a backtracking algorithm for stepping through a tree:

§ At any node, we proceed to the first child that has not yet been visited

§ Or, if we have visited all the children, we backtrack to the parent and repeat this decision making process

□ We end once all the children

of the root are visited

(57)

Depth-first Traversal

□ We define such a path as a depth-first traversal

□ We note that each node could be visited twice in such a scheme

§ The first time the node is approached (before any children)

§ The last time it is approached (after all children)

(58)

Implementing depth-first traversals

□ Depth-first traversals can be implemented with recursion:

(59)

Implementing depth-first traversals

□ Performed on this tree, the output would be

<A>

<B>

<C>

<D>

</D>

</C>

<E>

<F>

</F>

<G>

</G>

</E>

</B>

<H>

<I>

<J>

</J>

<K>

</K>

(60)

Implementing depth-first traversals

□ Alternatively, we can use a stack:

§ Create a stack and push the root node onto the stack

§ While the stack is not empty:

• Pop the top node

• Push all of the children of that node to the top of the stack in reverse order

§ Run time is Q (n)

§ The objects on the stack are all unvisited siblings from the root to the current node

• If each node has a maximum of two children, the memory required is Q (h): the height of the tree

□ With the recursive implementation, the memory is Q (h)

(61)

Applications

□ Tree application: displaying information about directory structures and the files contained within

§ Finding the height of a tree

§ Printing a hierarchical structure

(62)

Height

□ The int height() const function is recursive in nature:

1. Before the children are traversed, we assume that the node has no children and we set the height to zero: h current = 0

2. In recursively traversing the children, each child returns its height h and we update the height as max(1 + h, h current ) 3. Once all children have been traversed, we return h current

□ When the root returns a value, that is the height of the

tree

(63)

Printing a Hierarchy

□ Consider the directory structure presented on the left—

how do we display this in the format on the right?

/

usr/

bin/

local/

var/

adm/

cron/

log/

(64)

Printing a Hierarchy

□ For a directory, we initialize a tab level at the root to 0

□ We then do:

1. Before the children are traversed, we must:

a) Indent an appropriate number of tabs, and

b) Print the name of the directory followed by a '/' 2. In recursively traversing the children:

a) A value of one plus the current tab level must be passed to the children, and

b) No information are passed back

3. Once all children have been traversed, we are finished

(65)

Summary

□ This topic covered two types of traversals:

§ Breadth-first traversals

§ Depth-first traversals

§ Applications

§ Determination of how to structure a depth-first traversal

(66)

Parental Trees

Kyunghan Lee

Department of Electrical and Computer Engineering Seoul National University

https://nxc.snu.ac.kr

[email protected]

(67)

Outline

□ In this topic, we will

§ Define a parental tree

§ Consider an efficient implementation

§ Converting a parental tree to a node-based tree

(68)

Definition

□ A parental tree is a tree where each node only keeps a reference to its parent node

§ Note, this definition is restricted to this course

§ Also known as a parent-pointer tree

(69)

Definition

□ This requires significantly less memory than our general

tree structure, as no data structure is required to track

the children

(70)

Implementation

□ A naïve implementation may also be node based:

template <typename Type>

class Parental_tree { private:

Type element;

Parental_tree *parent;

public:

// ...

};

(71)

Implementation

□ Instead, generate an array of size n and associate each entry with a node in the tree

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

A B C D E F G H I J K L M N O P Q R S T

(72)

Implementation

□ Store the index of the parent in each node

§ The root node, wherever it is, points to itself

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

0 0 0 0 0 2 2 2 3 3 4 4 4 4 5 5 10 12 12 15

(73)

Implementation

□ The memory requirements are quite small relative to our node-based implementation

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

0 0 0 0 0 2 2 2 3 3 4 4 4 4 5 5 10 12 12 15

(74)

Implementation

□ In a tree, only one node will point to itself

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

0 0 0 0 0 2 2 2 3 3 4 4 4 4 5 5 10 12 12 15

(75)

Converting to a Simple_tree structure

□ Converting the array-based parental tree structure back into a node-based general tree structure is relatively straight-

forward:

int const n = 20;

int parent_array[n] = { 0, 0, 0, 0, 0, 2, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 10, 12, 12, 15};

Simple_tree<Type> *root_node = nullptr;

Simple_tree<Type> array = new Simple_tree<Type> [n];

for ( int i = 0; i < n; ++i ) {

array[i] = new General_tree<Type>();

}

for ( int i = 0; i < n; ++i ) {

if ( parent_array[i] == i ) {

(76)

Looking ahead

□ The parental tree representation is used in numerous places:

§ Storing the critical path for the topological sorting of a directed acyclic graph

§ Prim’s algorithm: storing a minimum spanning trees of a weighted graph

§ Dijkstra’s algorithm: storing the minimum paths in a weighted

graph

(77)

Summary

□ This topic covered

§ The definition of a parental tree

§ Considered an efficient implementation

§ Considered converting back to a Simple_tree-based structure

§ Considered various uses

W8.Tree, Tree_traversals.pdf

Trees

• Root, internal, and leaf nodes

you’ve seen in your first-year programming courses

Terminology

Terminology: Degree

Terminology: Nodes

Terminology: Internal Nodes

root node, or just root

Terminology: Depth

□ Nodes of depth up to 17

0

Terminology: Height

Terminology: Ancestor/Descendent

Terminology: Subtree

□ Cascading Style Sheets (CSS) use the tree structure to

Example: XHTML and CSS

□ The nested tags define a tree rooted at the HTML tag

Example: XHTML and CSS

§ For example:

</style>

§ More specifically, suppose you want any underlined text within paragraphs to be red

h1 { color:blue; } p u { color:red; }

Summary

• paths, depth, and height

Outline

Abstract Trees: Design

□ The tree with six nodes would be stored as follows:

Implementation

Implementation

§ Store the value of each node

https://nxc.snu.ac.kr

Background

§ The breadth-first traversal visits all nodes at depth k before proceeding onto depth k + 1

§ Can be implemented using a queue

• Push all of its children of the front node onto the queue

§ Or, if we have visited all the children, we backtrack to the parent and repeat this decision making process

§ The last time it is approached (after all children)

Implementing depth-first traversals

§ Run time is Q (n)

§ Finding the height of a tree

2. In recursively traversing the children, each child returns its height h and we update the height as max(1 + h, h current ) 3. Once all children have been traversed, we return h current

Printing a Hierarchy

b) No information are passed back

Parental Trees

Definition

the children

Implementation

Implementation

Simple_tree<Type> *array = new Simple_tree<Type> *[n];

§ Dijkstra’s algorithm: storing the minimum paths in a weighted

Simple_tree<Type> array = new Simple_tree<Type> [n];