스위프트: 이진 탐색 트리(1 / 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: #표현방식: #왜필요해?: #효율적: #간결성: #생략

이진 탐색 트리 : Binary Search Tree

• 이진 탐색 트리가 뭐야? 
• 이진 트리의 일종이고
• 탐색, 삽입, 제거 연산이 이상적인 상황에서 시간 복잡도가 O(log n) 이야. 
• 배열이나 연결리스트의 경우 O(n) 에 비해서 매우 빠른 속도지?
• 여기서 주의해야 할 것이 '이상적인 상황' 에서 그렇다는 거야. 이 '이상적인 상황' 이란 것은 이후에 설명할게?
• 이진 탐색 트리를 왜 배워?
• 자료구조가 발전하면서 더 빠른 속도의 연산 속도를 가지는 것을 생각하게 된거야.
• 이게 구현해 놓고 보니까 예전의 배열이나 연결리스트보다 훨씬 빠른거지. 이런 발전 과정을 배우는 거야. 
• '어떤 아이디어로 좋은 성능의 자료구조와 알고리즘을 만들어 냈을까' 라는 걸 배우는 거지.
• 어떻게 O(log n) 의 속도를 내는거야? 배열이나 연결리스트 보다 어떻게 더 빨라?
• 이진 탐색 트리는 트리를 구성할 때 2가지 규칙을 정함으로써 이 속도를 구현했어.
• 2가지 규칙은 아래와 같아
• 왼쪽 자식노드의 값은 반드시 부모 노드의 값보다 작아야 해.
• 오른쪽 자식노드의 값은 반드시 부모 노드의 값보다 같거나, 커야해.
• 자 이 두 가지 규칙을 따르는 이진 탐색 트리가 배열이랑 어떤 차이 때문에 속도가 빠른건지 보여줄게. 
• 배열과 이진 탐색 트리 비교.
• 아래와 같이 배열과 이진 탐색 트리가 있다고 생각할게. 이진탐색트리는 루트노드가 40 으로 가정했어~

• 각각의 자료구조에서 새로운 값 0을 삽입한다고 해보자
  
• 배열
• 0 이 첫 번째 인덱스에 삽입되면 배열의 나머지 값들이 한칸씩 뒤로 이동해야 하므로 n 번의 반복 연산이 수행되기 때문에 O(n) 의 수행속도를 가지지?

• 이진 탐색 트리
• 아래 그림을 보면 단 2번의 수행 만으로 '0' 이 원하는 곳으로 가는 것을 알 수 있지? 이 차이야. 존나 빠른 거지.
• 이게 탐색이나 제거연산을 수행할 때도 마찬가지야.

                                     

• 이진 탐색 트리의 단점과 위에서 말한 '이상적인 상황'에 대해서

• 아래 그림와 같은 트리가 있다고 해보자

• 0을 루트노드로 시작해서 4까지 순서대로 트리에 삽입하면 이런 구조가 되겠지? 부모노드보다 1씩 큰 값들이 삽입되니까 오른쪽으로 추가되잖아.

• 이런 이진트리에 새로운 값 5를 추가한다면?

배열이랑 다를 바 없이 연산을 4번 수행하네?  최악의 상황에서는 수행속도가 배열과 같은 O(n) 이네.

• 이런 트리를 'unbalanced' 혹은 '편향' 되었다고 표현해.
• 이럴 거면 트리를 왜 쓰나 싶지? 이게 이진 탐색 트리의 단점이야. 최악의 상황이 존재한다는 것이지.
• 위에서 설명했던 '이상적인 상황'은 balanced 된 트리를 말하는 거야. 아래 그림에서 오른쪽 처럼

---

• 구성 
• 전체적인 구성은 아래와 같아. 시작하기 전에 큰 그림 그려봐~
• BinaryNode 클래스는 전에 이진트리 에서 구현한 걸 가져온 거야. 

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>?{}
}

• 구현: BinarySearchTree

public struct BinarySearchTree<Element: Comparable> {
    public private(set) var root: BinaryNode<Element>? 
    // private(set) 은 set(write 속성) 은 private 으로 설정한다는 뜻이야. get(read 속성)은 앞의 public 을 따르는 거지.
    // get, set 을 구분해서 설정하고 싶을때 access control 키워드 안에 get, set 넣어줄 수 있어~
    init() {} // 초기화 함수..인대 왜 흰색으로 표시될까? 
}

• 삽입 구현 ( insert(:), insert(from: ) )

    // 재귀호출 할거야.
    private func insert(from node: BinaryNode<Element>?, value: Element) -> BinaryNode<Element> { 
        // 빈 노드에 삽입할 가능성 있어서 첫 매개변수 옵셔널 넣어줄게.
        // private 은 어차피 아래의 mutating func insert() 에서만 호출할 것이라서 붙인거야. 외부에서 호출할 일이 없쥬?
        guard let node = node else{ return BinaryNode(value: value)}
        // 이 구문은 두 가지 역할이 있어. 옵셔널 해제, 그리고 해당 위치에 값 삽입.
        // 루트노드가 nil 인 빈 노드라면 루트 노드의 값은 반환값인 삽입하는 BinaryNode 가 되지?
        if value < node.value { // value : 삽입될 노드의 값이 부모노드 보다 작으면 ?
            node.leftChild = insert(from: node.leftChild, value: value) // 왼쪽 노드로 가서 재귀호출.
        }else { // 삽입될 노드의 값이 부모노드와 같거나 그보다 크면?
            node.rightChild = insert(from: node.rightChild, value: value) // 오른쪽 노드로 가서 재귀호출
        }
        return node 
        // 탐색 하다가 자식 노드가 nil 인 삽입할 노드에 도착하면 guard 구문의 return 으로 값이 삽입되
        // 마지막의 return 이랑 guard 의 return 은 다른 함수의 범위에서 반환되는 값이라는게 헷갈릴 수 있어.
        // guard 의 return 은 마지막에 호출된 insert메소드의 return 이고
        // 마지막의 return 은 node 가 nil 이 아닐 때 계속 호출되는 return 이고.
        // 헷갈리면 예를들어 탐색이 많으면 이 커다란 insert 안에 무수히 많은 insert 가 존재하겠지?
        // 삽입하고자 하는 곳 찾아 가야하니까 무수히 많은 insert() 를 호출해서 찾아가잖아.
        // 다 찾았을 때 guard 에 의해 return 이 호출 되는 건 마지막 insert 메소드의 범위에서의 return 인 것이지.
        // 재귀호출에서 이 함수의 범위를 잘 이해해야해. 함수안에서 여러 함수가 호출되니까 이 범위가 헷갈리거든.
        // 마지막 return 은 재귀호출의 특징인 처음 호출한 root노드에 대한 node 가 가장 마지막에 return 하기 때문에
        // 모든 변경사항을 담은 root 노드의 node 가 마지막에 return 하는 거야.
    }
    public mutating func insert(_ value: Element) {
        root = insert(from: root, value: value)  
        // 메소드를 호출할 때 쓰는 메소드야. BinarySearchTree의 인스턴스를 통해 호출할 메소드.
        // 구조체 내부에 정의한 root 를 변경하므로 mutating 키워드.
        // from 매개 변수에는 항상 root 노드가 들어간다는 것을 유의.
    }
 

• 실행: insert() 

소스파일