On Jun 30, 2009, at 3:50 AM, Nicolas Oury wrote:
>
> If you use depth/size a lot, it might be faster to store them in the
> nodes. (it is pseudo code)
>
> (defstruct bintree :head :left :right :size :depth)
>
> (defn make-tree [head left right]
> (struct bintree head left right
> (+ (left :size) (right :size))
> ( + 1 (max (left :depth) (right :depth)))))
>
> You have a constant overhead to node construction, but then depth and
> size are O(1).
> Of course, it makes use of immutability of the children.
Very good call!
> That is really useful if you want to balance trees.
>
> I don't get how you store trees in a vector, but you should be able to
> store size/depth in the vector too.
It's not working for me right now because I'm tired, but basically the
observation is that index 1 is the root. Then index 2 and 3 are the
left and right children respectively. The left and right children of
index 2 are 4 and 5. The left and right children of index 3 are 6 and
7. So if you had this tree:
x
/ \
y z
/ \ / \
a b c d
You could store it in this vector:
[nil x y z a b c d]
And in general you can get from parent to child by doing (i * 2) or (i
* 2 + 1) and get from child to parent by doing floor [i / 2]. I
remember doing this in C because it was less intensive than making a
bunch of structs and making sure the pointers got managed correctly (I
was a sophomore, give me a break ;). This method doesn't have many
advantages in Clojure though. :)
—
Daniel Lyons
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
