자료구조 - 트리

C언어로 쉽게 풀어쓴 자료구조를 읽으며 정리

트리

트리는 데이터의 계층적 관계를 표현하는 비선형적 자료구조이다.
노드와 간선으로 이루어져 있으며 사이클을 허용하지 않는 그래프의 한 종류이다.

트리 - 구성요소

노드 : 트리를 구성하는 각 요소
간선 : 트리를 구성하기 위해 노드와 노드를 연결하는 선
루트 노드 : 트리 구조에서 최상위 노드
단말 노드, 리프 노드 (Terminal Node, Leaf Node) : 하위에 다른 노드가 연결되어 있지 않은 노드
내부 노드, 비단말 노드(Internal Node) : 단말 노드를 제외한 모든 노드

이진 트리

루트노드를 중심으로 최대 두 개의 서브 트리로 나눠진다.

나눠진 두 서브 트리 모두 이진 트리이다.
서브 트리는 공집합일 수도 있다. (공집합도 이진 트리이다.)

트리의 각 층 별로 숫자를 매겨 이를 레벨(level)이라고 한다.

레벨은 0(또는 1)부터 시작하게 되고 리프 노드의 레벨을 가리켜 높이라고 얘기한다.
루트 노드의 레벨은 0이다.

트리의 최고 레벨을 가리켜 해당 트리의 높이(height) 라고 한다.

높이가 h인 이진트리의 경우 노드 개수는 최소 h개, 최대 2^h-1 개이다.
따라서 n개의 노드를 가지는 이진트리의 최대 높이는 최대 n, 최소 floor(log2(n+1)) 이다.

이진 트리 - 분류

포화 이진트리 (Perfect Binary Tree)

모든 레벨이 꽉 찬 이진 트리
높이가 h이면 항상 2^h-1 의 노드 개수

완전 이진트리 (Complete Binary Tree)

위에서 아래로, 왼쪽에서 오른쪽 순서대로 차곡차곡 채워진 이진트리
높이가 h이면 노드의 개수는 2^(h-1) ~ 2^h -1

정 이진트리 (Full Binary Tree)

모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진트리

이진 트리 - 배열로 표현

힙을 구현할 때 완전 이진 트리 구조를 사용하게 되는데 일반적으로 배열을 이용하여 구현한다.

새로운 노드를 힙의 마지막 위치에 추가해야 하는데 이 때 배열을 사용하는 것이 더 효율적

구현 아이디어

모든 이진트리를 포화 이진트리라고 가정하고 배열의 크기를 정한다.

루트 노드의 위치를 배열의 1번 인덱스로 설정
- 루트가 1번에서 시작해야 i번째 노드에 대하여 부모 노드는 i/2, 왼쪽 노드는 2i, 오른쪽 노드는 2i+1의 인덱스를 가짐
왼쪽 서브 트리의 루트 노드의 위치를 2i
오른쪽 서브트리의 루트 노드를 2i + 1

이진 트리 - 연결 리스트로 표현

참조 값을 이용하여 부모 노드가 자식 노드를 가리키게 하는 방법이다.

노드는 클래스로 표현하고 링크는 참조 값으로 표현
Double Linked List로 완전 이진 트리를 구현할 수도 있음

class Node<T> {
    var value: T
    var left: Node?
    var right: Node?

    init(value: T) {
        self.value = value
        self.left = nil
        self.right = nil
    }
}

class BinaryTree<T> {
    
    private(set) var root: Node<T>?
    
    init() { }
    
    ...
}

이진트리 - 순회

전위 순회

자신, 왼쪽, 오른쪽 순서로 방문
계층적인 구조를 표현하고 싶을 때 활용하기 좋음 ex. 구조화된 문서 출력

중위 순회

왼쪽, 자신 오른쪽 순으로 방문
수식 트리를 중위 순위로 표현 > 인간에게 익숙한 표현 식
노드의 크기 순서대로 방문할 필요가 있을 때

후위 순회

왼쪽 오른쪽 자신 순으로 방문
자식 노드를 먼저 방문할 필요가 있는 경우
하위 폴더 용량의 계산
수식 트리의 계산 : 비단말 노드를 방문할 때 양쪽 서브트리의 값을 노드에 저장된 연산자를 이용하여 계산

레벨 순회

각 노드들을 낮은 레벨 부터 높은 레벨까지 순회
다른 트리 순회 방법들이 스택을 사용했던 것에 비해 레벨 순회는 큐를 사용하는 순회 방법

class BinaryTree<T> {
    
    private(set) var root: Node<T>?
    
    init() { }
    
    func preorder(_ node: Node<T>?) {
        guard let value = node?.value else { return }
        
        print(value)
        self.preorder(node?.left)
        self.preorder(node?.right)
    }
    
