Hi,
hubert_tiey...@t-online.de writes:
> Hi,
>
> I've been trying to implement some code to build Binary Search
> Trees. The code below works, I'm able to build a tree and then print
> it
> in ascending order, but it is quite ugly, with those Nullable types
> and
> having to access subtrees with code like tree.value.left instead of
> directly tree.left
>
> Here is a variant for a binary search tree which uses union types and also has
> an empty tree. The definition is straightforward and - at least for me - easy
> to
> understand.
OK, thanks for the suggestion. So, I ended up having three different
ways of constructing BSTs, and decided to test how they perform. The
three different methods are:
1.- my suggestion with Nullables (as per mail of Oct 30)
2.- the method with non-concrete types suggested by Ralph Smith (as per
mail of Oct 31)
3.- your suggestion with union types
a- your way of building the tree
b- modified way of building the tree
3b uses your idea of union types but build the tree as follows:
,----
| function build_bst3(list::Array{Int,1})
| head = list[1]
| tree = Bst3(head)
| for e in list[2:end]
| place_bst3(tree,e)
| end
| return tree
| end
|
| function place_bst3(tree::BST,e::Int)
| if e == tree.val
| # println("Dropping $(e). No repeated values allowed")
| elseif e < tree.val
| if tree.left == et
| tree.left = Bst3(e)
| else
| place_bst3(tree.left,e)
| end
| else
| if tree.right == et
| tree.right = Bst3(e)
| else
| place_bst3(tree.right,e)
| end
| end
| end
`----
I created an array with 1e5 unique values
test=unique(rand(1:Int(1e11),100000))
And this is the time it takes for each method:
Times to build the tree (best of 10 runs):
-----
Method 1: 0.125s
Method 2: 0.154s
Method 3a: 0.393s
Method 3b: 0.191s
Times to traverse the tree (count number of nodes):
----
Method 1: 0.017s
Method 2: 0.008s
Method 3: 0.017s
Given this, for the N-body code that I wrote I would actually go for
Method 2, since for each iteration I build the tree once but then I use
it many times (once per particle), so it should probably be the fastest.
Cheers,
--
Ángel de Vicente
http://www.iac.es/galeria/angelv/
