[Java / 자료구조] 트리(Tree)

트리 (Tree)

출처 https://www.geeksforgeeks.org/applications-of-tree-data-structure/

• 비선형 자료구조
  • 계층 관계, 상하 관계 표현, 부모자식 관계
• 원소들 간에 1:N 관계를 가지는 자료구조
• 원소들 간에 계층 관계를 가지는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조

 

정의

: 한 개 이상의 노드로 이루어진 유한 집합이다.

• 사이클이 없는 연결 그래프
• 단순 경로가 하나인 트리

 

트리의 조건 3가지

1. 연결 그래프여야 한다. == 경로가 하나 이상
2. 사이클이 없어야 한다. == 경로가 둘 미만
    => 두 조건을 만족한다면, 경로는 only 하나만 존재.

3. (특징) 노드 수 == 간선 수 + 1

• 노드 : 데이터 하나하나를 이루는 단위
• 루트 (Root) : 노드 중 최상위 노드
• 나머지 노드 : n개의 분리 집합 T1, … , TN으로 분리될 수 있다.
• 부트리(subtree) : T1, … , TN은 각각 하나의 트리가 되며(=재귀적 정의), 루트의 부트리이다.

 

❓ 노드가 하나만 있어도 트리인가? Yes! 단말노트

연결 리스트는 트리인가? Yes! 트리의 일종으로 볼 수 있다!

 

용어 정리

출처 https://www.designveloper.com/blog/tree-data-structure/

• 노드(node) : 트리의 원소
• 간선(edge) : 노드를 연결하는 선, 부모 노드와 자식 노드를 연결
• 루트 노드 (root node) : 트리의 시작 노드
• 형제 노드(sibling node) : 같은 부모의 자식 노드들
• 조상 노드(parent node) : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
• 자손 노드(child node) : 서브 트리에 있는 하위 레벨의 노드들
• 리프 (leaf) : 더이상 자손노드가 없는 마지막 자손노드

 

class Node {
	String data;
	Node[] link; // link field의 타입이 Node[] 배열 형태가 된다.
}

 

• 차수 (degree)
  • 노드의 차수 : 노드에 연결된 자식 노드의 수
  • 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
• 높이(level)
  • 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
  • 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값. 최대 레벨
  • 루트가 레벨 0부터 시작일수도, 1부터 시작일수도 있음.

 

---

트리 자료 구조의 종류

1️⃣ 이진 트리 (Binary Tree)

: 모든 노드들이 최대 2개의 서브 트리를 갖는 특별한 형태의 트리

== 각 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리

출처 https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254

• 각 노드가 최대 두 개의 자식 노드를 가지는 트리
• 각 레벨 i에서의 노드는 최대 2^i 개
• 높이가 h인 이진 트리 ⇒ 노드 최소 (h+1)개 / 최대 (2^(h+1) -1)개

 

 

이진 트리의 종류

1) 포화 이진 트리(Full Binary Tree)

: 모든 노드가 0 또는 2개의 자식 노드를 가지는 트리

• 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
• 높이가 h일 때, 노드 개수가 (2^(h+1) -1)개의 노드를 갖는 이진트리

 

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

: 모든 레벨이 꽉 차 있으며, 마지막 레벨은 왼쪽부터 순서대로 채워져 있는 트리

• 높이가 h이고 노드 수가 n개 일 때, 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리

 

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

• 높이 h에 대한 최소 개수의 노드를 가지면서 한 쪽 방향의 자식 노드만을 가지는 이진 트리
  • 왼쪽 편향 이진 트리 / 오른쪽 편향 이진 트리
• 굳이 연결 리스트로 표현할 수 있는 걸 트리로 표현하면 비효율적;;

⇒ 편향 이진 트리는 불필요한 배열의 비어있는 칸이 많아진다. == 비효율적

• 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생
• 트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우, 배열의 크기 변경이 어려워 비효율적

---

이진 트리의 표현

자식 노드 번호

• left : 부모 노드 번호 * 2
• right : 부모 노드 번호 * 2 +1