    func inorder(_ node: Node<T>?) {
        guard let value = node?.value else { return }
        
        self.inorder(node?.left)
        print(value)
        self.inorder(node?.right)
    }
    
    func postorder(_ node: Node<T>?) {
        guard let value = node?.value else { return }
        
        self.postorder(node?.left)
        self.postorder(node?.right)
        print(value)
    }
    
    func levelOrder(_ node: Node<T>?) {
        guard let node else { return }
        
        // https://liam777.tistory.com/25 에서 구현한 Queue 사용
        var queue: LinearQueue<Node<T>> = .init()
        queue.enqueue(node)
        
        while !queue.isEmpty {
            guard let node = queue.dequeue() else { continue }
            print(node.value)
            
            if let left = node.left {
                queue.enqueue(left)
            }
            
            if let right = node.right {
                queue.enqueue(right)
            }
        }
    }
    
    ...
}

BST(Binary Search Tree)

이진 탐색 트리는 효율적인 탐색을 위해 고안한 자료구조이다.

데이터 저장 규칙

이진 탐색 트리의 노드에 저장된 키는 유일함
부모의 키가 왼쪽 자식 노드의 키 보다 항상 큼
부모의 키가 오른쪽 자식 노드의 키보다 항상 작음
왼쪽과 오른쪽 서브 트리도 이진 탐색 트리임

시간 복잡도

조회에 대한 O(logn)의 평균 시간 복잡도
엄밀히 얘기하자면 O(h)가 맞음 (트리의 높이 h)
이진 탐색 트리가 한 쪽으로 편향된다면 (worst case) 시간 복잡도는 O(n)
이러한 문제점을 해결하기 위해 Rebalancing 기법들이 등장
트리의 구조를 재조정 (AVL 트리, Red-Black Tree, ...)

class Node<T: Comparable> {
    var value: T
    var left: Node?
    var right: Node?

    init(value: T) {
        self.value = value
        self.left = nil
        self.right = nil
    }
}

class BinarySearchTree<T: Comparable> {
    
    private(set) var root: Node<T>?
    
    init() { }
    
    func search(value: T, _ node: Node<T>?) -> Node<T>? {
        guard let node else { return nil }
        
        if value == node.value {
            return node
        } else if value < node.value {
            return self.search(value: value, node.left)
        } else {
            return self.search(value: value, node.right)
        }
    }
    ...
}

삽입 연산

해당 데이터를 트리에서 탐색한다
탐색이 실패한 위치가 바로 새로운 노드 삽입 위치가 된다

class BinarySearchTree<T: Comparable> {

    ...
    
    func insert(value: T) {
        self.root = self._insert(value: value, self.root)
    }
    
    private func _insert(value: T, _ node: Node<T>?) -> Node<T> {
        guard let node else {
            return Node(value: value)
        }
        
        if value == node.value {
            // do nothing
        } else if value < node.value {
            node.left = self._insert(value: value, node.left)
        } else {
            node.right = self._insert(value: value, node.right)
        }
        
        return node
    }
    
    ...
}

삭제 연산

세 가지 케이스를 고려해야 함

1. 삭제하려는 노드가 단말 노드인 경우 (서브 트리가 0개)

단말 노드의 부모 노드를 찾아서 연결을 끊는다.

2. 삭제하려는 노드가 하나의 서브 트리만 갖고 있는 경우

해당 노드를 삭제하고 서브 트리는 모두 부모 노드에 붙여준다.

3. 삭제하려는 노드가 두 개의 서브 트리를 갖고 있는 경우

왼쪽 서브트리의 가장 큰 값과 오른쪽 서브 트리에서 가장 작은 값 중 하나를 삭제할 노드의 위치로 가져 온다.

class BinarySearchTree<T: Comparable> {
    
    ...
    
    func delete(value: T) {
        self.root = self._delete(value: value, self.root)
    }
    
    private func _delete(value: T, _ node: Node<T>?) -> Node<T>? {
        guard let node else { return nil }
        
        if value == node.value {
            guard let right = node.right, let _ = node.left else {
                // 한쪽 자식만 있는 경우
                if let left = node.left, node.right == nil {
                    return left
                }
                if let right = node.right, node.left == nil {
                    return right
                }
                
                // 노드에 자식이 없는 경우
                return nil
            }
            
            // 두 자식이 있는 경우
            let minAtRight = self.findMin(right)
            node.value = minAtRight.value
            node.right = self._delete(value: minAtRight.value, node.right)
        }
        
        if value < node.value {
            node.left = self._delete(value: value, node.left)
        }
        
        if value > node.value {
            node.right = self._delete(value: value, node.right)
        }
        
        return node
    }
    
