[스위프트 : 자료구조] AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능오짐

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

저는 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: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• [스위프트 : 자료구조] AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능오짐

• 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: #표현방식: #왜필요해?: #효율적: #간결성: #생략

AVL Tree: 자가 균형 트리

• AVL 트리가 뭐야?
• AVL 트리는 넓게 보면 트리의 일종이야. 트리의 한 부분이기 때문에 전체적인 큰 그림을 설명하고 시작할게.
• 트리를 시작으로 트리의 깊이우선탐색, 레벨 탐색등, 트리를 만들고 탐색하는 걸 했었지.
• 그 다음으로 자식 노드를 두 개만 가지는 이진트리로 트리의 의미를 좁혔었지?
• 이진 트리의 탐색에서는 in-order, pre-order, post-order 의 3 가지 방법으로 탐색을 해 봤었어.
• 그 다음으로 이진 탐색 트리야. 이것은 이진 트리라는 특징을 이용해서 트리의 삽입, 삭제, 탐색 연산을 '이상적인 상황' 에서 O(log n) 의 좋은 성능을 보여줬지.
• 여기에 붙은 '이상적인 상황' 이 이진 탐색 트리의 단점이었어. 이상적인 상황이 아니면 속도는 여전히 O(n) 으로 배열과 다를 바가 없었지.
• 이 단점을 극복하기 위해 만든 것이 AVL 트리야. 드디어 나왔지? 궁극적으로 O(log n)의 성능을 가진 이진 트리를 구현하기 위해 만든 것이지.
• 이진 탐색 트리에서 성능에 영향을 미치는 것은 트리의 'balance' 였어. 트리의 balance 는 아래 그림과 같아. 얼마나 편향되지 않고 중심을 잘 잡고있냐는 것이지.
• 결론: AVL 트리는 삽입, 삭제, 탐색 등 연산을 수행할 때 마다 트리 스스로 자신의 balance 를 확인하고, 필요할 때마다 balance 를 조정하는 트리이고 그래서 'Self-balancing Tree' 라고도 해. 

• AVL 트리를 왜 배워? 
• 여기까지 오려고 트리나 이진 트리 등등을 한거야. AVL 은 트리중에 성능이 아주 좋고 똑똑하거든.

• AVL 에서 balance 가 관건이지? balance 에 대해 자세히 알아보자. 난 여기서 3가지 경우로 나눌거야.
• 완전 균형 상태 ( Perfect balance ) 

• 충분한 균형 상태 ( good-enough balance )
  
• 위에서 처럼 완벽하게 균형이 잡힌 트리는 잘 없기 때문에 '최소한 이정도는 되야 되야 balance 트리다.' 라는 느낌.
• 가장 아래쪽 레벨을 제외하고 모든 레벨에서 노드가 가득 찬 상태야. 맨 마지막 부분만 노드 자리가 비는 거지.

• 비 균형 상태 ( Unbalanced )
  
• 균형하지 않은 트리는 성능 저하의 원인이야. 이 문제를 해결하는 것이 AVL 트리의 목표!

                                 

                     

• AVL Tree 구성

• 구성 보면서 큰그림 그려봐!

• AVLNode 클래스

• 전에 구현했던 이진 트리 노드와 탐색 알고리즘 3 가지

• height 프로퍼티 와 자식노드의 height 를 이용한 연산프로퍼티들