완전 이진 트리 (포화 이진 트리 포함)

• 배열 삽입, 삭제가 자주 일어나지 않아 탐색에 효율적이다.

 

✅ 이진 트리 - 순회(traversal)

: 트리의 각 노드를 중복되지 않게 전부 방문하는 것.

트리는 비선형구조이기 때문에 선형구조에서와 같이 선후 연결 관계를 알 수 없다.

 

3가지 순회방법

• 전위 순회(preorder traversal) : VLR (Vertex : 정점)
  • 부모 노드 방문 후, 자식 노드를 좌, 우 순서로 방문
• 중위 순회(inorder traversal) : LVR
  • 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드
• 후위 순회(postorder traversal) : LRV
  • 자식 노드를 좌우 방문 → 부모 노드 방문

 

순회 코드로 구현하기

public class Tree_traversal {
	static char[] tree = { 0, 'A', 'B', 'C', 'D', 'E', 'F', 'G', 0, 0, 'H', 'I' };

	public static void main(String[] args) {
		System.out.println("전위 순회");
		preorder(1);
		System.out.println();
		
		System.out.println("중위 순회");
		inorder(1);
		System.out.println();
		
		System.out.println("후위 순회");
		postorder(1);
		System.out.println();
	}

	// 전위 순회 : 부모 -> 왼 -> 오 (VLR)
	// 매개변수로 트리의 루트 index 받기
	public static void preorder(int root) {
		if (root >= tree.length || tree[root] == 0) {
			return;
		}
		System.out.print(tree[root] + "->");
		preorder(root * 2);
		preorder(root * 2 + 1);

	}

	// 중위 순회 : 왼 -> 부모 -> 오 (LVR)
	// 매개변수로 트리의 루트 index 받기
	public static void inorder(int root) {
		if (root >= tree.length || tree[root] == 0) {
			return;
		}
		inorder(root * 2);
		System.out.print(tree[root] + "->");
		inorder(root * 2 + 1);
	}

	// 후위 순회 : 왼 -> 오 -> 부모 (LRV)
	// 매개변수로 트리의 루트 index 받기
	public static void postorder(int root) {
		if (root >= tree.length || tree[root] == 0) {
			return;
		}
		postorder(root * 2);
		postorder(root * 2 + 1);
		System.out.print(tree[root] + "->");
	}
}

출력

전위 순회)
A->B->D->E->H->I->C->F->G->

중위 순회)
D->B->H->E->I->A->F->C->G->

후위 순회)
D->H->I->E->B->F->G->C->A->

 

 

2️⃣ 이진 탐색 트리 (Binary Search Tree,  BST)

: 이진 트리의 일종으로, left key < parent key < right key의 조건을 만족하며, 서브트리들도 모두 이 조건을 만족하는 트리를 의미한다. 

출처 https://www.geeksforgeeks.org/difference-between-binary-search-tree-and-binary-heap/

• 노드의 왼쪽 서브 트리 : 노드의 키보다 작은 키가 있는 노드만 포함
• 노드의 오른쪽 서브 트리 : 노드의 키보다 큰 키가 있는 노드만 포함
• 왼쪽 및 오른쪽 서브 트리도 각각 이진 탐색 트리
• 중복된 키 허용하지 않는다. 

 

🔎 이진 탐색 트리 시간 복잡도

	균형 이진 탐색 트리	편향 이진 탐색 트리
탐색 시간	O(log⁡n)	O(n)
삽입 시간	O(log⁡n)	O(n)
삭제 시간	O(log⁡n)	O(n)
적합한 용도	데이터가 랜덤하게 삽입되는 경우	데이터가 정렬된 채로 삽입되는 경우

 

 

3️⃣ AVL 트리 (Adelson-Velsky and Landis Tree)

: 이진 탐색 트리(BST)의 일종으로, 삽입이나 삭제 연산 후에도 항상 트리의 균형을 유지하도록 설계된 자기 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)

출처 https://www.javatpoint.com/avl-tree

