Welcome to ECE 250 Algorithms and Data Structures

The tree data structure 1 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 The tree data structure 2 Trees

4.1.1 A rooted tree data structure stores information in nodes Similar to linked lists: There is a first node, or root Each node has variable number of references to successors Each node, other than the root, has exactly one node pointing to it The tree data structure 3 Terminology

4.1.1.1 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 The tree data structure 4 Terminology 4.1.1.1

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 The tree data structure 5 4.1.1.1 Terminology Phylogenetic trees have nodes with degree 2 or 0:

The tree data structure 6 4.1.1.1 Terminology 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 The tree data structure 7

4.1.1.1 Leaf nodes: Terminology The tree data structure 8 4.1.1.1 Internal nodes:

Terminology The tree data structure 9 Terminology 4.1.1.2 These trees are equal if the order of the children is ignored unordered trees They are different if order is relevant (ordered trees) We will usually examine ordered trees (linear orders)

In a hierarchical ordering, order is not relevant The tree data structure 10 4.1.1.3 Terminology The shape of a rooted tree gives a natural flow from the root node, or just root The tree data structure 11

Terminology 4.1.1.3 A path is a sequence of nodes (a0, a1, ..., an) where ak + 1 is a child of ak is The length of this path is n E.g., the path (B, E, G) has length 2 The tree data structure

12 Terminology 4.1.1.3 Paths of length 10 (11 nodes) and 4 (5 nodes) Start of these paths End of these paths The tree data structure 13

Terminology 4.1.1.3 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 The tree data structure 14

Terminology 4.1.1.3 Nodes of depth up to 17 0 4 9 14 17

The tree data structure 15 Terminology 4.1.1.3 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

The tree data structure 16 4.1.1.3 Terminology The height of this tree is 17 17 The tree data structure 17

Terminology 4.1.1.4 If a path exists from node a to node b: a is an ancestor of b b is a descendent 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

The tree data structure 18 4.1.1.4 Terminology The descendants of node B are B, C, D, E, F, and G: The ancestors of node I are I, H, and A: The tree data structure 19

4.1.1.4 Terminology All descendants (including itself) of the indicated node The tree data structure 20 4.1.1.4 Terminology All ancestors (including itself) of the indicated node

The tree data structure 21 4.1.2 Terminology Another approach to a tree is to define the tree recursively: A degree-0 node is a tree A node with degree n is a tree if it has n children and all of its children are disjoint trees (i.e., with no intersecting nodes) 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 The tree data structure 22 4.1.3 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

The tree data structure 23 4.1.3 Example: XHTML and CSS Consider the following XHTML document Hello World!

This is a Heading

This is a paragraph with some

underlined text.

The tree data structure 24 Example: XHTML and CSS 4.1.3 Consider the following XHTML document title

Hello World!

This is a Heading

heading body of page

This is a paragraph with some underlined text.

underlining

paragraph The tree data structure 25 4.1.3 Example: XHTML and CSS The nested tags define a tree rooted at the HTML tag Hello World!

This is a Heading

This is a paragraph with some underlined text.

The tree data structure 26 4.1.3 Example: XHTML and CSS

Web browsers render this tree as a web page The tree data structure 27 4.1.3 Example: XHTML and CSS XML tags ... must be nested For example, to get the following effect: 123456789 you may use 1 2 3 4 5 6 7 8 9 You may not use:

1 2 3 4 5 6 7 8 9 The tree data structure 28 4.1.3.1 Example: XHTML and CSS Cascading Style Sheets (CSS) make use of this tree structure to describe how HTML should be displayed For example:

indicates all text/decorations descendant from an h1 header should be blue The tree data structure 29 4.1.3.1 Example: XHTML and CSS For example, this style renders as follows:

The tree data structure 30 4.1.3.1 Example: XHTML and CSS For example, this style renders as follows:

The tree data structure 31 4.1.3.1 Example: XHTML and CSS Suppose you dont 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 text to be

underlined if it is a descendant of a

tag The tree data structure 32 4.1.3.1 Example: XHTML and CSS For example, this style renders as follows:

The tree data structure 33 4.1.3.1 Example: XHTML and CSS You can read the second style

as saying text/decorations descendant from the underlining tag () which itself is a descendant of a paragraph tag should be coloured red The tree data structure 34 Example: XML 4.1.3.1 In general, any XML can be represented as a tree All XML tools make use of this feature Parsers convert XML into an internal tree structure

XML transformation languages manipulate the tree structure E.g., XMLT The tree data structure 35 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 The tree data structure 36

References [1] Donald E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd Ed., Addison Wesley, 1997, 2.2.1, p.238. The tree data structure 37 Usage Notes These slides are made publicly available on the web for anyone to

use If you choose to use them, or a part thereof, for a course at another institution, I ask only three things: that you inform me that you are using the slides, that you acknowledge my work, and that you alert me of any mistakes which I made or changes which you make, and allow me the option of incorporating such changes (with an acknowledgment) in my set of slides Sincerely, Douglas Wilhelm Harder, MMath [email protected]

Recently Viewed Presentations

  • Applied Science SIL 2019 AIM: To be fully

    Applied Science SIL 2019 AIM: To be fully

    Be able to label a prokaryotic cell and explain the functions of the cell parts. Be able to label a eukaryotic cell . and. explain the functions of the cell parts. Be able to explain how organelles work together to...
  • Elements of Design

    Elements of Design

    ./fashion/FMBS10Design.ppt. Retrieved 9/17/210 Elements are the building blocks of design. Color: Most exciting element of design Shape: Overall outline of a garment, it is the form or silhouette. Line: Distinct, elongated mark as if drawn by a pencil or pen....
  • Control Unit - SNU

    Control Unit - SNU

    Title: Control Unit Author: Jaejin Lee Last modified by: Sang Lyul Min Document presentation format: 사용자 지정 Other titles: Gill Sans ヒラギノ角ゴ ProN W3 Arial Georgia Bold ヒラギノ明朝 ProN W6 Georgia ヒラギノ明朝 ProN W3 맑은 고딕 굴림 Helvetica Courier New...
  • The Northwest of Canada in 1800s

    The Northwest of Canada in 1800s

    The Fur Trade & Expansion of the West The Northwest of Canada in 1800s HBC (1670) vs. NWC (1779) Hudson Bay Company Founded in 1670 Radisson and Groseillier's explored beyond New France Returned with furs - pitched to King Charles...
  • Introduction To Rational Rose - La Salle University

    Introduction To Rational Rose - La Salle University

    ROSE = Rational Object Oriented Software Engineering Rational Rose is a set of visual modeling tools for development of object oriented software. Rose uses the UML to provide graphical methods for non-programmers wanting to model business processes as well as...
  • Management, Leadership, Employee Empowerment

    Management, Leadership, Employee Empowerment

    Vivian Mun, Ed.D. Accreditation 2012. Accreditation 2012. What is a rubric? A rubric is a . scoring tool . that lists the criteria for a piece of work, or "what counts" (for example, purpose, organization, details, voice, and mechanics are...
  • Computational Solid State Chemistry 2

    Computational Solid State Chemistry 2

    Modelling defects and dopants in ionic crystals. Calculation of energies of formation of defects in crystals. Modelling ion migration. Doping: substitution and solution energies. SSI-18 Workshop 3 July 2011
  • Chapter 1 Introduction: Matter and Measurement

    Chapter 1 Introduction: Matter and Measurement

    Arial MS Pゴシック Times New Roman Symbol Blank Presentation Chapter 1 Introduction: Units of Measurement Chemistry Matter Matter Matter Matter States of Matter Properties and Changes of Matter Types of Properties Types of Properties Types of Changes Units of Measurement...