[CS] 트리

눈치없어·2025년 3월 11일

자료 구현이 단순하고 다양한 변형이 가능한 자료구조로, 주로 계층적인 구조를 표현하기 위해 사용

📌 트리 구조

트리는 노드와 간선(링크)으로 이루어져 있음
- 노드: 트리 자료구조에서 데이터를 저장하는 구성 요소
- 간선: 트리 자료구조에서 노드를 연결하는 구성 요소
데이터가 저장된 노드와, 노드와 노드를 연결하는 간선으로 이루어진 트리는 상하 관계를 형성

📌 노드 종류

부모 노드(Parent Node): 상위에 위치한 노드
자식 노드(Child Node): 하위에 위치한 노드

형제 노드(Sibling Node): 같은 부모 노드를 공유하는 노드
조상 노드(Ancestor Node): 부모 노드와 그 부모 노드들
자손 노드(Descendant Node): 자식 노드와 그 자식 노드들

루트 노드(Root Node): 부모 노드가 없는 최상단 노드. 트리에서 유일하게 부모 노드가 없는 노드
리프 노드(Leaf Node): 더 이상 자식 노드가 없는 최하단 노드

📌 트리의 특징

부모 노드는 하나만 있을 수 있고,(최상단 노드 제외) 하나 이상의 자식 노드를 가질 수 있음
부모와 자식 노드는 상대적인 개념 (노드 B는 노드 A의 자식 노드이자 노드 D의 부모 노드가 될 수 있음)
트리는 계층적 구조이기 때문에 최상단 노드와 최하단 노드가 존재

📌 트리 이해 용어

차수 (Degree):
각 노드가 가지는 자식 노드의 수를 의미
예를 들어, 노드 b는 2개의 자식 노드를 가지므로 차수가 2
마찬가지로, 3개의 자식 노드를 가진 노드 c의 차수는 3이고, 리프 노드는 자식 노드가 없기 때문에 차수가 0
레벨 (Level):
루트 노드에서 시작해 특정 노드에 이르기까지 거치는 간선의 수를 의미
특정 노드가 트리에서 얼마나 깊은 곳에 있는지를 나타내는 개념
예를 들어, 노드 b는 레벨 1, 노드 f는 레벨 2임 트리에서 가장 높은 레벨을 가진 노드가 트리의 높이
서브트리(Subtree):
트리에 포함되어 있는 부분 트리
서브트리는 트리이기 때문에 루트 노드를 가질 수 있음
예를 들어, 서브트리 1의 루트 노드는 노드 b이고, 서브트리 2의 루트 노드는 노드 d
이렇게 트리 내에 또 다른 트리가 포함되는 구조를 통해, 트리는 복잡한 계층적 관계를 보다 유연하게 표현할 수 있음

📌 트리 구현/저장 방식

연결 리스트처럼 하나의 노드를 데이터를 저장할 공간과 자식 노드의 위치 정보(메모리 상의 주소)를 저장할 공간(들)의 모음으로 간주함으로써 구현할 수 있음

트리의 순회

트리의 모든 노드를 한 번씩 방문하는 작업을 의미

전위 순회 (Pre-order Traversal)

루트 노드부터 시작해 왼쪽 서브트리를 전위 순회하고, 이후 오른쪽 서브트리를 전위 순회하는 방식

순서: 루트 노드 → 왼쪽 서브트리 전위 순회 → 오른쪽 서브트리 전위 순회

예시:

루트 노드 a 방문, 왼쪽 서브트리의 루트 노드 b를 방문. 그 후, 노드 b의 왼쪽 서브트리의 루트 노드 d를 방문, 다시 왼쪽 자식 노드 h를 방문한 뒤 오른쪽 자식 노드 i 방문
b의 오른쪽 서브트리로 넘어가서, 루트 노드 e 방문, e의 왼쪽 자식 노드 j와 오른쪽 자식 노드 k를 차례로 방문
루트 노드 a의 왼쪽 서브트리를 모두 방문한 후, 오른쪽 서브트리로 넘어가서, 루트 노드 c를 방문, 왼쪽 서브트리의 루트 노드 f와 그 자식 노드들을 순회. 마지막으로 c의 오른쪽 서브트리의 루트 노드 g를 방문