- 각 노드에 균형 인수(Balance Factor)를 저장하고, 균형이 깨질 경우 회전(Rotation)을 통해 트리를 재조정한다. 

 

AVL 트리의 특징

1. 균형 인수 (Balance Factor)

: 각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이의 차이를 의미

Balance Factor = Height(left) - Height(right)

• 균형 인수의 값은 항상 -1, 0, 1 중 하나여야 한다.
  • -1 : 오른쪽 서브트리가 더 높다.
  • 0 : 양쪽 서브트리의 높이가 같다. 
  • 1 : 왼쪽 서브트리가 더 높다.
• 삽입 또는 삭제 시, 균형 인수가 -1, 0, 1 범위를 벗어날 경우, 회전(Rotation)을 통해 균형을 복구

 

2. 회전 (Rotation)

• 단순 회전
  • LL 회전(왼쪽-왼쪽 불균형)
  • RR 회전(오른쪽-오른쪽 불균형)
• 이중 회전
  • LR 회전 (왼쪽-오른쪽 불균형)
  • RL 회전 (오른쪽-왼쪽 불균형)

참고) https://www.javatpoint.com/avl-tree

AVL Tree (Data Structures) - javatpoint

 

🔎 AVL 트리 시간 복잡도

연산	시간 복잡도
탐색	O(log⁡n)
삽입	O(log⁡n)
삭제	O(log⁡n)

• 탐색 : AVL 트리는 항상 균형을 유지하기 때문에 트리의 높이가 O(logn)으로 제한되어 탐색이 빠르다.
• 삽입 / 삭제 : 삽입과 삭제 후 균형 상태를 확인하고, 필요한 경우 회전을 통해 균형을 맞추므로 O(logn)의 시간 복잡도를 가진다. 

 

 

4️⃣ 레드-블랙 트리 (Red-Black Tree)

: 이진 탐색 트리의 일종으로, 자기 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)이다. 

• 균형 유지를 위해 모든 노드는 Red-Black Rule을 따른다. 

 

레드-블랙 트리의 특징

1. 규칙

• 규칙 1 : 모든 노드는 빨강 또는 검정이다. 
• 규칙 2 : 루트 노드는 항상 검정이다. 
• 규칙 3 : 모든 리프 노드(NIL, NULL 노드)는 검정이다.
• 규칙 4 : 빨강 노드의 자식은 반드시 검정이다. 
• 규칙 5 : 모든 노드에서 특정 노드(NIL 노드)로 가는 경로에는 같은 개수의 검정 노드가 있어야 한다. 

 

2. 균형 유지

: 삽입 및 삭제 시, 트리가 규칙을 위반할 경우 재컬러링(Recoloring) 및 회전(Rotation)을 통해 균형을 복구한다. 

3. 회전

: AVL 트리와 유사하게 LL, RR, LR, RL 회전 방식이 사용

4. 장점

• 삽입/삭제 작업 시, 균형 복구가 더 적은 연산으로 이루어져 있으므로 AVL 트리보다 수행 시간이 빠르다.
• 데이터 삽입 및 삭제가 빈번하게 발생하는 경우에 유리하다. 

 

🔎 레드-블랙 트리 시간 복잡도

연산	시간 복잡도
탐색	O(log⁡n)
삽입	O(log⁡n)
삭제	O(log⁡n)

 

AVL 트리 v.s. 레드-블랙 트리 차이점

특성	AVL 트리	레드-블랙 트리
균형 기준	높이 균형 (왼쪽-오른쪽 서브트리 높이 차 ≤ 1)	색상 규칙을 통한 균형 유지
탐색 시간	O(logn) (더 빠르다)	O(logn) (약간 느리다)
삽입 / 삭제 시간	더 많은 회전 발생	회전 횟수가 적음
높이 제한	log n에 더 가까움	최대 2*log n (더 높을 수 있음)
재조정 방법	높이 차이를 기준으로 회전만 수행	회전 + 재컬러링 수행
사용 용도	탐색 빈도가 높은 경우	삽입/삭제가 빈번히 발생하는 경우

요약)

