Implementazione di alberi binari usando Swift enum

Question

Sto facendo alcuni esperimenti con le enune Swift per familiarizzarmi con loro e ho implementato un albero binario rudimentale. Funziona quando si aggiungono fino a tre elementi, ma aggiungendo altro oltre non lo cambia e non sono riuscito a capire perché non funzionava.

Ecco il codice:

protocol TreeProtocol { 
    mutating func insert(value: Int) 
    func walk() 
} 


enum Tree:TreeProtocol { 
    case Empty 
    case Leaf(Int) 
    case Node(Int, TreeProtocol?, TreeProtocol?) 

    init(){ 
     self = .Empty; 
    } 

    init(value: Int) { 
     self = .Leaf(value) 
    } 

    init(value: Int, left:TreeProtocol?, right:TreeProtocol?){ 
     self = .Node(value, left, right); 
    } 

    mutating func insert(value: Int) { 
     switch self { 
     case .Empty: 
      self = .Leaf(value) 

     case .Leaf(let currentNodeValue): 
      let newTree = Tree(value: value) // var here generates a warning 
      if value < currentNodeValue { 
       self = .Node(currentNodeValue, newTree, .None) 
      } 
      else { 
       self = .Node(currentNodeValue, .None, newTree) 
      } 

     case let .Node(currentNodeValue, leftNode, rightNode): 
      if (value < currentNodeValue) { 
       if leftNode == nil { 
        let newTree = Tree(value: value) 
        self = .Node(currentNodeValue, newTree, rightNode) 
       } 
       else { 
        var l = leftNode! // unable to call leftNode!.insert() directly 
        l.insert(value) 
       } 
      } 
      else { 
       if rightNode == nil { 
        let newTree = Tree(value: value) 
        self = .Node(currentNodeValue, leftNode, newTree) 
       } 
       else { 
        var r = rightNode! 
        r.insert(value) 
       } 
      } 
     } 
    } 

    func walk() { 
     switch self { 
     case .Empty: 
      print("Empty") 
     case .Leaf (let value): 
      print("\(value), ") 
     case .Node(let value, let leftNode, let rightNode): 
      if leftNode != nil { 
       leftNode!.walk() 
      } 
      print("\(value) ") 
      if (rightNode != nil) { 
       rightNode!.walk() 
      } 
     } 
    } 
} 

E se corro le seguenti prove:

var tree = Tree(); 
    tree.walk() 

    tree.insert(100) 
    tree.walk() 

    tree.insert(50) 
    tree.walk() 

    tree.insert(150) 
    tree.walk() 

    tree.insert(25) 
    tree.walk() 

l'output è:

Empty 

    100 

    50, 
    100 

    50, 
    100, 
    150 

    50, 
    100, 
    150 

Il valore 25 non è sempre aggiunto alla albero

(Questo codice è un po 'inelegante, è solo la prima iterazione, ci sono parecchie parti brutte che potrebbero essere migliorate e abbellite. In attesa di funzionalità enum ricorsiva da aggiungere al beta Xcode).

Answer 1

So che hai già una risposta, ma mi piace molto la tua implementazione e ho pensato di fornire il codice per implementare la soluzione di @ Wain e anche di ottimizzare alcune delle logiche nidificate if-else.

Si tratta di una leggera modifica per il protocollo, in modo che insert restituisce un valore:

protocol TreeProtocol { 
    mutating func insert(value: Int) -> TreeProtocol 
    func walk() 
} 

E poi la funzione insert può essere riscritta così:

mutating func insert(value: Int) -> TreeProtocol { 
    switch self { 
    case .Empty: 
     self = .Leaf(value) 

    case .Leaf(let currentNodeValue): 
     let newTree = Tree(value: value) 
     self = value < currentNodeValue 
      ? .Node(currentNodeValue, newTree, .None) 
      : .Node(currentNodeValue, .None, newTree) 

    case var .Node(currentNodeValue, leftNode, rightNode): 
     self = value < currentNodeValue 
      ? .Node(currentNodeValue, leftNode?.insert(value) ?? Tree(value: value), rightNode) 
      : .Node(currentNodeValue, leftNode, rightNode?.insert(value) ?? Tree(value: value)) 
    } 
    return self 
} 

Answer 2

Poiché si stanno modificando i nodi interni e in realtà ne viene creata una copia. Quella copia non viene mai inserita nell'albero, viene semplicemente gettata via dopo essere stata modificata. Se dopo l'inserimento in l e r reinserisci questi nodi (rispettivamente con self = .Node(currentNodeValue, l, rightNode) e self = .Node(currentNodeValue, leftNode, r)), l'albero nel suo insieme verrà aggiornato. È un problema di valore/per riferimento.