// 이진 트리의 노드 와 같고 이름만 AVLNode 로 수정했삼~
public class AVLNode<Element> {
    public var value: Element
    public var leftChild: AVLNode?
    public var rightChild: AVLNode?
    public var height = 0 // 트리가 balance 인지 unbalance 인지 확인할 때 사용할 프로퍼티
    public var balanceFactor: Int {
    // 자식노드의 높이 차를 이용해서 unbalance 를 식별할 예정이야.
        return leftHeight - rightHeight
    }
    public var leftHeight: Int { 
        // nil 이면 -1 이란 뜻은 자식 노드가 없는 곳의 높이를 -1 로 생각하라는 뜻입니다.
        // 이렇게 '노드가 없는 상태' 를 설정해 준 것입니다. 이유는 구현하면서 알게 될거에요.
        return leftChild?.height ?? -1
    }
    public var rightHeight: Int {
        return rightChild?.height ?? -1
    }
    public init(value: Element) 
    public func traverseInOrder(visit: (Element) -> Void)
    public func traversePreOrder(visit: (Element) -> Void)
    public func traversePostOrder(visit: (Element) -> Void) 
}

• AVLTree 클래스

• 이진 탐색 트리에 트리의 balance 확인하는 balanced() 와 그에 따른 rotate 메소드 4 가지 가 추가된거 보이쥬?

// 이진 탐색 트리 랑 같습니다.
public struct AVLTree<Element: Comparable> {
    public private(set) var root: AVLNode<Element>?
    public init() {}
    // 트리의 노드 회전시켜서 balance 맞추게 하는 메소드 4가지, 외부에서 맞추는 것이 아니라 트리 스스로 맞추기 때문에 private
    // (1 / 4) 왼쪽으로 회전. 오른 자식 노드가 unbalance 만들 면 왼쪽으로 회전시켜서 균형맞춰!
    private func leftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> 
    // (2 / 4) 오른쪽 회전. 왼 자식노드가 unbalance 만들 면 오른쪽으로 회전 시킴
    private func rightRotate(_ node: AVLNode<Element>) -> AVLNode<Element> 
    // (3 / 4) 오른쪽이후 왼쪽으로 회전. 꼬여있을 때 하는거.
    private func rightLeftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> 
    // (4 / 4) 왼쪽이후 오른쪽으로 회전
    private func leftRightRotate(_ node: AVLNode<Element>) -> AVLNode<Element>
    // 매개변수로 들어온 노드를 루트노드로 하는 서브트리의 balance 를 확인하고 그에 따른 조치를 취하게 하는 메소드
    private func balanced(_ node: AVLNode<Element>) -> AVLNode<Element>
// 여기부터 이진 탐색 트리 연산들. 삽입 , 탐색, 삭제 순.
    public mutating func insert(_ value: Element) // 삽입, 외부호출용 insert()와 내부을 담당하는 insert(from) 전에 헀쥬?
    private func insert(from node: AVLNode<Element>?, value: Element) -> AVLNode<Element>
    public func contains(_ value: Element) -> Bool // 원하는 노드 찾기
    var min: AVLNode { // 노드의 최소값 구하는
        return leftChild?.min ?? self
    }
    public mutating func remove(_ value: Element) // 삭제연산
    private func remove(node: AVLNode<Element>?, value: Element) -> AVLNode<Element>?
}

---

• 구현: AVLNode
• 새로 추가된 부분만 구현하고 설명할게! 전체소스 궁금하면 여기에 있어!

public class AVLNode<Element> {
    public var height = 0 
    // 여기서 높이란 해당 노드부터 leaf 노드 까지의 길이를 뜻하는 거야. 초기값은 0
    // height 프로퍼티가 balance 상태인지 판단하는 기준이야. 
    // height 를 이용해서 leftHeight, rightHeight를 구하고 이를 이용해서 balanceFactor 를 구한다.
    public var balanceFactor: Int {
        return leftHeight - rightHeight // 왼쪽과 오른쪽 자식노드의 height 프로퍼티 차이.
    }
    public var leftHeight: Int { 
        // nil 이면 -1 는 자식노드 없으면 높이 -1 로 친다는 거야.
        // leaf 노드가 0 이기 때문에 높이차가 1 이상이라는 걸 표현하기 위해서는 nil 일 때 -1 로 설정해주면 되.
        return leftChild?.height ?? -1
    }
    public var rightHeight: Int {
        return rightChild?.height ?? -1
    }
}

