이진 탐색 트리

이진 탐색 트리 Binary Search Tree
노드의 개수가 최대 2개인 트리
항상 정렬되어 있다
(루트노드를 기준으로
왼쪽노드는 루트노드 보다 작고, 오른쪽노드는 루트노드 보다 크다)
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

[Insertion]
시간복잡도: O(h)
h는 height로 트리의 높이

• 9를 넣을 때
• 루트(7)보다 크다 -> 오른쪽 브랜치로
• 10보다 작다 -> 왼쪽 브랜치로
• 결과:
  

• 3을 넣을 때
• 루트(7)보다 작다 -> 왼쪽 브랜치로
• 2보다 크다 -> 오른쪽 브랜치로
• 5보다 작다 -> 왼쪽 브랜치로
• 결과:
  

[In-order travelsal]
중위순회
노드가 오름차순으로 정렬된다

//노드에 값이 있거나, 왼쪽이나 오른쪽 노드가 있거나 없거나
//제한적인 상황만 필요하기 때문에 enum이 적절하다(값 타입)

//Recursive enum 'BinaryTree<T>' is not marked 'indirect'
//enum(값타입)은 메모리에 할당될 때 크키가 정해져있어야 하지만 recusive한 경우 그 크기가 정해져있지 않다
//포인터를 사용해 변수에 액세스하는 것과 같은 indirection(간접성)을 사용하기 위해 indirect 키워드를 사용한다
indirect enum BinaryTree<T: Comparable> {   // new Value와 old Value를 비교해야하기 때문에 Comparable 추가
    case empty
    case node(BinaryTree, T, BinaryTree)    //recursive
    
    // 전체 노드 개수 세기
    var count: Int {
        switch self {
        case let .node(left, _, right):
            return left.count + 1 + right.count
        case .empty:
            return 0
        }
    }
    
    // MARK: - 삽입
    // 값타입이 바뀔 땐 mutating 키워드 써주기
//    mutating func naiveInsert(newValue: T) {
//        // 노드가 비어있으면 새로운 노드 생성하기
//        guard case .node(var left, let value, var right) = self else {
//            self = .node(.empty, newValue, .empty)
//            return
//        }
//        if newValue < value {
//            left.naiveInsert(newValue: newValue)
//        } else {
//            right.naiveInsert(newValue: newValue)
//        }
//    }
    
    // enum으로 BinaryTree가 선언되어 있어 Copy On Write가 발생하기 때문에 (트리 복제가 계속 일어남) 새로운 값과 이전 값 연결해주는 삽입 -> O(n)
    // class로 선언된 경우 Copy On Write가 발생하지 않아서 시간복잡도는 일반적으로 O(logN)이 된다.
    private func newTreeWithInsertedValue(newValue: T) -> BinaryTree {
        switch self {
        // 트리가 비어있으면 새로운 노드를 생성하고
        case .empty:
            return .node(.empty, newValue, .empty)
        // 노드가 있으면 왼쪽이나 오른쪽의 자식 노드를 생성한다
        case let .node(left, value, right):
            if newValue < value {
                return .node(left.newTreeWithInsertedValue(newValue: newValue), value, right)
            } else {
                return .node(left, value, right.newTreeWithInsertedValue(newValue: newValue))
            }
        }
        
    }
    
    mutating func insert(newValue: T) {
        self = newTreeWithInsertedValue(newValue: newValue)
    }
    
    // MARK: - Traversal algorithms 순회 O(n)
    //n은 노드의 개수
    //In-order Traversal 중위순회 (노드를 오름차순으로 정렬)
    func traverseInOrder(process: (T) -> ()) {
        switch self {
        // 노드가 비어있으면 멈춘다
        case .empty:
            return
        // 노드가 비어있지 않으면,
        case let .node(left, value, right):
            left.traverseInOrder(process: process)
            process(value)
            right.traverseInOrder(process: process)
        }
    }
    
    //전위순회
    func traversePreOrder(process: (T) -> ()) {
        switch self {
        // 노드가 비어있으면 멈춘다
        case .empty:
            return
        // 노드가 비어있지 않으면,
        case let .node(left, value, right):
            process(value)
            left.traversePreOrder(process: process)
            right.traversePreOrder(process: process)
        }
    }
    
    //후위순회
    func traversePostOrder(process: (T) -> ()) {
        switch self {
        // 노드가 비어있으면 멈춘다
        case .empty:
            return
        // 노드가 비어있지 않으면,
        case let .node(left, value, right):
            left.traversePostOrder(process: process)
            right.traversePostOrder(process: process)
            process(value)
        }
    }
    
    //MARK:- searching
    func search(searchValue: T) -> BinaryTree? {
        switch self {
        case .empty:
            return nil
        case let .node(left, value, right):
            if searchValue == value {
                return self
            }
            if searchValue < value {
                return left.search(searchValue: searchValue)
            } else {
                return right.search(searchValue: searchValue)
            }
        }
    }
}

