Binäre Baumimplementierung mit Swift enum

Question

Ich mache einige Experimente mit Swift Enums, um mich mit ihnen vertraut zu machen und habe einen rudimentären Binärbaum implementiert. Es funktioniert, wenn Sie bis zu drei Elemente hinzufügen, aber das Hinzufügen von mehr darüber hinaus ändert es nicht und ich konnte nicht sehen, warum es nicht funktionierte.

Hier ist der Code:

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() 
      } 
     } 
    } 
} 

Und wenn ich die folgenden Tests durchgeführt:

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() 

Die Ausgabe lautet:

Empty 

    100 

    50, 
    100 

    50, 
    100, 
    150 

    50, 
    100, 
    150 

Der 25-Wert in die Einstiegs- wird nicht hinzugefügt Baum

(Dieser Code ist ein wenig unelegant, es ist nur die erste Iteration, da sind einige hässliche Teile drin, die verbessert und verschönert werden könnten. Warten auf rekursive Enum-Funktionalität, die der Xcode-Beta hinzugefügt werden soll).

Answer 1

Ich weiß, dass Sie bereits eine Antwort haben, aber ich mag Ihre Implementierung wirklich und dachte, ich würde den Code für die Implementierung von @ Wains Lösung bereitstellen und auch einige verschachtelte if-else Logik rationalisieren.

Es hat eine leichte Modifikation für das Protokoll beinhaltet, so dass insert einen Wert zurückgibt:

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

Und dann die insert Funktion kann wie folgt neu geschrieben werden:

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

Weil Sie die internen Knoten mutieren und das tatsächlich eine Kopie von ihnen erstellt. Diese Kopie wird niemals in den Baum eingefügt, sie wird einfach weggeworfen, nachdem sie verändert wurde. Wenn Sie nach dem Einfügen in l und r diese Knoten (mit self = .Node(currentNodeValue, l, rightNode) bzw. self = .Node(currentNodeValue, leftNode, r)) erneut einfügen, wird der Baum als Ganzes aktualisiert. Es ist ein by-value/by-Referenz-Problem.