• height 프로퍼티에 대해서
• 이제부터 설명할 것들은 이후에 내용을 스무스하게 이해하기 위해 필요한 것들이야! 
• 주석으로 적어놓은 것과 같이 해당 노드부터 leaf 노드까지의 길이를 뜻하는 거야.
• 아래 그림을 보면 노드들 각자는 자식노드를 타고 내려가 leaf 노드까지의 길이를 height 라고 뜻하는 걸 알 수 있지?

                    

• balanceFactor 에 대해서

• 코드에서 결정적으로 balance 상태를 판별하는 건 height 를 활용한 balanceFactor 를 통해서 할거야. 

• 왼쪽 과 오른 자식 노드의 높이의 차를 뜻하는 건데 아래 그림과 같아. 빈 노드는 높이를 '-1' 로 생각한다고 했었지?

• 녹색이 balanceFactor

• 파란색이 height

                            

• 여기에 40의 값을 가지고 있는 노드를 삽입해보자.
• 25의 노드의 balanceFactor 가 '-2'가 됬지?
• 결론: 어떤 노드의 balanceFactor 가 -2 or 2 를 가지면 unbalance 상태를 가지는 거야.
• 구현하면서 알게 되겠지만 아래 그림처럼 balanceFactor가 '-2' 를 가진 노드는 오른쪽 자식 노드쪽에 노드가 많아서( 무거워서? ) 불균형이 생겼다는 걸 뜻해.
• 마찬가지로 '2'를 가진 노드는 왼쪽 자식 노드가 많아서 불균형이 생긴거야.
• 노파심에 50노드도 balanceFactor 가 2 라서 살짝 이건 뭘까 하는 의문이 들것 같은데 이건 그냥 넘어가줘. 구현하면서 알게 될거야~

---

• AVLTree 구현하기 전에
• balanceFactor 가 2 or -2 가 되면 unbalance 트리라는 걸 알았지? 이 결과에 따라서 balance 로 바꾸는게 AVL 트리라고 했잖아?
• 여기서 unbalance 트리를 balance 트리로 어떻게 Rotation( 회전 ) 을 활용해서 구현하고 AVLTree 구현할게!
• Rotations (left rotation / left-right rotation / right rotation / right-left rotation 4가지)
• 4가지 인 이유는 unbalance 한 경우의 수가 4개이기 때문이야. 자 봐
• left rotation
• 위의 그림으로 설명할게 봐봐.
• 37 노드가 한 레벨 위로 올라가도록 왼쪽으로 회전시켜서 새로운 트리를 만들면 balance 로 되지?

• 더 일반적으로 설명하면 아래와 같아. 오른쪽이 무거우니까 왼쪽으로 회전시켜서 균형을 맞춘다고 생각하면 쉬워!
  

                          

• left rotation 구현

    // (1 / 4) 왼쪽으로 회전. 오른 자식 노드가 unbalance 만들 면 왼쪽으로 회전시켜서 균형맞추기.
     private func leftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
        let pivot = node.rightChild! // pivot 은 '중심점' 을 뜻함.
        // 매개변수로 들어오는 node를 루트노드로 하는 서브트리를 회전시키는 거야. 위 그림에서는 25 네
        // 25 의 오른 자식노드인 '27' 이 pivot 이 되겠네. pivot 은 회전될 서브 트리의 루트노드가 될 아이야.
        node.rightChild = pivot.leftChild
        // pivot 이 루트 노드가 될 거잖아. 그럼 내려가는 x 노드의 오른쪽 노드는 
        // x 노드보단 크고 y(pivot) 노드 보단 작은 b 노드가 되는거야. 파란색 펜으로 표시한 거야.
        pivot.leftChild = node
        // 왕권 교체 . x 노드는 y (pivot) 노드의 왼쪽 자식 노드가 되는 시점.
        node.height = max(node.leftHeight, node.rightHeight) + 1 // 노드 위치 바뀌었으니 heiht 수정
        pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1 // 마찬 가지.
        return pivot // 왕이된 놈 리턴. 그러니까 매개변수로 내려갈놈, 넣으면 왕이된놈 반환하는 거임.
    }

