스위프트 이진 검색 트리 검색

Question

단어 목록을 저장하는 BST를 구현하려고합니다. 순회하고 순서대로 인쇄하려고하면 목록이 알파벳 순으로 인쇄되기 때문에 트리 구조가 정확하다는 것을 알고 있습니다. 그러나 트리에서 요소를 찾는 내 검색 함수는 매번 false를 반환합니다.

func search(searchValue: String) -> Bool? { 
    if searchValue == value as! String{ 
     return true 
    } 

    if searchValue < value as! String { 
     return left?.search(searchValue: searchValue) 
    } 
    if searchValue > value as! String{ 
     return right?.search(searchValue: searchValue) 
    } 

    return false 


} 

이 루프에서 함수가 호출됩니다. BST에없는 모든 단어는 배열에 추가해야합니다. 현재는 단어가 배열에 추가되지 않습니다. 입력 배열은 BST에 대해 검사 할 모든 단어의 배열입니다. 문맥

for item in arrayInput 
     { 
      let target = item.lowercased()//reversed 
      let inTree = tree.search(searchValue: target) 
      if inTree == false 
      { 
       misspelled.append(item) 
      } 
     } 

더 BST 클래스 :

public class BinarySearchTree<T: Comparable> { 
     fileprivate(set) public var value: T 
     fileprivate(set) public var parent: BinarySearchTree? 
     fileprivate(set) public var left: BinarySearchTree? 
     fileprivate(set) public var right: BinarySearchTree? 


     public init(value: T) { 
      self.value = value 
     } 

     public convenience init(array: [T]) { 
      precondition(array.count > 0) 
      self.init(value: array.first!) 
      for v in array.dropFirst() { 
       insert(value: v) 
      } 
     } 

     } 
    public func insert(value: T) { 
      if value < self.value { 
       if let left = left { 
        left.insert(value: value) 
       } else { 
        left = BinarySearchTree(value: value) 
        left?.parent = self 
       } 
      } else { 
       if let right = right { 
        right.insert(value: value) 
       } else { 
        right = BinarySearchTree(value: value) 
        right?.parent = self 
       } 
      } 
     } 

Answer 1

나는 좀 걸릴 코드를 일부 개선했습니다 : 함께 무엇

public class BinarySearchTree<T: Comparable> { 
    fileprivate(set) public var value: T 
    fileprivate(set) public var parent: BinarySearchTree? 
    fileprivate(set) public var left: BinarySearchTree? 
    fileprivate(set) public var right: BinarySearchTree? 


    public init(value: T) { 
     self.value = value 
    } 

    public convenience init(array: [T]) { 
     precondition(array.count > 0) 
     self.init(value: array.first!) 
     for v in array.dropFirst() { 
      insert(value: v) 
     } 
    } 

    // Refactored out common code to reduce duplicaiton 
    public func insert(value: T) { 
     let nodeToModify = value < self.value ? left : right 

     if let nodeToModify = nodeToModify { 
      nodeToModify.insert(value: value) 
     } 
     else { 
      let subtree = BinarySearchTree(value: value) 
      subtree.parent = self 
      self.left = subtree 
     } 
    } 


    // Why constrain searching to just Strings? Keep it generic to all T: Comparable 
    func search(for searchValue: T) -> Bool { 
     if searchValue == value { return true } 

     if searchValue < value { 
      return left?.search(for: searchValue) ?? false 
     } 
     if searchValue > value { 
      return right?.search(for: searchValue) ?? false 
     } 

     return false 
    } 
} 

// Move the `search` function outside of the class, and into an extension 
// with the constaint that `T == String` 
extension BinarySearchTree where T == String { 
    func search(for searchValue: String) -> Bool { 
     if searchValue == value { return true } 

     if searchValue < value { 
      return left?.search(for: searchValue) ?? false 
     } 
     if searchValue > value { 
      return right?.search(for: searchValue) ?? false 
     } 

     return false 
    } 
} 

Answer 2

나는 문제가 당신이 당신의 이진 검색 트리의 리프 노드에 도달 한 후 전무를 반환하는 것입니다 생각합니다. 철자가 틀린 단어는 잎의 저장된 값보다 작거나 크므로 왼쪽 또는 오른쪽 자식을 찾고 해당 값이 nil이므로 함수가 nil을 반환합니다.

