Trees Make Money Fast Stock Fraud 2010 Goodrich Tamassia Ponzi Scheme Trees Bank Robbery 1 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 2010 Goodrich Tamassia Manufacturing Trees Asia Laptops R D Desktops Canada 2 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 Height of a tree maximum depth E of any node 3 Descendant of a node child grandchild grand grandchild etc I Siblings nodes with same parent 2010 Goodrich Tamassia Trees Subtree tree consisting of a node and its descendants A B C F J G D H K subtree3 Binary Trees A binary tree is a tree with the following properties Each internal node has at most two children exactly two for proper binary trees The children of a node are an ordered pair 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 2010 Goodrich Tamassia Trees arithmetic expressions decision processes searching A We call the children of an internal node left child and right child Alternative recursive definition a binary tree is either Applications B D C E H F G I 4 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 2010 Goodrich Tamassia 3 b 1 Trees 5 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 Yes On expense account No Yes Starbucks McDonalds Al Forno 2010 Goodrich Tamassia Trees No Caf Paragon 6 Differences Between A Tree A Binary Tree No node in a binary tree may have a degree more than 2 whereas there is no limit on the degree of a node in a tree The subtrees of a binary tree are ordered those of a tree are not ordered Differences Between A Tree A Binary Tree The subtrees of a binary tree are ordered those of a tree are not ordered a b a b Are different when viewed as binary trees Are the same when viewed as trees Binary Trees Full binary tree Complete binary tree All internal nodes have two children all levels except possibly the last are completely full the last level has all its nodes to the left side Perfect binary Tree A complete binary tree of height h has 2h 1 internal nodes and 2h leaves Also a binary tree with n nodes has height at least lgn Binary Trees example Properties Binary Trees We say that all internal nodes have at most two children External nodes have no children internal node external node Properties of Proper full 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 2010 Goodrich Tamassia Trees h log2 n 1 1 12 Properties of Proper Binary Trees Property 1 d Level d has at most 2 n number of nodes nodes e number of external nodes 0 1 i number of 1 2 internal nodes 2 4 22 h height 3 8 2 4 23 Let it be true for d 1 level d 1 2d 1 D 2 2d 1 2d Notation 2010 Goodrich Tamassia Trees 13 Properties of Proper full Binary Trees Property 2 A full binary tree of height h n number of nodes h 1 has 2 1 nodes e number of N 20 21 2h external nodes 2h 1 1 i number of Notation internal nodes h height 2010 Goodrich Tamassia Property 2 1 Height of a binary tree of N nodes log N N 2h 1 1 N 1 2h 1 h 1 log N 1 H log N 1 1 Log N Trees 14 Properties of Proper Binary Trees Property 3 In a binary tree the number n number of nodes of external nodes is 1 more e number of than the number of internal external nodes nodes i e e i 1 i number of internal nodes Base 0 internal node h height Clearly true for one node Let it be true for N 1 internal node tree T Make one external node internal to make it n internal node tree 2 new external nodes one old Trees 15 2010 Goodrich Tamassia external node gone Notation Properties of Proper Binary Trees Property 4 Notation n number of nodes e number of N 2e 1 Proof Based on previous 2010 Goodrich Tamassia Trees 16 BinaryTree ADT The BinaryTree ADT extends the Tree ADT i e it inherits all the methods of the Tree ADT Additional methods position p left position p right 2010 Goodrich Tamassia Trees Update methods may be defined by data structures implementing the BinaryTree ADT Proper binary tree Each node has either 0 or 2 children 17 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 Algorithm preOrder v visit v for each child w of v preorder w Make Money Fast 2 5 1 Motivations 2 Methods 3 4 1 1 Greed 1 2 Avidity 2010 Goodrich Tamassia 9 6 7 2 1 Stock Fraud Trees 2 2 Ponzi Scheme References 8 2 3 Bank Robbery 18 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 Algorithm postOrder v for each child w of v postOrder w visit v cs16 3 8 7 homeworks 1 2 h1c doc 3K h1nc doc 2K 2010 Goodrich Tamassia todo txt 1K programs 4 5 DDR cpp 10K Trees Stocks cpp 25K 6 Robot cpp 20K 19 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 v isExternal inOrder v left visit v if v isExternal inOrder v right x v inorder rank of v y v depth of v 6 2 8 1 4 3 2010 Goodrich Tamassia 7 9 5 Trees 20 Arithmetic Expression Using B A D C B E inorder traversal A B C D E infix expression preorder traversal AB C D E prefix expression postorder traversal AB C D E postfix expression level order traversal E D CAB 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 a …
View Full Document
Unlocking...