트리(Tree)의 개념과 종류 / Java 구현

 

 

이전 포스팅의 스택과 큐는 선형 자료구조라고 부릅니다. 선형 자료구조는 데이터를 순차적으로 나열시킨 구조를 뜻합니다. 이번 포스팅에서는 비선형 자료구조인 트리(Tree)에 대해서 알아봅시다!

 

 

트리(Tree)란 ?

 

비선형이 무엇일까요? 비선형 자료구조는 선형 구조와는 다르게 데이터가 계층적으로 구성되어 있습니다. 

비선형 자료구조인 트리는 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 자료구조입니다. 즉, 데이터 요소들의 단순한 나열이 아닌 부모 - 자식 관계의 계층적 구조로 표현됩니다. 

 

그렇다면 트리의 구조를 그림과 함께 알아봅시다.

 

 

루트, 부모, 자식, 레벨 등 다양한 용어가 존재합니다. 이것들을 한번 정리하고 가야겠죠.

 

• node: 트리를 구성하고 있는 각 요소
• Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선
• Root Node: 최상위 계층에 존재하는 노드
• level: 트리의 특정 깊이를 가지는 노드의 집합
• degree(차수): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드
• Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함

트리의 구현

자바로 트리를 구현해보았습니다.

 

public class TreeNode {
	
	private Object data;
	private TreeNode left;
	private TreeNode right;
	public TreeNode(Object data){
		this.data = data;
		left = null;
		right = null;
	}
	
	public void makeLeftSubTree(TreeNode node) {
		if(this.left != null) this.left = null;
		this.left = node;
	}
	
	public void makeRightSubTree(TreeNode node) {
		if(this.right !=null) this.right = null;
		this.right = node; 
	}
	
	public Object getData() {
		return this.data;
	}
	
	public TreeNode getLeftSubTree() {
		return this.left;
	}
	
	public TreeNode getRightSubTree() {
		return this.right;
	}
	
	public static void main(String[] args) {
		
		TreeNode T1 = new TreeNode(1);
		TreeNode T2 = new TreeNode(2);
		TreeNode T3 = new TreeNode(3);
		TreeNode T4 = new TreeNode(4);
		
		T1.makeLeftSubTree(T2);
		T1.makeRightSubTree(T3);
		T2.makeLeftSubTree(T4);

		System.out.println(T1.getLeftSubTree().getData());
		System.out.println(T1.getRightSubTree().getData());		
		System.out.println(T2.getLeftSubTree().getData());
		
	}
}

 

 

 

이진 트리의 종류

 

- Full Binary Tree(정 이진 트리)

트리의 모든 노드가 0개 혹은 2개의 자식을 갖는 경우입니다. 즉 자식을 하나만 가지는 노드는 없습니다.

 

 

- Completed Binary Tree(완전 이진 트리)

완전 이진 트리는 마지막 레벨을 제외한 나머지 노드가 꽉 차있어야 하며, 마지막 레벨의 노드도 왼쪽으로 몰려있어야 합니다. 완전 이진 트리는 힙(Heap) 정렬에서 쓰이기도 합니다.

 

 

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

포화 이진 트리는 Full Binary Tree이면서 Completed Binary Tree 입니다. 즉 모든 레벨에서 노드가 꽉 차있는 트리를 의미합니다.

 

 

- Binary Search Tree(이진 탐색 트리)

이진 탐색 트리란 Binary Tree의 속성을 가지면서 자식 노드의 크기가 왼쪽에서 오른쪽 순서로 연결되는 것입니다. 즉 노드의 왼쪽 서브트리는 그 노드의 값보다 작은 값을 가지는 노드들로 구성되어 있고, 노드의 오른쪽 서브트리는 그 노드의 값과 같거나 큰 값을 가지는 노드들로 구성되어 있습니다.

 

 

 

 

 

 

 

 

이번 포스팅에서는 트리의 종류에 대해서 알아보았습니다.

다음 포스팅에서는 Binary Search Tree를 직접 구현해보도록 하겠습니다. :)