Thanks Matthias, I think I have it now, much appreciated. On Friday, May 24, 2019 at 2:24:57 PM UTC+1, Matthias Felleisen wrote: > > > > > On May 24, 2019, at 6:27 AM, Sean Kemplay <sean....@gmail.com > <javascript:>> wrote: > > > > Hi all, > > > > I trying to work out the ART of the sum-tree question from HTDP2e. > > > > I have worked through the book before however am going through it again, > this time am doing every exercise - this is not homework! > > > > Here is my data defenitions, examples, a function ror summing up the > contents and tests - > > > > ; A Pair is a list of two items > > > > ; A Number-Tree is one of: > > ; Number > > ; [Pair-of Number-Tree] > > ; Examples - > > ; 0 > > ; (list 0 1) > > ; (list (list 1 2) 3) > > ; (list (list 1 2) (list 3 4)) > > ; (list (list (list 1 2) (list 3 4)) (list (list 5 6) (list 7 8))) > > ; (list (list (list (list (list (list (list 8 7) 6 ) 5) 4) 3) 2) 1) > > > > ; Number-Tree -> Number > > ; Sum up all numbers in nt > > (check-expect (sum-list 0) 0) > > (check-expect (sum-list (list 1 2)) 3) > > (check-expect (sum-list (list (list 1 2) (list 3 4))) 10) > > (check-expect (sum-list(list (list (list 1 2) (list 3 4)) (list (list 5 > 6) (list 7 8)))) 36) > > (check-expect (sum-list (list (list (list (list (list (list (list 8 7) 6 > ) 5) 4) 3) 2) 1)) 36) > > (define (sum-list nt) > > (cond [(number? nt) nt] > > [else (+ (sum-list (first nt)) > > (sum-list (second nt)))])) > > > > > > Using a balanced tree my analysis shows an ART of n^2 to run sum-list > where n is the depth of the tree > > (sum-list(list (list (list 1 2) (list 3 4)) (list (list 5 6) (list 7 > 8)))) > > > > > > Using avery unbalanced tree with all nodesheading down to the left my > analysis shows an ART of 2n - or just n when the constant is removed. > > (sum-list (list (list (list (list (list (list (list 8 7) 6 ) 5) 4) 3) 2) > 1)) > > > > So the unbalanced tree in this case where all nodes need to be visited > would be better? > > > Equally good. > > > > A BST a search function would be better with a balanced tree but not > sum-tree? > > Yes. > > > > Could someone possibly comment whether I am on the right track here? > > Good job. > > > > >
-- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/491b3a19-824b-4e8b-9c2e-7e2f8ff1eabe%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