결과: a → b → d → h → i → e → j → k → c → f → l → g

전위 순회 의사 코드

전위 순회(노드):
  if 노드가 존재하지 않으면:
    return
  노드 값 출력
  전위 순회(노드의 왼쪽 자식)
  전위 순회(노드의 오른쪽 자식)

전위 순회 자바 코드

class Node {
    int data;
    Node left, right;
    
    Node(int item) {
        data = item;
        left = right = null;
    }
}

public class Tree {
    void preOrder(Node node) {
        if (node == null) return;
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        Tree tree = new Tree();
        tree.preOrder(root);
    }
}

중위 순회 (In-order Traversal)

루트 노드 기준으로 왼쪽 서브트리를 먼저 중위 순회하고, 그 다음 루트 노드를 방문한 후, 마지막으로 오른쪽 서브트리를 중위 순회하는 방법

순서: 왼쪽 서브트리 중위 순회 → 루트 노드 → 오른쪽 서브트리 중위 순회

예시:

왼쪽 서브트리의 루트 노드 b부터 시작, 왼쪽 서브트리의 루트 노드 d를 기준으로 중위 순회를 진행. 노드 h를 방문, d를 방문, 이어서 d의 오른쪽 자식 노드 i를 방문
이제 b를 방문, b의 오른쪽 서브트리로 넘어가 e의 왼쪽 서브트리 j, 그 후 e를 방문, 마지막으로 e의 오른쪽 자식 노드 k 방문
루트 노드 a를 방문한 후, 오른쪽 서브트리로 넘어가 f의 왼쪽 자식 노드 l을 방문하고, f를 방문, 마지막으로 오른쪽 서브트리 c를 순회
c의 왼쪽 자식 노드 g를 방문, 마지막으로 c를 방문

결과: h → d → i → b → j → e → k → a → l → f → c → g

중위 순회 의사 코드

중위 순회(노드):
  if 노드가 존재하지 않으면:
    return
  중위 순회(노드의 왼쪽 자식)
  노드 값 출력
  중위 순회(노드의 오른쪽 자식)

중위 순회 자바 코드

class Node {
    int data;
    Node left, right;
    
    Node(int item) {
        data = item;
        left = right = null;
    }
}

public class Tree {
    void inOrder(Node node) {
        if (node == null) return;
        inOrder(node.left);  // 왼쪽 자식
        System.out.print(node.data + " ");  // 노드 값 출력
        inOrder(node.right); // 오른쪽 자식
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        Tree tree = new Tree();
        tree.inOrder(root);
    }
}

후위 순회 (Post-order Traversal)

후위 순회는 루트 노드 기준으로 왼쪽 서브트리를 후위 순회하고, 오른쪽 서브트리를 후위 순회한 뒤 마지막에 루트 노드를 방문하는 순회 방법

순서: 왼쪽 서브트리 후위 순회 → 오른쪽 서브트리 후위 순회 → 루트 노드 방문

예시:

왼쪽 서브트리의 루트 노드 b부터 시작, 왼쪽 서브트리의 루트 노드 d를 기준으로 후위 순회를 진행. 먼저 h를 방문, i를 방문한 뒤 d를 방문
b의 오른쪽 서브트리로 넘어가서 e의 왼쪽 자식 노드 j를 방문, k 방문 후 e 방문
b 방문 후, 루트 노드 a의 오른쪽 서브트리로 넘어가 f의 왼쪽 자식 노드 l 방문, f 방문 후, g 방문, 마지막으로 c 방문
마지막으로 루트 노드 a를 방문

결과: h → i → d → j → k → e → b → l → f → g → c → a

후위 순회 의사 코드

후위 순회(노드):
  if 노드가 존재하지 않으면:
    return
  후위 순회(노드의 왼쪽 자식)
  후위 순회(노드의 오른쪽 자식)
  노드 값 출력

