> On May 24, 2019, at 6:27 AM, Sean Kemplay <sean.kemp...@gmail.com> 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/6A4AA4C8-A08B-4C5F-832D-DAB6FF4E150B%40felleisen.org.
For more options, visit https://groups.google.com/d/optout.