- AVL 트리는 탐색이 더 빠르고 엄격하게 균형을 유지하며, 탐색이 빈번한 경우에 적합

- 레드-블랙 트리는 삽입 및 삭제에서 더 적은 조정 작업이 필요하며, 데이터의 삽입과 삭제가 빈번한 경우에 적합

 

 

사용 사례)

- AVL 트리: 데이터베이스 검색 시스템 등 탐색 최적화가 필요한 경우

- 레드-블랙 트리: 운영 체제 스케줄러, 파일 시스템, 로그 저장 시스템 등 삽입/삭제가 많은 경우

 

 

---

💡 Tree DP란?

: 트리라는 자료구조를 활용하여 동적 프로그래밍(Dynamic Programming) 기법을 적용하는 것

• 트리의 노드들에 대해 각 노드의 상태를 계산하거나 최적의 값을 찾는 과정에서 DP의 아이디어를 사용하는 방법
• DFS(Depth First Search)를 통해 각 노드를 탐색하면서, 하위 노드(자식 노드)의 값을 계산하여 상위 노드(부모 노드)에 필요한 정보를 전달하거나, 상위 노드에서 값을 내려주는 방식으로 문제 해결

-> 이를 통해 DFS 한 번을 돌고 나면, 부모 노드와 깊이, 크기 등에 대한 정보를 얻을 수 있다. 

import java.util.ArrayList;

public class TreeDP {
    static ArrayList<Integer>[] edge = new ArrayList[100010];
    static int[] parent = new int[100010];
    static int[] depth = new int[100010];
    static int[] size = new int[100010];
    static int[] height = new int[100010];
    static int[] sum = new int[100010];

    public static void main(String[] args) {
        int n = 5; // 노드 개수
        int[][] edges = {
            {1, 2},
            {1, 3},
            {2, 4},
            {2, 5}
        };

        // 초기화
        for (int i = 0; i < edge.length; i++) {
            edge[i] = new ArrayList<>();
        }
        
        // 간선 입력
        for (int[] e : edges) {
            int u = e[0];
            int v = e[1];
            edge[u].add(v);
            edge[v].add(u);
        }

        // 배열 초기화
        for (int i = 0; i < 100010; i++) {
            parent[i] = 0;
            depth[i] = 0;
            size[i] = 0;
            height[i] = 0;
            sum[i] = 0;
        }

        // DFS 실행
        dfs(1, -1);

        // 결과 출력
        for (int i = 1; i <= n; i++) {
            System.out.printf("Node %d: Parent=%d, Depth=%d, Size=%d, Height=%d, Sum=%d\n",
                    i, parent[i], depth[i], size[i], height[i], sum[i]);
        }
    }

    // 현재 노드 curr와 어디로부터 왔는지 prv 넘겨주기
    static void dfs(int curr, int prv) {
        size[curr] = 1; // 서브 트리 크기
        height[curr] = 0; // 서브 트리 높이
        sum[curr] = curr; // 서브트리 값의 합 (자기 자신 포함)

        for (int next : edge[curr]) {
            if (next == prv) continue; // 부모 노드로는 돌아가지 않음

            // 부모 노드 관련 정보
            parent[next] = curr;
            depth[next] = depth[curr] + 1;
            
            dfs(next, curr);

            // 서브트리 관련 정보
            size[curr] += size[next];
            height[curr] = Math.max(height[curr], height[next] + 1);
            sum[curr] += sum[next];
        }
    }
}

출력

Node 1: Parent=0, Depth=0, Size=5, Height=2, Sum=15
Node 2: Parent=1, Depth=1, Size=3, Height=1, Sum=11
Node 3: Parent=1, Depth=1, Size=1, Height=0, Sum=3
Node 4: Parent=2, Depth=2, Size=1, Height=0, Sum=4
Node 5: Parent=2, Depth=2, Size=1, Height=0, Sum=5

 

출처)

https://cs.kenyon.edu/index.php/scmp-218-00-data-structures/binary-search-tree/

https://www.designveloper.com/blog/tree-data-structure/

https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254