후위 순회 자바 코드

class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

public class Tree {
    void postOrder(Node node) {
        if (node == null) return;
        postOrder(node.left);  // 왼쪽 자식
        postOrder(node.right); // 오른쪽 자식
        System.out.print(node.data + " ");  // 노드 값 출력
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);

        Tree tree = new Tree();
        tree.postOrder(root);
    }
}

전위 / 중위 / 후위 순회는 각각 트리의 모든 노드를 한 번씩 방문하기 위한 순회 방법
노드를 방문하는 방법과 순서가 다름

레벨 순서 순회: 가장 낮은 레벨부터 차례로 노드를 순회하는 방법
결과: a → b → c → d → e → f → g → h → i → j → k → l

트리 종류

이진트리 (Binary Tree)

자식 노드의 개수가 최대 2개인 트리
가장 일반적이고 널리 사용되는 트리 형태로, 흔히 "트리"라고 할 때 떠오르는 구조
모든 자식 노드가 2개 이하이기 때문에 각 노드는 왼쪽과 오른쪽 자식 노드를 가질 수 있음

편향된 이진트리 (Skewed Binary Tree)

이진트리에서 모든 자식 노드가 한쪽으로 치우친 경우
자식 노드가 항상 한쪽 방향으로만 존재하는 형태

세부적인 이진트리 종류

📌 정이진트리 (Full Binary Tree)

자식 노드의 개수가 0개 또는 2개인 이진트리
즉, 각 노드가 자식 노드를 0개 또는 2개만 가지는 구조

📌 포화이진트리 (Perfect Binary Tree)

모든 리프 노드가 동일한 레벨에 있고, 모든 노드가 자식 노드를 2개씩 가지는 이진트리
예를 들어, 모든 리프 노드의 레벨이 동일하고, 그 위의 노드들이 자식 노드를 정확히 2개씩 가지는 경우

📌 완전이진트리 (Complete Binary Tree)

마지막 레벨을 제외한 모든 레벨이 꽉 차 있어야 하고, 마지막 레벨의 노드들이 왼쪽부터 채워진 이진트리
왼쪽부터 오른쪽으로 차례대로 노드가 채워지며, 마지막 레벨만 노드가 부족할 수 있음
예를 들어, 마지막 레벨의 노드들이 왼쪽부터 채워져 있지 않으면, 그 트리는 완전이진트리가 아님

탐색에 활용되는 트리: 이진탐색트리와 힙

탐색에 특화된 트리 구조로 이진탐색트리와 힙이 있음
이 두 트리는 데이터를 효율적으로 찾거나 최대값/최솟값을 빠르게 찾을 수 있도록 설계됨

📌 이진탐색트리 (Binary Search Tree, BST)

특정 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값들을 가진 노드들이 있고, 오른쪽 서브트리에는 해당 노드보다 큰 값들을 가진 노드들이 있는 구조
즉, 트리에서 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값을 가지는 규칙을 따름

탐색 시간: O(log n)의 시간 복잡도로 원하는 값을 탐색할 수 있음. 트리가 균형을 이룰 경우, 매우 빠른 탐색이 가능

예시:
트리에서 15를 탐색하려고 할 때, 8보다 작은 값들만 있는 왼쪽 서브트리를 살펴볼 필요가 없음
하지만 편향된 트리의 경우, O(n) 의 시간 복잡도를 가지게 되어 탐색 속도가 느려질 수 있음(이진탐색트리의 최악의 경우)

📌 힙 (Heap)

최댓값 또는 최솟값을 빠르게 찾기 위해 사용

최대 힙:
- 부모 노드의 값이 자식 노드의 값보다 큰 값으로 이루어진 이진 트리
- 가장 큰 값이 루트 노드에 위치
최소 힙:
- 부모 노드의 값이 자식 노드의 값보다 작은 값으로 이루어진 이진 트리
- 가장 작은 값이 루트 노드에 위치

노드 간 크기(크다/작다)의 비교는 숫자만 가능한게 아니라 문자 간의 비교도 가능
원하는 우선순위를 직접 지정할 수도 있음