// leaf nodes
//let node5 = BinaryTree.node(.empty, "5", .empty)
//let nodeA = BinaryTree.node(.empty, "a", .empty)
//let node10 = BinaryTree.node(.empty, "10", .empty)
//let node4 = BinaryTree.node(.empty, "4", .empty)
//let node3 = BinaryTree.node(.empty, "3", .empty)
//let nodeB = BinaryTree.node(.empty, "b", .empty)
//
//// intermediate nodes on the left 루트 왼쪽
//let Aminus10 = BinaryTree.node(nodeA, "-", node10)
//let timeLeft = BinaryTree.node(node5, "*", Aminus10)
//
//// intermediate nodes on the right 루트 오른쪽
//let minus4 = BinaryTree.node(.empty, "-", node4)
//let divide3andB = BinaryTree.node(node3, "/", nodeB)
//let timesRight = BinaryTree.node(minus4, "*", divide3andB)
//
//// root node
//let tree = BinaryTree.node(timeLeft, "+", timesRight)
//print(tree.count)   //12 (전체 노드의 개수)

extension BinaryTree: CustomStringConvertible {
    var description: String {
        switch self {
        case let .node(left, value, right):
            return "value: \(value), left = [" + left.description + "], right = [" + right.description + "]"
        case .empty:
            return ""
        }
    }
}

// Copy on Write 성질 때문에
// 새로운 값이 이전 값과 연결되지 않기 때문에, 새로운 값이 업데이트되지 않는다.
var binaryTree: BinaryTree<Int> = .empty
binaryTree.insert(newValue: 5)
binaryTree.insert(newValue: 7)
binaryTree.insert(newValue: 9)

print(binaryTree.description)
//"value: 5, left = [], right = [value: 7, left = [], right = [value: 9, left = [], right = []]]\n"

var tree: BinaryTree<Int> = .empty
tree.insert(newValue: 7)
tree.insert(newValue: 10)
tree.insert(newValue: 2)
tree.insert(newValue: 1)
tree.insert(newValue: 5)
tree.insert(newValue: 9)

tree.traverseInOrder { print($0) }   // 1 2 5 7 9 10
tree.traversePreOrder { print($0) }  // 7 2 1 5 10 9
tree.traversePostOrder { print($0) } // 1 5 2 9 10 7
tree.search(searchValue: 5) //value: 5, left = [], right = []

escape

https://docs.swift.org/swift-book/LanguageGuide/Closures.html

Trie 트라이

접두사를 저장하기 좋은 구조

해시 테이블을 대체하기 좋다
충돌을 걱정하지 않아도 되며
해시 알고리즘이 없어도 되고
알파벳순서로 정렬되기 때문이다

항상 이미 존재하는 노드가 있으면 재사용한다 (노드를 찾는 것을 tries...)

“Cut”과 “Cute”는 “Cut”을 접두사로 가지기 때문에 4개의 노드를 사용한다

//참조타입이라 class로 구현하기
class TrieNode<T: Hashable> {   //딕셔너리의 키는 Hashable 프로토콜을 따라야 한다
    var value: T?
    weak var parent: TrieNode?  //reference cycle을 방지하기 위해 weak로 선언하기
    var children: [T: TrieNode] = [:]
    var isTerminating = false   //단어에 마침표를 찍기 cut. cut.e.
    
    init(value: T? = nil, parent: TrieNode? = nil) {
        self.value = value
        self.parent = parent
    }
    
    func add(child: T) {
        //딕셔너리에 없어야 한다
        guard children[child] == nil else { return }
        
        children[child] = TrieNode(value: child, parent: self)
    }
}

class Trie {
    typealias Node = TrieNode<Character>
    fileprivate let root: Node
    
    init() {
        root = Node()    //초기화하기
    }
}

extension Trie {
    func insert(word: String) {
        //비어있으면 insert를 멈춘다
        guard !word.isEmpty else {
            return
        }
        
        var currentNode = root
        
        let characters = Array(word.lowercased())    //String을 Character로 저장하기 위해 Array 사용
        var currentIndex = 0
        
        while currentIndex < characters.count {
            let character = characters[currentIndex]
            
            if let child = currentNode.children[character] {    //child딕셔너리에 있으면
                currentNode = child
            } else {
                currentNode.add(child: character)   //child딕셔너리에 추가
                currentNode = currentNode.children[character]!  //currentNode의 참조값을 새로운 노드로
            }
            
            currentIndex += 1   //다음 character로 넘어가기
        }
        
        //문자의 마지막에 마침표를 더하는 느낌
        if currentIndex == characters.count {
            currentNode.isTerminating = true
        }
    }
    
    //단어 유무 확인하기
    func contains(word: String) -> Bool {
        //비어있으면 종료
        guard !word.isEmpty else { return false }
        var currentNode = root
        
        let characters = Array(word.lowercased())
        var currentIndex = 0
        
        while currentIndex < characters.count, let child = currentNode.children[characters[currentIndex]] {
            currentIndex += 1
            currentNode = child
        }
        
        //currentIndex가 끝까지 도달하고 마침표가 있으면 특정 단어가 Trie에 있음을 의미한다
        if currentIndex == characters.count && currentNode.isTerminating {
            return true
        } else {
            return false
        }
    }
}

let trie = Trie()
trie.insert(word: "cute")
trie.contains(word: "cute") //true

trie.contains(word: "cut")  //flase
trie.insert(word: "cut")
trie.contains(word: "cut")  //true

출처:
https://www.raywenderlich.com/892-swift-algorithm-club-swift-trie-data-structure

공간분할트리