스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제

안녕하세요 !  씩이 입니다!

저는 Swift 와 iOS 를 공부하고 연구하는 대딩 ( 대학생 ) 이구요!

같은 분야를 공부하는 분들에게 조금이라도 도움이 주고 싶어서 공부하는 것들을 공유합니다.

제 3자가 있다고 가정하고 설명하기 때문에 존대를 하지 않는점 이해 부탁드립니다.

공유가 미래 라고 생각합니다. 

한국의 모든 개발자분들 존경합니다!

---

• Swift version : Swift 4.2  ( 18.09. 01 ~ ) Swift 언어
• 참고한 것들
• DataStructures and Algorithms in Swift
• Swift-Algorithm-club 깃허브 
• 스위프트 데이터 구조와 알고리즘

• 씩이 Github
• 자료구조 소스파일 있습니다.
• iOS 관련 자료들, 정보들 정리해 두었습니다.

• 스위프트로 구현한 자료구조 : DataStructures in Swift4
• Swift4 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조
  
• Swift4 : 연결리스트 (2 / 3) : #LinkedList : #값 추가하기, push, append : #값 삽입하기,insert
• Swift4 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: )
• Swift4: 스택: #Stack: #자료구조: #DataStructure: #쌓기
• Swift4: 큐 (1 / 4): Queue: #자료구조: #배열로 구현한 큐: #배열의원리
• Swift4: 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList
• Swift4: 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음
• Swift4: 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!
  