---

• right rotation
• left rotation 과 대칭관계야. 아래 그림 처럼!
• 그러므로 왼쪽이 무거워서 오른쪽으로 회전하는 거겠지?

                       

• right rotation 구현

    // (2 / 4) 오른쪽 회전. 왼 자식노드가 unbalance 만들 면 오른쪽으로 회전 시킴.
    private func rightRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
        let pivot = node.leftChild!
        node.leftChild = pivot.rightChild
        pivot.rightChild = node
        node.height = max(node.leftHeight, node.rightHeight) + 1
        pivot.height = max(pivot.leftHeight, pivot.rightHeight) + 1
        return pivot
    }

---

• right - left rotation
• 위의 경우들과는 다르게 아래 그림처럼 트리에 36이 삽입되었다고 해보자. 
• balanceFactor 가 '-2' 라서 분명 unbalance 트리인데 .. 마지막 노드 어떻게 올리지... 멘붕오지?
• 이럴 경우에 그림과 같이 두 번의 회전을 통해 balance 로 만드는 거야.

• right - left rotation 구현

    // (3 / 4) 오른쪽이후 왼쪽으로 회전. 꼬여있을 때 하는거.
    private func rightLeftRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
        guard let rightChild = node.rightChild else { // 옵셔널 해제 해주고.
            return node // nil 이면 그냥 반환해버림
        }
        node.rightChild = rightRotate(rightChild) 
        // 먼저 오른 자식노드를 오른 회전 시킨 노드로 수정하고.
        return leftRotate(node) // 최종 왼쪽 회전 시킨 노드를 반환
    }

---

• right - left rotation

• 아래 그림처럼 위의 left - right rotation과 대칭관계야.

• right - left rotation 구현

    // (4 / 4) 왼쪽이후 오른쪽으로 회전
    private func leftRightRotate(_ node: AVLNode<Element>) -> AVLNode<Element> {
        guard let leftChild = node.leftChild else { return node}
        node.leftChild = leftRotate(leftChild) 
        return rightRotate(node)
    }

---

• balanced 구현
• 지금까지 트리가 unbalance 인 상태에서 balance 로 만들기 위해 rotation 메소드 4 가지를 사용했지?
• 이 4 가지 메소드를 적절한 상황에서 사용할 수 있도록 하는 balanced() 메소드를 구현할 거야.
• 이 메소드는 노드의 balanceFactor를 기준으로 트리가 unbalance 인지 확인하는 원리야.

    // 밸런스 맞추는 게 필요한지 아닌지 판단하는 메소드
    private func balanced(_ node: AVLNode<Element>) -> AVLNode<Element> {
        // 매개변수로 들어오는 해당 노드의 balancaFactor 로 unbalance 여부를 판단하는 메소드
        // balanceFactor 가 2 or 2 라서 unbalance 면 balance 트리로 수정하는 메소드를 내부에서으로 호출함
        switch node.balanceFactor { // 스위치 구문 활용하자.
        case 2:
            // 왼쪽 자식노드 쪽이 무거운 unbalance 트리.
            if let leftChild = node.leftChild, leftChild.balanceFactor == -1 {
                // let leftChild = node.leftChild 로 먼저 옵셔널 해제 해주구~
                // 아 if 조건문에서 && 가 아닌 , 쓰는 건 앞에꺼 먼저 만족한 후 뒤의 구문 만족해야 한다는 뜻이야.
                // 왼쪽 자식노드가 무거운 (높이차가 2) 인 상태에서
                // , 뒤쪽 구문인 'leftChild.balanceFactor == -1' 은 중간에 있는 놈이 오른쪽으로 꺽인다는 뜻이야.
                // 구부러져 있는 상태에서는 사용하려고 rotation 메소드 중에 left-Right rotation 정의했었지?
                return leftRightRotate(node)
            }else {
                // 그런경우 아니라면 왼쪽이 무거우니까, 오른쪽으로 회전시키면 되.
                return rightRotate(node)
            }
        case -2:
            // 오른쪽 자식노드 무거워 
            if let rightChild = node.rightChild, rightChild.balanceFactor == 1 {
                // 오른쪽 자식쪽이 무거운 상태에서 꺾여있다면 회전 2번 해야했지?
                return rightLeftRotate(node)
            }else {
                return leftRotate(node) // 오른쪽이 무거우니까 왼쪽으로 회전시켜서 balance 맞추자
            }
        default: // balance 상태에서는 매개변수로 들어온 노드를 그대로 반환시키는 거야. 수정하지 않고.
            return node
        }
    }

