[자료구조] 트리(Tree)

 

 

 

 

 

 

 

 

 

자료구조, 트리(Tree)에 대해 알아보기 

---

 

 

 

 

 

Tree는 계층적인 데이터 구조로서 컴퓨터 과학 및 프로그래밍에서 광범위하게 활용되는 중요한 개념입니다. 

 

 

 

 

Tree의 구조와 특징

 

트리는 노드(Node)와 엣지(Edge)로 구성되며, 각 노드는 하나의 부모 노드와 여러 개의 자식 노드를 가질 수 있습니다.

 

이러한 구조는 계층적인 관계를 표현하는 데 유용하며, 루트노드(Root Node)에서 리프노드(Leaf Node)로 이어지는 경로가 존재합니다.

 

• 트리에는 사이클이 없음
• 트리에서 루트노드를 제외한 모든 노드는 단 하나의 부모노드를 가짐

 

 

 

Tree의 종류

 

1. 이진트리(Binary Tree)

 

트리의 여러 자료구조 유형 중 가장 기본이 되는 구조입니다. 

이진트리는 2개 이하의 자식노드를 갖습니다. (자식이 없거나 1개만 갖는 것도 가능)

2개의 자식노드 중 왼쪽 노드를 Left Node, 오른쪽 노드를 Right Node라고 합니다. 

 

이진트리 예시

 

 

이진트리에는 3가지 종류가 있습니다. 

• 편향 이진트리(Skewed Binary Tree)
• 포화 이진트리(Full Binary Tree)
• 완전 이진트리(Complete Binary Tree)

 

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

 

하나의 차수로만 이루어진 트리입니다. 

 

배열리스트와 같은 선형구조이므로 리프노드 탐색 시 모든 데이터를 탐색해야해서 비효율적입니다. 

 

편향이진트리 예시

 

 

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

 

리프노드를 제외한 모든 노드의 차수가 2개로 이루어진 트리입니다. 

 

해당 차수에 몇 개의 노드가 존재하는지 알 수 있어 노드 개수를 파악하기 용이합니다. 

 

 

포화이진트리 예시

 

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

 

포화 이진트리와 같이 리프 노드를 제외한 모든 노드의 차수가 2개로 이루어진 트리입니다.

 

포화 이진트리와의 다른점은 모든 노드가 왼쪽부터 생성된다는 것입니다. 

 

힙(Heap)은 완전 이진트리의 일종입니다. 

 

 

완전이진트리 예시

 

 

2. 이진 탐색 트리(Binary Search Tree)

 

이진 탐색 트리는 탐색을 위한 이진 트리 기반의 자료구조 입니다. 

 

• left node에는 부모노드보다 작은 값이 저장됨
• right node에는 부모노드와 값이 같거나 큰 값이 저장됨 
• 모든 노드는 중복값을 가지지 않음 

이진탐색트리 예시

 

 

 

 

 

3. 레드 블랙 트리 (Red Black Tree)

 

레드 블랙 트리는 자기 균형을 유지하는 이진 검색 트리입니다. 아래 규칙을 통해 트리가 저절로 균형을 잡도록 돕습니다. 따라서 탐색, 삽입, 삭제 연산을 안정적으로 빠른 시간 내에 처리할 수 있습니다. 

 

• 각 노드는 레드 혹은 블랙의 색상을 가짐
• 루트 노드와 모든 리프 노드는 블랙
• 레드 노드는 연속으로 오지 않음
• 모든 단순 경로에서 블랙 노드의 수는 동일

 

레드블랙트리 예시

 

 

 

 

4. B 트리 (B Tree)

 

B 트리는 주로 데이터베이스 및 파일 시스템에서 사용되는 자료구조입니다.

 

• 모든 리프 노드는 같은 레벨에 위치
• 각 노드는 키를 저장하며, 노드당 최소 t-1개, 최대 2t-1개의 키를 가짐(t는 트리의 차수)
• 노드의 키는 정렬된 상태로 유지되며, 노드 간 분할 및 병합을 통해 트리의 균형을 유지
• B 트리는 대규모 데이터의 효율적인 관리를 가능하게 하며, 트리의 높이를 낮게 유지하여 검색 시간을 최소화

 

B트리 예시

 

 

 

 

 

Tree의 순회

 

트리에서 순회란, 트리의 각 노드를 체계적인 방법으로 탐색하는 것입니다. 

 

노드를 탐색하는 순서에 따라 아래와 같이 분류됩니다. 

 

트리 예시

 

1. 전위 순회(preorder)

 

전위순회는 깊이 우선 순회(depth-first traversal)라고도 합니다. 

 

• 루트노드 - 왼쪽 서브트리 - 오른쪽 서브트리
• F - B - A - D - C - E - G - I - H

void preOrderTraversal(TreeNode root){
	if(root == null) return;
    
    System.out.print(root.val + " "); //루트노드
    
    preOrderTraversal(root.left);    //왼쪽 서브트리
     
    preOrderTraversal(root.right);   //오른쪽 서브트리 
}

 

 

2.중위 순회(inorder)

 

중위순회는 대칭 순회(symmetric)라고도 합니다. 

 

• 왼쪽 서브트리 - 노드 - 오른쪽 서브트리 
• A - B - C - D - E - F - G - H - I

void inOrderTraversal(TreeNode root){
	if(root == null) return;
    
    inOrderOTraversal(root.left);       //왼쪽 서브트리
    
    System.out.print(root.val + " ");  //루트노드
    
    System.out.print(root.right);     //오른쪽 서브트리 
}

 

3. 후위 순회(postorder)

 

• 왼쪽 서브트리 - 오른쪽 서브트리 - 노드 
• A - C - E - D - B - H - I- G - F 

void postOderTraversal(TreeNode root){
	if (root == null) return;
    
    postOderTreversal(root.left);       //왼쪽 서브트리
    
    postOderTraversal(root.right);     //오른쪽 서브트리
    
    System.out.print(root.val + " "); //루트노드 
}

 

4.레벨 순회(levelorder)

 

레벨 순회는 너비 우선 순회(breadth-first traversal)라고도 합니다. 

 

• 모든 노드를 낮은 레벨부터 차례로 순회
• 레벨이 같을 경우, 좌 -> 우로 방문 
• F - B - G - A - D - I - C - E - H

 

 

자바를 통한 구현 

class TreeNode{
	int val;
    TreeNode left;
    TreeNode right;
    
    public TreeNode(int val){
    	this.val = val;
        this.left = null;
        this.right = null;
    }
}


public class Main{
	public static void main(String[] args){
    
    //이진트리 생성
    TreeNode root = new TreeNode(F);
    root.left = new TreeNode(B);
    root.right = new TreeNode(G);
    root.left.letf = new TreeNode(A);
    root.left.right = new TreeNode(D);
    root.left.right.left = new TreeNode(C);
    root.left.right.right = new TreeNode(E);
    root.right.right = new TreeNode(I);
    root.right.right.left = new TreeNode(H);
    
    
    //전위순회 
    System.out.print("전위 순회: ");
    preOrderTraversal(root);
    System.out.println();
    
    //중위순회
    System.out.print("중위 순회: ");
    inOrderTraversal(root);
    System.out.println();
    
    //후위순회
    System.out.print("후위 순회: ");
    postOrderTraversal(root);
    System.out.println();
    
    }
}