How to implement binary search tree in Julia?

Question

I am trying to implement BST in Julia, but ran into a problem while calling the insert function. When I try to create a new node, the structure remains unchanged.

My code is:

type Node key::Int64 left right end function insert(key::Int64, node) if node == 0 node = Node(key, 0, 0) elseif key < node.key insert(key, node.left) elseif key > node.key insert(key, node.right) end end root = Node(0,0,0) insert(1,root) insert(2,root) 

I also tried changing zero to nothing. The next version I tried with certain data types in node, but when I try to call insert without a value (similar to C Null), it gave me an error.

Thanks for the answer.

Answer 1

There are a number of problems in the code. One of them is that it is not a stable type, it can contain anything on the left and right. Another is that setting the local variable node inside the insert function will not affect the change of anything. A stylistic problem, functions that change their arguments, as a rule, have! like the last character in a name, such as insert !, push! SetIndex !.

I think the following should work:

 type BST key::Int left::Nullable{BST} right::Nullable{BST} end BST(key::Int) = BST(key, Nullable{BST}(), Nullable{BST}()) BST() = BST(0) function Base.push!(node::BST, key) if key < node.key if node.left.isnull node.left = BST(key) else push!(node.left.value, key) end elseif key > node.key if node.right.isnull node.right = BST(key) else push!(node.right.value, key) end end end root = BST() push!(root, 1) push!(root, 2) 

This version overloads pressing Julia! and uses the Nullable type so that it can distinguish between the leaf node and where it needs to continue searching to find where to insert the key. This definition is recursive and not optimized, it would be much faster to do this using loops instead of recursive ones.