이 문제를 해결할 수있는 몇 가지 방법이 있지만 가장 단순한 변경은 왼쪽 또는 오른쪽이 nil 인 경우 nil이 false로 병합하는 것입니다.

func search(searchValue: String) -> Bool { 
    if searchValue == value as! String { 
     return true 
    } 

    if searchValue < value as! String { 
     return left?.search(searchValue: searchValue) ?? false 
    } 
    if searchValue > value as! String { 
     return right?.search(searchValue: searchValue) ?? false 
    } 

    return false 
} 

Answer 3

스위프트 4

class SearchTreeNode<T: Comparable>{ 
private var element: T 
var parent: SearchTreeNode? 
var left: SearchTreeNode? 
var right: SearchTreeNode? 

init(value _element: T, parent: SearchTreeNode<T>?) { 
    element = _element 
    self.parent = parent 
} 

func value() -> T { 
    return element 
} 
} 

class BinarySearchTree<T: Comparable>{ 
var root: SearchTreeNode<T> 

init(rootValue _element: T) { 
    root = SearchTreeNode(value: _element, parent: nil) 
} 

func append(value: T) { 
    addValue(toTree: root, _element: value) 
} 

func isPresent(element: T) { 
    if let node = search(for: element, nodeToSearch: root){ 
     print(node.right?.value()) 
     print(node.left?.value()) 
     print(node.parent?.value()) 
     print("Item is presnt in search tree") 
    }else{ 
     print("Item not presnt in search tree") 
    } 
} 

private func addValue(toTree currentNode: SearchTreeNode<T>, _element: T){ 
    if currentNode.value() == _element { 
     print("Already Presnt") 
    }else if currentNode.value() > _element { 
     if currentNode.left == nil { 
      currentNode.left = SearchTreeNode(value: _element, parent: currentNode) 
     }else{ 
      addValue(toTree: currentNode.left!, _element: _element) 
     } 
    }else if currentNode.value() < _element{ 
     if currentNode.right == nil { 
      currentNode.right = SearchTreeNode(value: _element, parent: currentNode) 
     }else{ 
      addValue(toTree: currentNode.right!, _element: _element) 
     } 
    } 
} 

private func search(for _element: T, nodeToSearch node: SearchTreeNode<T>) -> SearchTreeNode<T>?{ 
    if node.value() == _element { 
     return node 
    }else if node.value() > _element { 
     if node.left == nil { 
      return nil 
     }else{ 
      return search(for: _element, nodeToSearch: node.left!) 
     } 
    }else if node.value() < _element{ 
     if node.right == nil { 
      return nil 
     }else{ 
      return search(for: _element, nodeToSearch: node.right!) 
     } 
    }else{ 
     return nil 
    } 
} 

func getRightMostNode(forNode node: SearchTreeNode<T>) -> SearchTreeNode<T> { 
    if node.right != nil { 
     return getRightMostNode(forNode: node.right!) 
    } 
    return node 
} 

func delete(_element: T){ 
    if let node = search(for: _element, nodeToSearch: root) { 
     if (node.left != nil) && (node.right != nil) { 
      var rightMostNode = getRightMostNode(forNode: node.left!) 
      rightMostNode.right = node.right 
      node.left?.parent = node.parent 
      (node.parent?.left?.value() == _element) ? (node.parent?.left = node.left) : (node.parent?.right = node.left) 
     }else if (node.left != nil) { 
      node.left?.parent = node.parent 
      (node.parent?.left?.value() == _element) ? (node.parent?.left = node.left) : (node.parent?.right = node.left) 
     }else if (node.right != nil){ 
      node.right?.parent = node.parent 
      (node.parent?.left?.value() == _element) ? (node.parent?.left = node.right) : (node.parent?.right = node.right) 
     }else{ 
      (node.parent?.left?.value() == _element) ? (node.parent?.left = nil) : (node.parent?.right = nil) 
     } 
    }else{ 
     print("Element for deletion is not present") 
    } 
} 
}