트리 기초 공부

트리 : 노드의 집합

• 루트 노드(부모X) vs 리프 노드(자식X)
• 트리는 서브 트리로 구성, 서브 트리도 서브 트리로 구성

다양한 트리 종류

• B트리, R트리, AVL트리, 스플레이 트리, 레드블랙트리 … (많은 트리들...)
• 이중 레드 블랙트리는 검색, 삽입, 삭제 등 작업에 있어 최악의 성능을 나타냄 → 이걸 왜? : 최악의 성능은 역으로 실시간 데이터 처리 or 개발에서 최악의 시나리오를 검토할 수 있게 해준다.

이진 트리

• 자식 노드의 수가 최대 2인 트리 (0~2)
• 완전 이진 트리 : 마지막 노드 앞까지 노드가 전부 채워져있는 이진 트리
• 포화 이진 트리 : 리프 노드의 레벨이 모두 동일하고 모든 레벨이 가득 채워져 있는 트리 (레벨 = 루트 노드 까지의 거리 + 1, 층이라고 생각하면 편함)

이진 탐색 트리

• 특정한 조건에 의해 구성된 이진 트리
• O(n) ~ O(logN) 정도의 탐색 시간이 걸림
• 조건 : 왼쪽 노드는 자신보다 값이 작고 오른쪽 노드는 자신보다 값이 크다
• 조건을 통해 알 수 있는 것 : 각 노드는 왼쪽 서브 트리 보다 큰 값이고 오른쪽 서브 트리 보다는 작은 값이다.

트리 기본 코드

public class Node<T:Comparable> {
    var value: T // 노드 값
    var parent: Node? // 부모 노드 - 루트 노드는 부모가 없음
    var leftNode: Node? // 왼쪽 자식 노드
    var rightNode: Node? // 오른쪽 자식 노드

    // 이러면 초기화 할때 변수를 전부 넣어줘야함, 기본값 지정
    init(value: T, parent: Node? = nil, leftNode: Node? = nil, rightNode: Node? = nil) {
        self.value = value
        self.parent = parent
        self.leftNode = leftNode
        self.rightNode = rightNode
    }
    func isRoot() -> Bool { // 루트 노드 인지 판단
        if self.parent == nil { return true }
        return false
    }
    func addNode(_ value: T){ // 노드 삽입
        if value < self.value { // 왼쪽 자식에 삽입
            if let leftNode = self.leftNode { // 왼쪽 자식이 존재 - 삽입을 왼쪽 노드 로 위임
                leftNode.addNode(value)
            }else { // 왼쪽 자식이 미존재 - 새로운 노드를 만들어서 노드 추가
                let newNode: Node = Node(value: value)
                newNode.parent = self
                leftNode = newNode
            }
        }else { // 오른쪽 자식에 삽입
            if let rightNode = self.rightNode {
                rightNode.addNode(value)
            }else { //새로운 노드 추가
                let newNode: Node = Node(value: value)
                newNode.parent = self
                rightNode = newNode
            }
        }
    }
    func search(_ value: T) -> Node? { // 노드 검색
        if value == self.value { return self }

        if value < self.value {
            return self.leftNode?.search(value)
        }else {
            return self.rightNode?.search(value)
        }
    }
    func deleteNode(){
        if let _ = self.leftNode, let _ = self.rightNode { // 자식이 두개인 경우
            self.swapNode()
        }else if let left = self.leftNode { // 자식이 왼쪽만 있는 경우
            self.changeParent(left)
        }else if let right = self.rightNode { // 자식이 오른쪽만 있는 경우
            self.changeParent(right)
        }else { // 자식이 없는 경우
            self.changeParent(nil) // 부모의 자식이 nil이면 되는데 왼쪽인지 오른쪽인지 모르니 위임
        }
        //참조값 삭제
        self.parent = nil
        self.leftNode = nil
        self.rightNode = nil
    }
    func changeParent(_ node: Node?) { // 노드의 부모를 변경
        guard let parent = self.parent else { // root 노드인 경우
            node?.parent = nil
            return
        }
        // 객체간의 비교이므로 ===
        if parent.leftNode === self { parent.leftNode = node }
        else { parent.rightNode = node }
        node?.parent = parent // 부모를 변경
    }
    func swapNode() { // 본인과 왼쪽 서브 트리의 가장 오른쪽 노드와 변경, 자식이 둘인 경우에 필요
        // 교환할 노드와 자식들을 연결
        guard let leftNode = self.leftNode, let rightNode = self.rightNode else { return }
        let leftMax: Node = leftNode.searchMax() // 왼쪽 서브 트리중 가장 큰노드
        leftMax.deleteNode() // delete해도 leftMax가 반환되는것은 아님 자식이 있으면 자식과 부모를 연결하고 자식이 없으면 부모와의 연결을 끊을뿐
        leftMax.rightNode = rightNode // 오른쪽 자식을 연결
        rightNode.parent = leftMax //부모 연결

        if leftNode === leftMax { // 왼쪽 노드가 왼쪽 자식 뿐일때
            leftMax.leftNode = nil // 변경후의 왼쪽 노드는 없음
        } else { // 변경후에도 노드가 있다면
            leftMax.leftNode = leftNode //왼쪽 자식을 연결
            leftNode.parent = leftMax // 부모 연결
        }
        // 여기까지 교환할 노드와 자식들을 연결
        self.changeParent(leftMax) // 마지막으로 자신의 부모랑 변경한 노드랑 연결
    }
    func searchMax() -> Node { // 노드보다 가장 큰 값을 서치
        if let rightNode = self.rightNode { // 오른쪽노드가 있음
            return rightNode.searchMax() // 오른쪽 노드의 가장 큰 값을 서치
        }
        return self // 오른쪽 노드가 없으면 내가 가장 큰값
    }
}

트리 순회 방식

1. 중위 순회 (inorder)
   • 좌측 - 본인 - 우측 노드 순으로 출력
   • 오름차순으로 정렬
2. 전위 순회 (preorder)
   • 본인 - 좌측 - 우측 노드 순으로 출력
3. 후위 순회 (postorder)
   • 좌측 - 우측 - 본인 노드 순으로 출력

• 트리 기본 코드에서 확장 (접근 방식: Node.함수명(루트노드))

    // 순회관련 확장
    extension Node {
        static func inOrderTraversal(_ node: Node?) { // 중위순회
            guard let node = node else { return }
            inOrderTraversal(node.leftNode)
            print(node.value)
            inOrderTraversal(node.rightNode)
        }
        static func preOrderTraversal(_ node: Node?) { // 전위순회
            guard let node = node else { return }
            print(node.value)
            preOrderTraversal(node.leftNode)
            preOrderTraversal(node.rightNode)
        }
        static func postOrderTraversal(_ node: Node?) { // 후위순회
            guard let node = node else { return }
            postOrderTraversal(node.leftNode)
            postOrderTraversal(node.rightNode)
            print(node.value)
        }
    }