data structures.pdf

Data Structures and Algorithms CC 204 1. What is a data structure? a) A type of algorithm b) A way to organize and store data c) A method for sorting data d) A programming language 2. Which of the following is an example of a linear data structure? a) Tree b) Graph c) Linked List d) Hash Table ...

Data Structures and Algorithms CC 204 1. What is a data structure? a) A type of algorithm b) A way to organize and store data c) A method for sorting data d) A programming language 2. Which of the following is an example of a linear data structure? a) Tree b) Graph c) Linked List d) Hash Table 3. What is an algorithm? a) A programming language b) A step-by-step procedure to solve a problem c) A type of data structure d) A computer program 4. Which data structure uses the Last-In, First-Out (LIFO) principle? a) Queue b) Stack c) Array d) Linked List 5. Which of these is NOT a common operation performed on data structures? a) Insertion b) Deletion c) Compilation d) Traversal 6. Which data structure is used to store a sequence of elements that can be accessed by their index? a) Queue b) Array c) Stack d) Tree 7. Which data structure uses the First-In, First-Out (FIFO) principle? a) Queue b) Stack c) Heap d) Tree 8. What is a recursive algorithm? a) An algorithm that repeats itself indefinitely b) An algorithm that calls itself with a smaller input c) An algorithm that only works on sorted data d) An algorithm that runs in a loop 9. Which data structure is typically used for implementing a priority queue? a) Stack b) Heap c) Array d) Linked List 10. Which sorting algorithm repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order? a) Quick Sort b) Bubble Sort c) Merge Sort d) Heap Sort 11. Which of the following is an example of a non-linear data structure? a) Array b) Linked List c) Tree d) Queue 12. What is the primary difference between a stack and a queue? a) Stack is LIFO, Queue is FIFO b) Stack is FIFO, Queue is LIFO c) Stack allows duplicates, Queue does not d) Stack is static, Queue is dynamic 13. In a binary search algorithm, the array must be: a) Unsorted b) Sorted c) Partially sorted d) Circular 14. What is a hash function used for in a hash table? a) To convert data into a fixed-size value b) To sort data c) To traverse data d) To encrypt data 15. Which sorting algorithm is considered the simplest but least efficient for large datasets? a) Quick Sort b) Merge Sort c) Bubble Sort d) Heap Sort Introduction to Python  Overview · History · Installing & Running Python · Names & Assignment · Sequences types: Lists, Tuples, and Strings · Mutability  Brief History of Python · Invented in the Netherlands, early 90s by Guido van Rossum · Named after Monty Python · Open sourced from the beginning · Considered a scripting language, but is much more · Scalable, object oriented and functional from the beginning · Used by Google from the beginning  Python’s Benevolent Dictator For Life “Python is an experiment in how much freedom program-mers need. Too much freedom and nobody can read another's code; too little and expressive-ness is endangered.” - Guido van Rossum http://docs.python.org / The Python tutorial is good! Running Python  The Python Interpreter · Typical Python implementations offer both an interpreter and compiler · Interactive interface to Python with a read-eval-print loop [finin@linux2 ~]$ python Python 2.4.3 (#1, Jan 14 2008, 18:32:40) [GCC 4.1.2 20070626 (Red Hat 4.1.2-14)] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> def square(x):... return x * x...  Installing · Python is pre-installed on most Unix systems, including Linux and MAC OS X · The pre-installed version may not be the most recent one (2.6.2 and 3.1.1 as of Sept 09) · Download from http://python.org/download/ · Python comes with a large library of standard modules · There are several options for an IDE  IDLE Development Environment · IDLE is an Integrated DeveLopment Environ-ment for Python, typically used on Windows · Multi-window text editor with syntax highlighting, auto- completion, smart indent and other. · Python shell with syntax highlighting. · Integrated debugger with stepping, persis- tent breakpoints,  Editing Python in Emacs · Emacs python-mode has good support for editing Python, enabled enabled by default for.py files · Features: completion, symbol help, eldoc, and inferior interpreter shell, etc. Running Interactively on UNIX On Unix… % python >>> 3+3 6 · Python prompts with ‘>>>’. · To exit Python (not Idle): In Unix, type CONTROL-D In Windows, type CONTROL-Z + Evaluate exit() Running Programs on UNIX · Call python program via the python interpreter % python fact.py · Make a python file directly executable by Adding the appropriate path to your python interpreter as the first line of your file #!/usr/bin/python Making the file executable % chmod a+x fact.py  Example ‘script’: fact.py #! /usr/bin/python def fact(x): """Returns the factorial of its argument, assumed to be a point""" if x === 0: return 1 return x * fact(x - 1) print print ’N fact(N)’ print "---------" for n in range(10): print n, fact(n)  Python Scripts · When you call a python program from the command line the interpreter evaluates each expression in the file · Familiar mechanisms are used to provide command line arguments and/or redirect input and output · Python also has mechanisms to allow a python program to act both as a script and as a module to be imported and used by another python program  Example of a Script #! /usr/bin/python """ reads text from standard input and outputs any email addresses it finds, one to a line. """ import re from sys import stdin # a regular expression ~ for a valid email address pat = re.compile(r'[-\w][-.\w]*@[-\w][- \w.]+[a-zA-Z]{2,4}') for line in stdin.readlines(): for address in pat.findall(line):  results python> python email0.py  Getting a unique, sorted list import re from sys import stdin pat = re.compile(r'[-\w][-.\w]*@[-\w][- \w.]+[a-zA-Z]{2,4}’) # found is an initially empty set (a list w/o duplicates) found = set( ) for line in stdin.readlines(): for address in pat.findall(line): found.add(address) # sorted() takes a sequence, returns a sorted list of its elements for address in sorted(found): print address  results python> python email2.py  Simple functions: ex.py #factorial done recursively and iteratively def fact1(n): ans = 1 for i in range(2,n): ans = ans * n return ans def fact2(n): if n < 1: return 1 else: return n * fact2(n - 1)  Simple functions: ex.py 671> python Python 2.5.2 … >>> import ex >>> ex.fact1(6) 1296 >>> ex.fact2(200) 78865786736479050355236321393218507…000000L >>> ex.fact1 >>> fact1 Traceback (most recent call last): File "", line 1, in NameError: name 'fact1' is not defined >>> The Basics A Code Sample (in IDLE) x = 34 - 23 # A comment. y = “Hello” # Another one. z = 3.45 if z == 3.45 or y == “Hello”: x = x + 1 y = y + “ World” # String concat. print x = 12 print y = Hello World  Enough to Understand the Code · Indentation matters to code meaning Block structure indicated by indentation · First assignment to a variable creates it Variable types don’t need to be declared. Python figures out the variable types on its own. · Assignment is = and comparison is == · For numbers + - * / % are as  Basic Datatypes · Integers (default for numbers) z = 5 / 2 # Answer 2, integer division · Floats x = 3.456 · Strings Can use “” or ‘’ to specify with “abc” == ‘abc’ Unmatched can occur within the string: “matt’s” Use triple double-quotes for multi- line strings or strings than contain both ‘ and “ inside of  Whitespace Whitespace is meaningful in Python: especially indentation and placement of newlines ·Use a newline to end a line of code Use \ when must go to next line prematurely ·No braces {} to mark blocks of code, use consistent indentation instead First line with less indentation is outside of the block First line with more indentation starts a nested block  Comments · Start comments with #, rest of line is ignored · Can include a “documentation string” as the first line of a new function or class you define · Development environments, debugger, and other tools use it: it’s good style to include one def fact(n): “““fact(n) assumes n is a positive integer and returns facorial of n.””” assert(n>0)  Assignment · Binding a variable in Python means setting a name to hold a reference to some object Assignment creates references, not copies · Names in Python do not have an intrinsic type, objects have types Python determines the type of the reference automatically based on what data is assigned to it · You create a name the first time it appears on the left side of an assignment expression: x = 3 · A reference is deleted via garbage collection after any names bound to it have passed out of scope  Naming Rules · Names are case sensitive and cannot start with a number. They can contain letters, numbers, and underscores. bob Bob _bob _2_bob_ bob_2 BoB · There are some reserved words: and, assert, break, class, continue, def, del, elif, else, except, exec, finally, for, from, global, if, import, in, is, lambda, not, or, pass, print, raise, return, try, while  Naming conventions The Python community has these recommend-ed naming conventions ·joined_lower for functions, methods and, attributes ·joined_lower or ALL_CAPS for constants ·StudlyCaps for classes ·camelCase only to conform to pre- existing conventions ·Attributes: interface, _internal, __private  Assignment ·You can assign to multiple names at the same time >>> x, y = 2, 3 >>> x 2 >>> y 3 This makes it easy to swap values >>> x, y = y, x ·Assignments can be chained >>> a = b = x = 2  Accessing Non-Existent Name Accessing a name before it’s been properly created (by placing it on the left side of an assignment), raises an error >>> y Traceback (most recent call last): File "", line 1, in -toplevel- y NameError: name ‘y' is not defined >>> y = 3 >>> y 3 Sequence types: Tuples, Lists, and Strings  Sequence Types 1.Tuple: (‘john’, 32, [CMSC]) · A simple immutable ordered sequence of items · Items can be of mixed types, including collection types 2.Strings: “John Smith” Immutable Conceptually very much like a tuple 3.List: [1, 2, ‘john’, (‘up’, ‘down’)] · Mutable ordered sequence of  Similar Syntax · All three sequence types (tuples, strings, and lists) share much of the same syntax and functionality. · Key difference: Tuples and strings are immutable Lists are mutable · The operations shown in this section can be applied to all sequence types  Sequence Types 1 · Define tuples using parentheses and commas >>> tp = (23, ‘abc’, 4.56, (2,3), ‘def’) · Define lists are using square brackets and commas >>> li = [“abc”, 34, 4.34, 23] · Define strings using quotes (“, ‘, or “““). >>> st = “Hello World” >>> st = ‘Hello World’ >>> st = “““This is a multi-line string that uses triple quotes.”””  Sequence Types 2 · Access individual members of a tuple, list, or string using square bracket “array” notation · Note that all are 0 based… >>> tu = (23, ‘abc’, 4.56, (2,3), ‘def’) >>> tu # Second item in the tuple. ‘abc’ >>> li = [“abc”, 34, 4.34, 23] >>> li # Second item in the list. 34 >>> st = “Hello World” >>> st # Second character in string. ‘e’  Positive and negative indices >>> t = (23, ‘abc’, 4.56, (2,3), ‘def’) Positive index: count from the left, starting with 0 >>> t ‘abc’ Negative index: count from right, starting with –1 >>> t[-3] 4.56  Slicing: return copy of a subset >>> t = (23, ‘abc’, 4.56, (2,3), ‘def’) Return a copy of the container with a subset of the original members. Start copying at the first index, and stop copying before second. >>> t[1:4] (‘abc’, 4.56, (2,3)) Negative indices count from end >>> t[1:-1] (‘abc’, 4.56, (2,3))  Slicing: return copy of a =subset >>> t = (23, ‘abc’, 4.56, (2,3), ‘def’) Omit first index to make copy starting from beginning of the container >>> t[:2] (23, ‘abc’) Omit second index to make copy starting at first index and going to end >>> t[2:] (4.56, (2,3), ‘def’)  Copying the Whole Sequence · [ : ] makes a copy of an entire sequence >>> t[:] (23, ‘abc’, 4.56, (2,3), ‘def’) · Note the difference between these two lines for mutable sequences >>> l2 = l1 # Both refer to 1 ref, # changing one affects both >>> l2 = l1[:] # Independent copies, two refs  The ‘in’ Operator · Boolean test whether a value is inside a container: >>> t = [1, 2, 4, 5] >>> 3 in t False >>> 4 in t True >>> 4 not in t False · For strings, tests for substrings >>> a = 'abcde' >>> 'c' in a True >>> 'cd' in a True >>> 'ac' in a False · Be careful: the in keyword is also used in the syntax of for loops and list  The + Operator The + operator produces a new tuple, list, or string whose value is the concatenation of its arguments. >>> (1, 2, 3) + (4, 5, 6) (1, 2, 3, 4, 5, 6) >>> [1, 2, 3] + [4, 5, 6] [1, 2, 3, 4, 5, 6] >>> “Hello” + “ ” + “World” ‘Hello World’  The * Operator · The * operator produces a new tuple, list, or string that “repeats” the original content. >>> (1, 2, 3) * 3 (1, 2, 3, 1, 2, 3, 1, 2, 3) >>> [1, 2, 3] * 3 [1, 2, 3, 1, 2, 3, 1, 2, 3] >>> “Hello” * 3 ‘HelloHelloHello’ Mutability: Tuples vs. Lists  Lists are mutable >>> li = [‘abc’, 23, 4.34, 23] >>> li = 45 >>> li [‘abc’, 45, 4.34, 23] · We can change lists in place. · Name li still points to the same memory reference when we’re done.  Tuples are immutable >>> t = (23, ‘abc’, 4.56, (2,3), ‘def’) >>> t = 3.14 Traceback (most recent call last): File "", line 1, in -toplevel- tu = 3.14 TypeError: object doesn't support item assignment ·You can’t change a tuple. ·You can make a fresh tuple and assign its reference to a previously used name. >>> t = (23, ‘abc’, 3.14, (2,3), ‘def’) ·The immutability of tuples means they’re faster than lists. Operations on Lists Only >>> li = [1, 11, 3, 4, 5] >>> li.append(‘a’) # Note the method syntax >>> li [1, 11, 3, 4, 5, ‘a’] >>> li.insert(2, ‘i’) >>>li [1, 11, ‘i’, 3, 4, 5, ‘a’]  The extend method vs + · + creates a fresh list with a new memory ref · extend operates on list li in place. >>> li.extend([9, 8, 7]) >>> li [1, 2, ‘i’, 3, 4, 5, ‘a’, 9, 8, 7] · Potentially confusing: extend takes a list as an argument. append takes a singleton as an argument. >>> li.append([10, 11, 12]) >>> li Operations on Lists Only Lists have many methods, including index, count, remove, reverse, sort >>> li = [‘a’, ‘b’, ‘c’, ‘b’] >>> li.index(‘b’) # index of 1 st occurrence 1 >>> li.count(‘b’) # number of occurrences 2 >>> li.remove(‘b’) # remove 1 st occurrence >>> li [‘a’, ‘c’, ‘b’] Operations on Lists Only >>> li = [5, 2, 6, 8] >>> li.reverse() # reverse the list *in place* >>> li [8, 6, 2, 5] >>> li.sort() # sort the list *in place* >>> li [2, 5, 6, 8] >>> li.sort(some_function) # sort in place using user-defined comparison  Tuple details · The comma is the tuple creation operator, not parens >>> 1, (1,) · Python shows parens for clarity (best practice) >>> (1,) (1,) · Don't forget the comma! >>> (1) 1 · Trailing comma only required for singletons others · Empty tuples have a special syntactic form  Summary: Tuples vs. Lists · Lists slower but more powerful than tuples Lists can be modified, and they have lots of handy operations and mehtods Tuples are immutable and have fewer features · To convert between tuples and lists use the list() and tuple() functions: li = list(tu) tu = tuple(li)  Stack and Queue 70  What is a Stack Stack of Books 71  Stacks What is a Stack? – A stack is a data structure of ordered items such that items can be inserted and removed only at one end. 72  Stacks What can we do with a stack? – push - place an item on the stack – peek - Look at the item on top of the stack, but do not remove it – pop - Look at the item on top of the stack and remove it 73  Stacks A stack is a LIFO (Last- In/First-Out) data structure A stack is sometimes also called a pushdown store. What are some applications of stacks? – Program execution – Parsing – Evaluating 74 postfix expressions  Stacks Problem: – What happens if we try to pop an item off the stack when the stack is empty? This is called a stack underflow. The pop method needs some way of telling us that this has happened. In java we use the java.util.EmptyStackException 75 Interface IStack Interface Istack { boolean empty(); void push(char c); char pop(); char peek(); }  Using a IStack A balance of braces. – (()) balanced braces – ()(()()))) not balanced braces How can you use Istack to check a brace is balanced or not? When you implement the above requirement, you ignore the implementation details of Istack.  Implementing a Stack There are two ways we can implement a stack: – Using an array – Using a linked list 78  Implementing a Stack Implementing a stack using an array is fairly easy. – The bottom of the stack is at data – The top of the stack is at data[numItems-1] – push onto the stack at data[numItems] – pop off of the stack at 79 data[numItems-1]  Implementing a Stack Implementing a stack using a linked list isn’t that bad either… – Store the items in the stack in a linked list – The top of the stack is the head node, the bottom of the stack is the end of the list – push by adding to the front of the 80list  Reversing a Word We can use a stack to reverse the letters in a word. How? 81  Reversing a Word Read each letter in the word and push it onto the stack When you reach the end of the word, pop the letters off the stack and print them out. 82 What is a Queue? 83  Queues What is a queue? – A data structure of ordered items such that items can be inserted only at one end and removed at the other end. Example – A line at the supermarket 84  Queues What can we do with a queue? – Enqueue - Add an item to the queue – Dequeue - Remove an item from the queue These ops are also called insert and getFront in order to simplify things. 85  Queues A queue is called a FIFO (First in-First out) data structure. What are some applications of queues? – Round-robin scheduling in processors – Input/Output processing – Queueing of packets for 86  Implementing a Queue Just like a stack, we can implementing a queue in two ways: – Using an array – Using a linked list 87  Implementing a Queue Using an array to implement a queue is significantly harder than using an array to implement a stack. Why? – Unlike a stack, where we add and remove at the same end, in a queue we add to one end and remove from the other. 88  Implementing a Queue There are two options for implementing a queue using an array: Option 1: – Enqueue at data and shift all of the rest of the items in the array down to make room. – Dequeue from data[numItems-1] 89  Implementing a Queue Option 2 – Enqueue at data[rear+1] – Dequeue at data[front] – The rear variable always contains the index of the last item in the queue. – The front variable always contains the index of the first item in the queue. – When we reach the end of the array, 90 wrap around to the front Implementing a Queue // option 2 sketch of insert insert(Object item) { if(manyItems == 0) front = rear = 0; else rear = (rear + 1) mod size; data[rear] 91 = item; Implementing a Queue // option 2 sketch of getFront Object getFront() { answer = data[front]; front = (front + 1) mod size; manyItems--; 92 return answer  Implementing a Queue Implementing a queue using a linked list is still easy: – Front of the queue is stored as the head node of the linked list, rear of the queue is stored as the tail node. – Enqueue by adding to the end of the list – Dequeue by removing from the front 93 of the list.  The tree data structure 94 The Tree Data Structure  The tree data structure 95 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 96 The Tree Data Structure Trees are the first data structure different from what you’ve seen in your first-year programming courses http://xkcd.com/71/  The tree data structure 97 4.1.1 Trees 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 98 4.1.1.1 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  The tree data structure 99 4.1.1.1 Terminology 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 100 4.1.1.1 Terminology Phylogenetic trees have nodes with degree 2 or 0:  The tree data structure 101 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 102 4.1.1.1 Terminology Leaf nodes:  The tree data structure 103 4.1.1.1 Terminology Internal nodes:  The tree data structure 104 4.1.1.2 Terminology 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 105 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 106 4.1.1.3 Terminology 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 107 4.1.1.3 Terminology Paths of length 10 (11 nodes) and 4 (5 nodes) Start of these paths End of these paths  The tree data structure 108 4.1.1.3 Terminology 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 109 4.1.1.3 Terminology Nodes of depth up to 17 0 4 9 14 17  The tree data structure 110 4.1.1.3 Terminology 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  The tree data structure 111 4.1.1.3 Terminology The height of this tree is 17 17  The tree data structure 112 4.1.1.4 Terminology 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 113 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 114 4.1.1.4 Terminology All descendants (including itself) of the indicated node  The tree data structure 115 4.1.1.4 Terminology All ancestors (including itself) of the indicated node  The tree data structure 116 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 117 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 118 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 119 4.1.3 Example: XHTML and CSS Consider the following XHTML document ti tl HelloWorld!e headi ng This is a Heading body of page This is a paragraph with some underlined text. underlining paragra ph  The tree data structure 120 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 121 4.1.3 Example: XHTML and CSS Web browsers render this tree as a web page  The tree data structure 122 4.1.3 Example: XHTML and CSS XML tags... must be nested For example, to get the following effect: 1 2 3 4 5 6 7 8 9 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 123 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: h1 { color:blue; } indicates all text/decorations descendant from an h1 header should be blue  The tree data structure 124 4.1.3.1 Example: XHTML and CSS For example, this style renders as follows: h1 { color:blue; }  The tree data structure 125 4.1.3.1 Example: XHTML and CSS For example, this style renders as follows: h1 { color:blue; } u { color:red; }  The tree data structure 126 4.1.3.1 Example: XHTML and CSS 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 text to be underlined if it is a descendant of a tag  The tree data structure 127 4.1.3.1 Example: XHTML and CSS For example, this style renders as follows: h1 { color:blue; } p u { color:red; }  The tree data structure 128 4.1.3.1 Example: XHTML and CSS You can read the second style h1 { color:blue; } p u { color:red; } 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 129 4.1.3.1 Example: XML 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 130 4.1.3.1 MathML: x2 + y2 = z2 x2+ y2 =z2 x2 y2 z2 x^2+y^2 = z^2  The tree data structure 131 4.1.3.1 MathML: x2 + y2 = z2 The tree structure for the same MathML expression is  The tree data structure 132 4.1.3.1 MathML: x2 + y2 = z2 Why use 500 characters to describe the equation x2 + y2 = z2 which, after all, is only twelve characters (counting spaces)? The root contains three children, each different codings of: – How it should look (presentation), – What it means mathematically (content), and – A translation to a specific language (Maple)  The tree data structure 133 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 134 References Donald E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd Ed., Addison Wesley, 1997, §2.2.1, p.238.