Wie implementiert man BST in Julia?

Question

Ich versuche, BST in Julia zu implementieren, aber ich stieß auf Problem, wenn ich die Einfügefunktion aufrufen. Wenn ich versuche, einen neuen Knoten zu erstellen, bleibt die Struktur unverändert.

Mein Code:

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) 

Ich habe auch versucht Null zu nichts zu ändern. Die nächste Version, die ich ausprobiert habe, ist mit definierten Datentypen in Node, aber wenn ich versuche, Einfüge mit nichts Wert (ähnlich wie C Null) aufzurufen, gab es mir einen Fehler.

Danke für die Antwort.

Answer 1

Der Code weist eine Reihe von Problemen auf. Einer ist, dass es nicht typstabil ist, links und rechts könnte alles enthalten. Die andere Möglichkeit besteht darin, dass das Setzen des lokalen Variablenknotens innerhalb der Einfügefunktion keinen Einfluss auf die Änderung hat. Ein stilistisches Problem, Funktionen, die ihre Argumente ändern, haben in der Regel ein! Als letztes Zeichen im Namen, wie Einfügen !, drücken! Setindex !.

denke ich Folgendes sollte funktionieren:

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) 

Diese Version der Julia Push Überlastungen! Funktion und verwendet den Nullable-Typ, um zwischen einem Blattknoten und der Position zu unterscheiden, an der die Suche fortgesetzt werden muss, um den Schlüssel zu finden. Dies ist eine rekursive Definition, und ist nicht optimiert, es wäre viel schneller, es mit Schleifen statt rekursiv zu tun.