Trees Make Money Fast! Stock Fraud 05/01/24 04:40 Ponzi Scheme

Trees Make Money Fast! Stock Fraud 05/01/24 04:40 Ponzi Scheme Trees Bank Robbery 1

Outline and Reading Tree ADT (§2.3.1) Preorder and postorder traversals (§2.3.2) BinaryTree ADT (§2.3.3) Inorder traversal (§2.3.3) Euler Tour traversal (§2.3.3) Template method pattern Data structures for trees (§2.3.4) Java implementation (http://jdsl.org) 05/01/24 04:40 Trees 2

What is a Tree In computer science, a tree is an abstract model of a hierarchical structure A tree consists of nodes with a parentchild relation Applications: Computers”R”Us Sales US International Organization charts File systems Europe Programming environments 05/01/24 04:40 Manufacturing Trees Asia Laptops R&D Desktops Canada 3

Tree Terminology Root: node without parent (A) Internal node: node with at least one child (A, B, C, F) External node (a.k.a. leaf ): node without children (E, I, J, K, G, H, D) Ancestors of a node: parent, grandparent, grand-grandparent, etc. Depth of a node: number of ancestors E Height of a tree: maximum depth of any node (3) Descendant of a node: child, I grandchild, grand-grandchild, etc. 05/01/24 04:40 Trees Subtree: tree consisting of a node and its descendants A B C F J G D H K subtree4

Tree ADT We use positions to abstract nodes Generic methods: Query methods: integer size() boolean isEmpty() objectIterator elements() positionIterator positions() Accessor methods: Update methods: swapElements(p, q) object replaceElement(p, o) Additional update methods may be defined by data structures implementing the Tree ADT position root() position parent(p) positionIterator children(p) 05/01/24 04:40 boolean isInternal(p) boolean isExternal(p) boolean isRoot(p) Trees 5

Preorder Traversal A traversal visits the nodes of a tree in a systematic manner In a preorder traversal, a node is visited before its descendants Application: print a structured document 1 Make Money Fast! 2 5 1. Motivations 9 2. Methods 3 4 1.1 Greed 1.2 Avidity 05/01/24 04:40 Algorithm preOrder(v) visit(v) for each child w of v preorder (w) 6 7 2.1 Stock Fraud Trees 2.2 Ponzi Scheme References 8 2.3 Bank Robbery 6

Postorder Traversal In a postorder traversal, a node is visited after its descendants Application: compute space used by files in a directory and its subdirectories 9 cs16/ 3 8 7 homeworks/ todo.txt 1K programs/ 1 2 h1c.doc 3K h1nc.doc 2K 05/01/24 04:40 Algorithm postOrder(v) for each child w of v postOrder (w) visit(v) 4 5 DDR.java 10K Trees Stocks.java 25K 6 Robot.java 20K 7

Binary Tree A binary tree is a tree with the following properties: Applications: Each internal node has two children The children of a node are an ordered pair A We call the children of an internal node left child and right child Alternative recursive definition: a binary tree is either a tree consisting of a single node, or a tree whose root has an ordered pair of children, each of which is a binary tree arithmetic expressions decision processes searching B D E H 05/01/24 04:40 Trees C F G I 8

Arithmetic Expression Tree Binary tree associated with an arithmetic expression internal nodes: operators external nodes: operands Example: arithmetic expression tree for the expression (2 (a 1) (3 b)) 2 a 05/01/24 04:40 3 b 1 Trees 9

Decision Tree Binary tree associated with a decision process internal nodes: questions with yes/no answer external nodes: decisions Example: dining decision Want a fast meal? No Yes How about coffee? On expense account? Yes No Yes No Starbucks Spike’s Al Forno Café Paragon 05/01/24 04:40 Trees 10

Properties of Binary Trees Notation Properties: e i 1 n 2e 1 h i h (n 1) 2 e 2h h log e 2 n number of nodes e number of external nodes i number of internal nodes h height 05/01/24 04:40 Trees h log2 (n 1) 1 11

BinaryTree ADT The BinaryTree ADT extends the Tree ADT, i.e., it inherits all the methods of the Tree ADT Additional methods: Update methods may be defined by data structures implementing the BinaryTree ADT position leftChild(p) position rightChild(p) position sibling(p) 05/01/24 04:40 Trees 12

Inorder Traversal In an inorder traversal a node is visited after its left subtree and before its right subtree Application: draw a binary tree Algorithm inOrder(v) if isInternal (v) inOrder (leftChild (v)) visit(v) if isInternal (v) inOrder (rightChild (v)) x(v) inorder rank of v y(v) depth of v 6 2 8 1 4 3 05/01/24 04:40 7 9 5 Trees 13

Print Arithmetic Expressions Specialization of an inorder traversal print operand or operator when visiting node print “(“ before traversing left subtree print “)“ after traversing right subtree 2 3 a 05/01/24 04:40 Algorithm printExpression(v) if isInternal (v) print(“(’’) inOrder (leftChild (v)) print(v.element ()) if isInternal (v) inOrder (rightChild (v)) print (“)’’) b ((2 (a 1)) (3 b)) 1 Trees 14

Evaluate Arithmetic Expressions Algorithm evalExpr(v) if isExternal (v) return v.element () else x evalExpr(leftChild (v)) y evalExpr(rightChild (v)) operator stored at v return x y Specialization of a postorder traversal recursive method returning the value of a subtree when visiting an internal node, combine the values of the subtrees 2 3 5 05/01/24 04:40 2 1 Trees 15

Euler Tour Traversal Generic traversal of a binary tree Includes a special cases the preorder, postorder and inorder traversals Walk around the tree and visit each node three times: on the left (preorder) from below (inorder) on the right (postorder) L 2 R B 5 05/01/24 04:40 3 2 1 Trees 16

Template Method Pattern public abstract class EulerTour { Generic algorithm that can be specialized by protected BinaryTree tree; redefining certain steps protected void visitExternal(Position p, Result r) { } Implemented by means of protected void visitLeft(Position p, Result r) { } an abstract Java class protected void visitBelow(Position p, Result r) { } Visit methods that can be protected void visitRight(Position p, Result r) { } redefined by subclasses protected Object eulerTour(Position p) { Template method eulerTour Result r new Result(); Recursively called on the if tree.isExternal(p) { visitExternal(p, r); } left and right children else { A Result object with fields visitLeft(p, r); leftResult, rightResult and r.leftResult eulerTour(tree.leftChild(p)); finalResult keeps track of visitBelow(p, r); the output of the recursive calls to eulerTour r.rightResult eulerTour(tree.rightChild(p)); visitRight(p, r); return r.finalResult; } 05/01/24 04:40 Trees 17

Specializations of EulerTour We show how to specialize class EulerTour to evaluate an arithmetic expression Assumptions public class EvaluateExpression extends EulerTour { protected void visitExternal(Position p, Result r) { r.finalResult (Integer) p.element(); } protected void visitRight(Position p, Result r) { Operator op (Operator) p.element(); r.finalResult op.operation( (Integer) r.leftResult, (Integer) r.rightResult ); } External nodes store Integer objects Internal nodes store Operator objects supporting method operation (Integer, Integer) } 05/01/24 04:40 Trees 18

Data Structure for Trees A node is represented by an object storing Element Parent node Sequence of children nodes B Node objects implement the Position ADT A B D A C D F E C 05/01/24 04:40 F Trees E 19

Data Structure for Binary Trees A node is represented by an object storing Element Parent node Left child node Right child node B Node objects implement the Position ADT B A A D C 05/01/24 04:40 D E C Trees E 20

Java Implementation Tree interface BinaryTree interface extending Tree Classes implementing Tree and BinaryTree and providing expandExternal(v) v Constructors Update methods Print methods expandExternal(v) removeAboveExternal(w ) 05/01/24 04:40 removeAboveExternal(w) Examples of updates for binary trees A A v A B Trees C w B 21

Trees in JDSL JDSL was developed at Brown’s Center for Geometric Computing See the JDSL documentation and tutorials at http://jdsl.org JDSL is the Library of Data Structures in Java Tree interfaces in JDSL InspectableBinaryTree InspectableTree BinaryTree Tree Inspectable versions of the interfaces do not have update methods Tree classes in JDSL InspectableTree Tree InspectableBinaryTree NodeBinaryTree NodeTree 05/01/24 04:40 BinaryTree Trees 22