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.
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.
Best,
Nicolas.
On Tue, 2009-06-30 at 02:28 -0600, Daniel Lyons wrote:
>
> On Jun 30, 2009, at 1:05 AM, Emeka wrote:
>
> > Hello All,
> >
> > I have a BinaryTree Nodes that I want to resolve it's depth and the
> > BinaryTree may be unbalanced. How do I do this? Can't just figure it
> > out on my own?
> > It is in the form of vector of vectors, and from one cell of any
> > vector I can move to the next row however the column index has to
> > be either increased by one or decreased by one(and the new cell is
> > empty).
>
>
> If you had a balanced binary tree, you could just take log_2(N) where
> N is the number of nodes. :) But since you don't you have to do
> something like get the max depth of the left branch and the right
> branch and add one to it (pseudocode):
>
>
> (defn depth [tree]
> (if (nil? tree) 0
> (+ 1 (max (depth (left tree)) (depth (right tree)))))
>
>
> If you're storing this binary tree in an array, I vaguely remember
> doing something like storing the left node at 2*i where i is the index
> of the current node, and the right node at 2*i+1. I'm not sure how
> you'd do that with an unbalanced tree unless you did something like
> have nils in your array. If you did that, you just need to take
> log_2(I) where I is the index of the last non-nil value in the array.
>
>
> I'm not sure exactly what data structure you're working with to make
> your binary tree though. Can you send an example of the tree you have
> as vectors?
>
>
> Are you also trying to compute whether or not it's unbalanced or is
> that just a given that it might be?
>
> —
> 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
-~----------~----~----~----~------~----~------~--~---
