Come implementare BST in Julia?

Question

Sto cercando di implementare BST in Julia, ma ho riscontrato dei problemi quando chiamo funzione di inserimento. Quando provo a creare un nuovo nodo, la struttura rimane invariata.

Il mio codice:

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) 

Ho anche cercato di cambiare zero a nulla. La prossima versione che ho provato è con i tipi di dati definiti in Node, ma quando provo a chiamare insert con valore nulla (simile a C Null) mi ha dato errore.

Grazie per la risposta.

Answer 1

Il codice ha un numero di problemi. Uno è che non è di tipo stabile, sinistra e destra potrebbero contenere qualsiasi cosa. L'altro è che l'impostazione del nodo di variabile locale all'interno della funzione di inserimento non influirà sul cambiamento di nulla. Un problema stilistico, le funzioni che modificano i loro argomenti generalmente hanno un! come ultimo carattere nel nome, come insert !, push! setindex !.

penso che il seguente dovrebbe funzionare:

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) 

Questa versione sovraccarica il Julia spingere! funzione e utilizza il tipo Nullable in modo che possa distinguere tra un nodo foglia e dove deve continuare la ricerca per trovare dove inserire la chiave. Questa è una definizione ricorsiva e non è ottimizzata, sarebbe molto più veloce farlo con i loop anziché ricorsivi.