• 스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4
• 스위프트: 이진 탐색 트리(1 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• 스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제

• Swift 주제별 분류
• Swift4 : 제어 전달 명령문( Control Transfer Statement ) : #continue, #break, #return 키워드
• Swift4 : 클래스와 구조체 : #값을 대하는 방식 : #참조타입, 값 타입 : #===
• Swift4 : 프로퍼티 : #Property : #get, set : #willSet, didSet
• Swift4 : 메소드 : #Method : #영향력 범위 : #self : #mutating : #값타입 수정
• Swift4 : 프로토콜 1 : #Protocol : #설계 : #요구사항 : #델리게이트 패턴 전처리 (1 / 2)
• Swift4 : 프로토콜 2 : #델리게이트 패턴 : #델리게이션 (2 / 2)
• Swift4 : 제네릭 : #Generics : #왜필요해? : #where키워드 : #제약사항걸기
• Swift4 : 자동 참조 카운팅 : #Automatic Referece Counting : #ARC :#강한참조 : #Strong Reference Cycle : #메모리 누수
• Swift4 : 클로저: Closure: #표현방식: #왜필요해?: #효율적: #간결성: #생략

이진 탐색 트리(2 / 2) : Binary Search Tree

• 구성 
• 두 번째 포스팅 이니까 탐색과 제거 연산을 구현할 예정~

public struct BinarySearchTree<Element: Comparable> {
    public private(set) var root: BinaryNode<Element>? 
    init() {}
    //MARK: - 삽입 메소드 // (1 / 2)
    public mutating func insert(_ value: Element) {}
    private func insert(from node: BinaryNode<Element>?, value: Element) -> BinaryNode<Element> {}
    //MARK: - 탐색 메소드 // (2 / 2)
    public func contains(_ value: Element) -> Bool {}
    //MARK: - 제거 메소드 // (2 / 2)
    public mutating func remove(_ value: Element) {}
    private func remove(node: BinaryNode<Element>?, value: Element) -> BinaryNode<Element>?{}
}

---

• 탐색 구현: contains() 
• 2가지 방법으로 구현할 거야. 성능이 좋은 순으로^^
• 이렇게 하면 traverseInOrder 메소드를 사용해서 트리의 모든 노드를 탐색하는 거쥬? traverseInOrder는 이진트리에 나옵니다~

    public func contains(_ value: Element) -> Bool {
        guard let root = root else{ return false } // 빈 노드 체크 해주고
        
        var found = false
        root.traverseInOrder { // 이진탐색에서 했던 traverseInOrder 메소드를 사용해서 탐색한다~
            /* 클로져 이기 때문에 이렇게 매개변수 생략해서 작성해도 무방해! 헷갈릴까봐 아래처럼 작성한거야
             if $0 == value {
                found = true
             }
            */
            (a) in // 매개변수 a 는 이진노드의 값 (value) 임!
            if a == value {
                found = true
            }
        }
        return found
    }

• 모든 노드를 검사할 필요가 없어. 이진 탐색 트리는 자식노드에 규칙이 있기 때문이지 ( 값이 작으면 왼쪽, 크거나 같으면 오른쪽 )
• 효율적이지? 당연히 성능도 좋아지지~

    public func contains(_ value: Element) -> Bool {
        var current = root 
        
        while let node = current { // current 가 nil 이 아닐 때 까지 반복
            if node.value == value{ // nil 이 아니면 current 노드 검사
                return true
            }
            if value < node.value { // 매개변수 value 가 현재노드 value 보다 작다면 왼쪽이쥬?
                current = current?.leftChild
            } else {
                current = current?.rightChild // 반대면 오른쪽이쥬?
            }
        }
        return false
    }

• 탐색 구현: contains()
• exampleTree 는 저번 포스팅에서 구현했던 이진탐색 트리입니다.

---

• 제거 구현하기 전에 제거하는 연산은 3가지의 경우로 나뉘어.
• 1.  leaf node 인 경우 -> 그냥 삭제하면 되쥬?

• 2. 자식 노드를 하나만 가지고 있는 경우 -> 제거한 후 자식노드가 한칸 위로 올라오쥬?

• 3. 자식 노드가 두개 모두 있는 경우
• 아래 그림에서 25를 삭제한다고 해 볼게.
• 이제 자식 노드를 올리면 둘 중 누구를 올려야 할 지 딜레마가 오기 시작하쥬?
• 12를 올리면  37은 어디에 붙일 것이며, 37을 올리는것도 마찬가지고, 둘다 올리면 자식노드가 3개가 되서 이진트리가 아닌게 되는데..
• 이 때에는 오른 자식노드의 가장 작은 값을 올리면 됩니다. 
• 오른 노드의 가장 작은 값은 오른 노드를 루트 노드로 하는 트리라고 생각하고 왼쪽 우선 탐색으로 나온 첫 번째 값, 즉 가장 왼쪽에서 가장 아래에 있는 값임.

• 제거 구현: remove(), remove(from: ) , 최솟값 구하는 min 프로퍼티 까지

    // 삽입과 마찬가지로 재귀호출
    private func remove(node: BinaryNode<Element>?, value: Element) -> BinaryNode<Element>?{
        guard let node = node else { return nil } // 빈 노드에서 제거하면 nil 반환.
        if value == node.value {
            // 요기가 이제 지우는 거야. 3 가지 경우로 나뉘는
            if node.leftChild == nil && node.rightChild == nil { // 1. leaf node 면!
                return nil // 그냥 없애버리면 되므로 nil 반환~
            }
            if node.leftChild == nil { // 2.1 오른쪽노드만 존재할 때
                return node.rightChild // 해당 노드를 지우고 오른쪽 자식노드로 수정되는 거임. 한칸 올라오니까
            }
            if node.rightChild == nil { // 2.2 왼쪽 노드만 존재할 때
                return node.leftChild // 해당 노드를 지우고 왼쪽 자식 노드로 수정되는 거임.
            }
            node.value = node.rightChild!.min.value // 3. 자식 노드가 두개 모두 존재할 때
            // 자식노드 전부 있을 경우 오른노드쪽에서 최소값 구하고 최소값으로 수정.
            node.rightChild = remove(node: node.rightChild, value: node.value)
            // 값은 수정했고 수정한 값 제거하려고 오른쪽을 시작으로 remove 메소드 다시 재귀호출.
            // value 부분을 수정한 값인 node.value 이 들어가 있지? 없애는 값이 node.value 니까~
            // 삭제되는 노드는 leaf 노드가 삭제되는 방식으로 삭제 되겠네. 왼쪽 최소값은 leaf 노드 니까
        } else if value < node.value { // 삽입 할 때랑 같지? 탐색하는 거야.
            node.leftChild = remove(node: node.leftChild, value: value)
        } else {
            node.rightChild = remove(node: node.rightChild, value: value)
        }
        return node
    }
 
    public mutating func remove(_ value: Element) {
        // 실제로 호출되는 메소드. insert 때 봤쥬? 
        root = remove(node: root, value: value)
    }
 
extension BinaryNode { // 제거 연산에서 두 자식노드 모두 가진 노드 제거할 때 오른노드의 최솟값 했었지?
    var min: BinaryNode {
        return leftChild?.min ?? self 
        // leftChild 가 nil 이 아니면 왼쪽 , nil 이면 self. 재귀호출로 최솟값 구해버림.
        // 왼쪽 자식노드가 nil 일 때까지 계속 가다가 nil 이면 그에 해당하는 BinaryNode 인 self 반환. self 는 최소값 노드임.
    }
}

• 제거 실행: remove()

exampleTree는 위에서 예를 든 트리와 똑같이 만들었습니다.

삭제 전.

삭제 후.

전체 소스 파일