JuliaでBSTを実装する方法は？

Question

JuliaでBSTを実装しようとしていますが、挿入機能を呼び出すときに問題が発生しました。新しいノードを作成しようとすると、構造は変更されません。

マイコード：

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) 

私も何にもゼロを変更しようとしました。私が試した次のバージョンはNodeで定義されたデータ型を使っていますが、何も値を持たないinsert（C Nullに似ています）を呼び出そうとするとエラーが出ます。

ありがとうございます。

Answer 1

コードにはいくつかの問題があります。 1つはタイプが安定しておらず、左右に何かが含まれている可能性があります。 もう1つは、インサート関数内にローカル変数ノードを設定しても、何も変更に影響しないということです。 文章上の問題は、引数を変更する関数には一般に！挿入のような名前の最後の文字として、！プッシュ！ setindex !.

私は次のように動作するはずだと思う：

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) 

このバージョンでは、ジュリアのプッシュをオーバーロード！リーフノードとキーを挿入する場所を検索するために検索を続ける必要がある場所を区別できるようにNullable型を使用します。これは再帰的な定義であり、最適化されていないため、再帰的ではなくループで行う方がはるかに高速です。