    private func findMin(_ node: Node<T>) -> Node<T> {
        var currentNode = node
        while let left = currentNode.left {
            currentNode = left
        }
        return currentNode
    }
    ...
}

BST 전체 코드

class Node<T: Comparable> {
    var value: T
    var left: Node?
    var right: Node?

    init(value: T) {
        self.value = value
        self.left = nil
        self.right = nil
    }
}

class BinarySearchTree<T: Comparable> {
    
    private(set) var root: Node<T>?
    
    init() { }
    
    func search(value: T, _ node: Node<T>?) -> Node<T>? {
        guard let node else { return nil }
        
        if value == node.value {
            return node
        } else if value < node.value {
            return self.search(value: value, node.left)
        } else {
            return self.search(value: value, node.right)
        }
    }
    
    func insert(value: T) {
        self.root = self._insert(value: value, self.root)
    }
    
    private func _insert(value: T, _ node: Node<T>?) -> Node<T> {
        guard let node else {
            return Node(value: value)
        }
        
        if value == node.value {
            // do nothing
        } else if value < node.value {
            node.left = self._insert(value: value, node.left)
        } else {
            node.right = self._insert(value: value, node.right)
        }
        
        return node
    }
    
    func delete(value: T) {
        self.root = self._delete(value: value, self.root)
    }
    
    private func _delete(value: T, _ node: Node<T>?) -> Node<T>? {
        guard let node else { return nil }
        
        if value == node.value {
            guard let right = node.right, let _ = node.left else {
                // 한쪽 자식만 있는 경우
                if let left = node.left, node.right == nil {
                    return left
                }
                if let right = node.right, node.left == nil {
                    return right
                }
                
                // 노드에 자식이 없는 경우
                return nil
            }
            
            // 두 자식이 있는 경우
            let minAtRight = self.findMin(right)
            node.value = minAtRight.value
            node.right = self._delete(value: minAtRight.value, node.right)
        }
        
        if value < node.value {
            node.left = self._delete(value: value, node.left)
        }
        
        if value > node.value {
            node.right = self._delete(value: value, node.right)
        }
        
        return node
    }
    
    private func findMin(_ node: Node<T>) -> Node<T> {
        var currentNode = node
        while let left = currentNode.left {
            currentNode = left
        }
        return currentNode
    }
    
    func preorder(_ node: Node<T>?) {
        guard let value = node?.value else { return }
        
        print(value)
        self.preorder(node?.left)
        self.preorder(node?.right)
    }
    
    func inorder(_ node: Node<T>?) {
        guard let value = node?.value else { return }
        
        self.inorder(node?.left)
        print(value)
        self.inorder(node?.right)
    }
    
    func postorder(_ node: Node<T>?) {
        guard let value = node?.value else { return }
        
        self.postorder(node?.left)
        self.postorder(node?.right)
        print(value)
    }
    
    func levelOrder(_ node: Node<T>?) {
        guard let node else { return }
        
        // https://liam777.tistory.com/25 에서 구현한 Queue 사용
        var queue: LinearQueue<Node<T>> = .init()
        queue.enqueue(node)
        
        while !queue.isEmpty {
            guard let node = queue.dequeue() else { continue }
            print(node.value)
            
            if let left = node.left {
                queue.enqueue(left)
            }
            
            if let right = node.right {
                queue.enqueue(right)
            }
        }
    }
}

struct LinearQueue<Element> {
    private var _queue: [Element] = []

    var isEmpty: Bool { return self._queue.isEmpty }
    var count: Int { return self._queue.count }

    mutating func enqueue(_ element: Element) {
        self._queue.append(element)
    }

    mutating func dequeue() -> Element? {
        return self.isEmpty ? nil : self._queue.removeFirst()
    }
}

'CS > 자료구조' 카테고리의 다른 글

자료구조 - Heap (2) 정렬 (2)	2024.09.16
자료구조 - Heap (1) 기본 (3)	2024.09.02
자료구조 - 스택, 큐, 덱 (0)	2024.08.17
자료 구조 - 배열, 연결 리스트 (1)	2024.08.14
자료 구조 - 순환 (Recursion) (1)	2024.08.12

리암

자료구조 - 트리

트리

트리 - 구성요소

이진 트리

이진 트리 - 분류

이진 트리 - 배열로 표현

이진 트리 - 연결 리스트로 표현

이진트리 - 순회

BST(Binary Search Tree)

'CS > 자료구조' 카테고리의 다른 글

티스토리툴바

자료구조 - 트리

트리

트리 - 구성요소

이진 트리

이진 트리 - 분류

이진 트리 - 배열로 표현

이진 트리 - 연결 리스트로 표현

이진트리 - 순회

BST(Binary Search Tree)

'CS > 자료구조' 카테고리의 다른 글

'CS/자료구조' Related Articles

티스토리툴바