• 그림으로 보여줄게
• 왼쪽 트리는 중간 노드의 balanceFactor가 1 이라 꺽이지 않은 unbalance
• 오른쪽 트리는 중간 노드의 balanceFactor 가 -1 이라 꺽인 unbalance 
• 이렇게 구분이 가능하다는 거야. 구분이 가능하기 때문에 이 구분을 기준으로 4가지 rotation 메소드 중 적절한 것을 선택하는 원리야.

• ---

  구현: AVLTree

• 위에서 AVLTree 구현하기 전에 크게 두 가지를 했어.

• 트리가 unbalance 인지 확인하고 unbalance 라면 balance 인 트리로 수정하게 하는 일을 수행하는 balanced() 메소드 

• balanced() 메소드 내에서 unbalance 트리를 balance 트리로 수정하는 방법인 4가지 rotation() 메소드

• 위에서 정의한 메소드들을 이진탐색트리에 적용해서 AVLTree 를 만들거야.  

• insert, remove 연산에만 적용이 되고 contain 은 이진 탐색 트리와 바뀌는 내용은 없어. 그냥 트리에서 값 있는지 확인하는 메소드 이기 때문에. 

• AVLTree

---

• insert 메소드

    // 이진 탐색 트리랑 틀은 전부 같습니다.
    public mutating func insert(_ value: Element) {
        root = insert(from: root, value: value)
    }
    
    private func insert(from node: AVLNode<Element>?, value: Element) -> AVLNode<Element> {
        guard let node = node else {
            return AVLNode(value: value)
        }
        if value < node.value {
            node.leftChild = insert(from: node.leftChild, value: value)
            // 재귀함수에서 방향.
        } else {
            node.rightChild = insert(from: node.rightChild, value: value)
        }
        // 여기 추가하면 탐색하면서 높이가 2 이상 차이나는 게 있으면 바꾸구 리턴 반복
        let balancedNode = balanced(node) // 밸런스 필요한지 판단함. 필요하면 바꿈.
        balancedNode.height = max(balancedNode.leftHeight, balancedNode.rightHeight) + 1
        // 구조가 변했을 가능성이 있으므로 height 프로퍼티 재설정 해주구.
        return balancedNode
    }

• 헷갈리시는 친구들을 위해서
• 우리는 insert() 를 추가할 때마다 호출기 때문에 balance 조정은 내부적으로 그때 그때, insert 메소드가 호출될 때 실시간으로 같이 이루어 지는 거야.
• 실행부분을 보면 납득할 거야. 봐봐
• insert 실행

• 이 실행을 순서대로 뜯어볼거야. 호출 시점에 어떤 일이 일어나는지!
  

• tree.insert(5) 부분에 대해서 의문점.
  