힙의 주요 용도는 우선순위 큐에 사용되는 것
예를 들어, 최대힙을 사용하면, 큐에서 데이터를 우선순위가 높은 값부터 꺼낼 수 있음
힙을 구현하면 우선순위 큐에서 데이터가 어떤 순서로 저장되었든, 우선순위가 높은 값부터 데이터를 꺼낼 수 있음

균형을 맞추는 트리: RB 트리

이진탐색트리는 삽입과 삭제 연산이 반복되면서 편향된 트리로 변할 수 있는 문제 있음
이러한 편향된 트리는 탐색 속도가 O(n)으로, 사실상 연결리스트처럼 동작하게 되어 트리 자료구조의 장점을 잃게 됨

이를 해결하기 위해 자기 균형 이진 탐색 트리가 필요 RB 트리(Red-Black Tree)는 그 중 하나로, 트리의 균형을 맞추기 위한 규칙을 따름

📌 RB 트리 주요 특징

자기 균형: 트리가 삽입과 삭제를 거치면서도 균형을 유지하도록 도움
색상 규칙: 각 노드에 빨간색(red) 또는 검은색(black)을 칠하고, 이 색상에 기반하여 트리의 균형을 맞춤

📌 RB 트리의 활용

리눅스 커널: RB 트리는 리눅스 커널의 CPU 스케줄러인 CFS 스케줄러에도 사용됨
C++ STL: C++의 std::map 또는 std::set 같은 컨테이너도 내부적으로 RB 트리를 사용하여 데이터를 저장하고 있음

📌 RB 트리 규칙

루트 노드는 블랙 노드이다.
리프 노드는 블랙 노드이다.
레드 노드의 자식 노드는 블랙 노드이다.
루트 노드에서 임의의 리프 노드에 이르는 경로드의 블랙 노드 수는 같다.

📌 RB 트리 삽입 및 회전

삽입: 새로운 노드를 삽입할 때, 기본적으로 레드 노드로 삽입. 이후 RB 트리 규칙을 만족시키기 위해 색상을 변경하거나 회전을 진행
회전: 트리의 균형을 맞추기 위해 왼쪽 회전과 오른쪽 회전을 사용. 예를 들어, 노드를 기준으로 왼쪽으로 회전하면, 자식 노드가 부모 노드로 올라가고 부모 노드는 자식의 왼쪽 자식이 됨

회전 예시
예를 들어, 30을 삽입한 후 RB 트리 규칙을 만족시키기 위해 회전을 진행할 수 있음. 삽입 후, 트리는 규칙을 만족하지 않으므로 회전과 색상 재지정이 필요. 이 과정을 통해 트리가 균형을 이룸

이 경우 "노드가 레드 노드일 경우, 자식 노드는 블랙 노드"라는 3번 조건에 부합하지 않음
따라서 조건에 맞게 트리를 왼쪽으로 회전하고, 색상을 재지정.

> 12를 15의 자식 노드로 만들고, 12를 레드 노드로, 15를 블랙 노드로 변환

삭제 연산 예시
5를 삭제한다고 가정

> 언제 색을 재지정하고 트리를 회전할지를 결정하는 보다 상세한 알고리즘도 있음

여기서는 다루지 않겠음

RB 트리는 이진탐색트리의 효율성을 유지하면서, 항상 균형 잡힌 구조를 제공하는 중요한 자료구조
삽입과 삭제가 일어나도 트리의 균형이 자동으로 유지되기 때문에, 탐색 시간이 항상 O(log n)으로 일정하게 유지됨

대용량 입출력을 위한 트리: B 트리

B 트리는 자기 균형 이진 탐색 트리와 유사하지만, 이진 탐색 트리가 아닌 다진 탐색 트리
즉, 하나의 노드가 여러 개의 자식 노드를 가질 수 있는 구조로, 대량의 데이터를 효율적으로 처리하는 데 최적화된 트리

📌 B 트리의 특징

