> it only requires O(log n) on a (balanced) search tree:
sorry, O(log n) for conttains?
and O(n log n) in total
--
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
Right, but evaluating tree-size is O(n), even with a binary search tree. Doing
this on each insertion is slow.
The following is a possible solution without "do", and it only requires O(log
n) on a (balanced) search tree:
(define tree5
(let loop ([tree null] [n 5])
(define x (random 10))
Or if you know that there are only 10 candidates, you can just iterate
over (a prefix of) this list:
(shuffle (build-list 10 values))
Robby
On Mon, Feb 15, 2016 at 8:37 AM, Tony Garnock-Jones wrote:
> If your "insert" is idempotent, and you have some means of measuring
> tree size, you can el
If your "insert" is idempotent, and you have some means of measuring
tree size, you can eliminate i, c and x:
(define tree4
(do ([tree null (insert tree (random 10))])
[(>= (tree-size tree) 5) tree]))
I arrived at this by considering doing something similar for sets:
(define tree4
(do ([
I try to fill a binary tree with 5 random numbers, avoiding duplicates. Is
there a more elegant way than this (using "Iterations and Comprehensions")?
(define tree4
(do ([x (random 10) (random 10)]
[c #f (contains? tree x)]
[tree null (if c tree (insert tree x))]
[i 0 (if c
5 matches
Mail list logo