• balanceFactor 가 -2 인 노드가 2, 3 두개가 있는데 그럼 rotation 메소드가 두번 호출되서 구조가 두번 바뀌는 건가요? 
• 이 의문점이 드는 이유는 재귀호출을 잘 이해하지 못해서 입니다. 저도 이런 의문점이 들어서 소스코드를 하나하나 뜯어서 봤거든.
• 재귀호출에 의해서 가장 끝자락에서, 위의 예에서는 '노드 3' 에서 밸런스 체크하고 rotation 메소드 호출해서 balance 맞추고 그 결과가 위의 그림에서 보이지?
• 그 이후에 '노드 2' 에 대한 밸런스 체크가 이루어 지는거야. 재귀호출 이기 때문에 루트 노드에 대한 명령문이 가장 마지막에 실행되니까!
• 이미 balance 조정되서 balance 상태인 '노드 2' 의 balance 를 체크하는 balanced() 메소드가 호출되는 시점은 이 트리야.

                                                                                

• 자 의문점으로 돌아가서  balanceFactor 의 값이 -2 인 노드가 두 개 존재하더라도 실제로 rotation 메소드가  두번 실행는게 아니라 끝자락에서 밸러스조절이 이미 완료되서 다음 밸러스 체크는 balanceFactor 가 -2 가 나오지 않는거지. 

---

• remove 메소드
• 원리는 insert 에서 모두 설명했어. remove 메소드에도 똑같이 적용되.

    // 이진 탐색 트리랑 틀은 전부 같습니다.
public mutating func remove(_ value: Element) {
        root = remove(node: root, value: value)
    }
    private func remove(node: AVLNode<Element>?, value: Element) -> AVLNode<Element>? {
        guard let node = node else {
            return nil
        }
        if value == node.value {
            if node.leftChild == nil && node.rightChild == nil {
                return nil
            }
            if node.leftChild == nil {
                return node.rightChild
            }
            if node.rightChild == nil {
                return node.leftChild
            }
            node.value = node.rightChild!.min.value
            node.rightChild = remove(node: node.rightChild, value: node.value)
        } else if value < node.value {
            node.leftChild = remove(node: node.leftChild, value: value)
        } else {
            node.rightChild = remove(node: node.rightChild, value: value)
        }
        // 여기부터 추가되는 부분.
        let balanceNode = balanced(node)
        balanceNode.height = max(balanceNode.leftHeight, balanceNode.rightHeight) + 1
        return balanceNode
    }

• remove 실행

• AVL Tree 정리!

• AVL 트리는 이진 탐색 트리의 확장형 이기 때문에 기본적인 모든 소스코드는 전에 구현했던 이진 탐색 트리에서 가져왔고 여기에 몇몇 코드들을 추가하는 방식이야.

• 목표는 이진 트리가 자기 자신이 'unbalance' 상태가 되면 스스로 구조를 수정해서 'balance' 상태로 수정되게 만들거야.

• 이를 구현하려면 트리가 'balance' 인지 'unbalance' 인지를 알 수 있어야 해. 어떤 상태인지 알아서 수정하는 명령을 내릴 거니까.

• 이를 가능하게 만든 것이 AVLNode 클래스의 height 프로퍼티야. 요걸 활용해서 leftChild, rightChild 를 만들고 또 이것들을 활용해서 balanceFactor 프로퍼티를 만들어.

• 이 프로퍼티들을 활용해서 balance 를 식별하는데 이 기능을 하는 메소드가 balanced() 였지?

•  balanced() 에서 unbalance 로 판별된 아이들은 balance 가 되기 위해 트리를 수정하는 작업을 했던게 4가지 경우의 rotation() 메소드였지?

• 이 메소드들을 insert, remove 의 재귀호출 메소드에 적용해서 트리가 실시간으로 balance 를 유지하게 만들었고

• 우리는 항상 O(log n) 의 성능을 내는 자료구조인 AVLTree 를 만든거야. 끝 ! 수고했어. 전체소스코드는 내 깃허브에 있어! 링크걸어줄게!  

전체 소스 코드