다진 탐색 트리: 하나의 노드가 여러 개의 자식 노드를 가질 수 있음
노드의 자식 노드 수: 각 노드는 자식 노드의 최소 개수와 최대 개수가 정해져 있음
M차 B 트리: 한 노드가 가질 수 있는 최대 자식 노드의 개수가 M개인 B 트리
- M차 B 트리가(루트 노드와 리프 노드를 제외하고) 가질 수 있는 최소 자식 노드의 개수는 [M/2]개
- 예를 들어, 5차 B 트리의 한 노드는 최대 5개의 자식 노드를 가질 수 있고, (루트 노드와 리프 노드를 제외한)노드들은 최소 3개의 자식 노드를 가질 수 있음

> '[]' 기호는 올림을 의미

키 값: 각 노드는 하나 이상의 키 값을 가짐. 키들은 오름차순으로 정렬되어 있음

위 트리의 루트 노드에는 2개의 키가 존재하며, key1은 key2보다 작은 값을 갖음
각각의 노드는 B 트리로 다룰 실질적인 데이터(의 위치)도 포함할 수 있음
키 값 자체를 B 트리로 다룰 데이터로 삼을 수도 있지만, 일반적으로 키는 데이터를 찾기 위한 인덱스로 활용되므로 '키를 알면 키에 대응되는 데이터도 알 수 있다'고 이해하면됨

이진 탐색 트리와 유사하게 B 트리에서는 각 키 사이 사이에 자식 노드(혹은 서브트리)의 위치를 저장하고 있으며, 키가 자식 노드(혹은 서브트리)가 가질 수 있는 값의 범위를 나타내는 역할을 함
키 사이 사이에 자식 노드가 존재하기 때문에 키가 N개인 노드가 가질 수 있는 자식 노드의 수는 반드시 (N+1)개가 됨
그림의 노드 A의 자식 노드는 노드 B, C, D 3개가 되고, 노드 A의 자식 노드인 B, C, D가 갖는 범위는

노드 B < key1
key1 < 노드 C < key2
노드 D > key2
이렇게 갖음

즉, 각 자식 노드의 값이 왼쪽 자식 노드(서브트리)부터 오른쪽 자식 노드(서브트리)까지 정렬되어 있는 셈이고, B 트리는 모든 리프 노드의 깊이가 같다는 특징도 있음
따라서 특정 노드에만 자식 노드가 존재하는 편향된 형태는 발생하지 않음

📌 B 트리의 장점

B 트리는 파일 시스템이나 데이터베이스와 같이 대량의 데이터를 처리할 때 매우 유용
그 이유는 입출력 연산 횟수를 최소화할 수 있기 때문. 메모리 접근에 비해 보조기억장치에서의 접근 속도는 느리기 때문에, B 트리는 노드가 여러 데이터를 저장할 수 있어 보조기억장치에 대한 입출력 연산을 줄이고 성능을 향상시킴

효율적인 데이터 접근: B 트리는 한 노드에 블록 단위로 여러 데이터를 저장할 수 있어, 보조기억장치와의 연동에서 효율성을 극대화

📌 B 트리 / B+ 트리 차이점

B 트리는 주로 파일 시스템이나 데이터베이스에서 사용. 그러나 B+ 트리라는 변형이 더 많이 사용됨
B+ 트리는 B 트리의 개선된 형태

주요 차이점

B+ 트리에서는 실질적인 데이터가 최하위 리프 노드에만 저장됨
실질적 데이터를 저장하는 최하위 리프 노드는 연결 리스트 형태로 연결되어 있어, 범위 연산을 용이하게 함

이 밖에도 문자열을 효율적으로 탐색하고 저장하기 위한 트라이, 빠른 구간 연산을 위한 세그먼트 트리, 펜윅 트리 등 트리의 종류는 매우 다양함

참고: 북스터디 - 이것이 취업을 위한 컴퓨터 과학이다 (Chapter 4-5)

눈치없어

dock 사이즈 다르잖아

이전 포스트

[CS] 해시 테이블

다음 포스트