[알고리즘] 트리와 이진트리 - 이진트리(Binary Tree) 검색

이번 코딩테스트 문제는 이진검색을 활용해서 풀어야한다고 해서 이론공부를 먼저 하고, 관련된 실습문제를 따라 작성해보았다. 이진트리 이론은 이해했지만, 자바코드로 구현하려니 머리가 멍해졌다. 💭 자바코드로 구현할 때 노드 자체를 써 본 경험이 적어서 그런것 같아 이번기회에 정리하고 익숙해지려고 한다. 

 

1. 트리(Tree)

트리는 노드(Node)들과 이 노드들을 연결하는 링크(link)로 구성되며 계층적 구조를 표현할 때 사용된다.

• 조직도
• 디렉토리와 서브디렉토리 구조
• 가계도

 

트리(Tree) 의 기본 성질

• 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다.
• 트리 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다. (같은 노드를 두 번 이상 방문하지 않는다는 조건 하에)

 

트리(Tree) 용어

• 루트 노드 (Root Node) : 부모가 없는 노드, 트리는 하나의 루트노드를 가진다.
• 단말 노드 (Leaf Node) : 자식이 없는 노드
• 내부(Internal) 노드 : 단말 노드가 아닌 노드
• 링크 (Link) : 노드를 연결하는 선 (= edge, branch)
• 형제 (Sibling) : 같은 부모를 가진 노드

 

크기가 9이고, 높이가 3인 이진 트리

 

• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
  • 6의 깊이 : 2
  • 11의 깊이 : 3
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
  • 7의 차수 : 2 
  • 9의 차수 : 1
• 트리의 차수(degree of tree): 트리의 최대 차수
  
  • 최대 차수가 2이므로 트리의 차수 (디그리) 는 2
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이
  • 5, 11, 4의 깊이 : 3 → 트리의 높이 3

선형구조(Linear) - 일직선 상 
자료를 구성하는 데이터를 순차적으로 나열시킨 형태
배열, 리스트, 스택. 큐

비선형구조(NonLinear) - 일직선 상에 있지 않음
하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것을 의미
트리, 그래프

출처 : https://goodgid.github.io/DS-Linear-and-NonLinear/

 

2. 이진트리(Binary Tree)

• 이진 트리에서 각 노드는 최대 2개의 자식을 가진다.
• 각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지 지정된다. (자식이 한명인 경우에도)

왼쪽 자식노드 오른쪽 자식노드를 구분함 (서로 다른 이진트리)

이진 트리 종류

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

• 정 이진 트리 (Full Binary Tree) : 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
• 완전 이진 트리 (Complete Binary Tree) : 맨 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 가능한 한 가장 왼쪽에 있다. ➡ Heap
• 변질 트리 (Degenerate tree / Pathological tree) : 각 부모 노드는 오직 한 개의 연관 자식 노드를 갖는다. 이는 성능 면에서 트리가 연결 리스트 데이터 구조처럼 동작한다는 것을 의미한다.
• 포화 이진 트리 (Complete Binary Tree) : 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는다
• 균형 이진 트리 (Balanced Binary Tree) : 잎 노드에 대해 가능한 한 최대의 최소 높이(다른 말로 깊이)를 갖는데, 주어진 수의 잎 노드에 대해, 잎 노드가 가능한 가장 큰 높이에 위치하기 때문이다.

- 높이가 h인 정 이진트리는 2^h-1 개의 노드를 가진다.
- 노드가 N개인 정/완전 이진트리의 높이는 O(logN)이다.
- 노드가 N개인 이진트리의 높이는 최악의 경우 N이 될 수도 있다.

 

※ 이진 트리 순회 ( Traversal )

순회 : 이진 트리의 모든 노드를 방문하는 일

1. 전위 순회 (preorder)  : 자기 자신 - 왼 - 오
2. 중위 순회 (inorder) : 왼 - 자기 자신 - 오
3. 후위 순회 (postorder) : 왼 - 오 - 자기 자신
4. 레벨오더 순회 (level-order) : 레벨 순으로 방문 (동일 레벨에서는 왼쪽에서 오른쪽 순서로 방문) 큐(Queue)를 이용하여 구현

 

3. 이진트리 효율성

데이터의 탐색 속도 증진을 위해 사용하는 구조이다.

데이터를 검색할 때 전체 데이터를 검색하지 않고, 해당 데이터 집합(예:배열)에서의 중간값을 찾아 크기를 비교하는 방식으로 데이터를 검색한다. 

 

이진 검색 : 중간값을 구해서 해당 중간값보다 크거나 작은지를 판단해서 왼쪽/오른쪽 노드 지정
노드의 개수 : N
시간 복잡도 : O(logN)

 

출처 : youtube 엔지니어대한민국

예를 들어, 위 그림과 같이 저장된 배열에서 2 라는 값을 찾고 싶을 때. 이진트리는 0~9까지의 모든값을 조회하지 않고 중간 값(Root node)을 찾는다. 여기서 중간 값은 4 또는 5가 될 수 있기 때문에 중간 값을 정할 규칙을 정한다.

(더 작은 수가 중간값이 되는것으로 하자 - 왼쪽 값)

1. 중간 값을 찾는다. => 4
2. 찾고자하는 값이 중간 값보다 작은지 큰 지 판단 (2<4) 작으므로 4의 왼쪽노드에서만 탐색한다.
3. 원하는 값을 찾을때까지 반복

위의 방식으로 데이터를 탐색하기 때문에 해당하지 않는 반대편의 노드는 탐색 자체를 하지 않는다.

따라서 절반만 탐색해도 값을 찾을 수 있기 때문에 시간 복잡도는 O(logN) 이 된다. 

 

4. 이진트리 검색 실습

배열을 이진검색트리로 만들기 위해 재귀함수 이용 [필요한 값]

1. 배열
2. 시작 인덱스
3. 끝 인덱스
4. 중간값 찾기 (시작값 + 끝값) /2

[자료구조 알고리즘] 배열을 이진검색트리로 만들기 in Java

: 정렬이 되어있고, 고유한 정수로만 이루어진 배열이 있다. 이 배열로 이진검색트리를 구현하시오.

package Tree;

class Tree{
	class Node{
		int data;
		Node left;	//왼쪽 노드 저장 변수
		Node right;	//오른쪽 노드 저장 변수
		Node (int data){
			this.data = data;
		}
	}
	
	//Tree class의 멤버변수 (시작점 root Node 변수
	Node root;
	
	//재귀호출에 필요한 데이터를 처음으로 지정 
	//재귀호출이 끝나면 root 노드의 주소를 받아서 멤버변수에 저장
	public void makeTree(int [] a) {
		root = makeTreeR(a, 0, a.length-1);
	}
	
	public Node makeTreeR(int [] a, int start, int end) {
		//재귀호출을 마치고 null을 반환하라 (끝나는 시점을 명시)
		if(start > end) return null;
		int mid = (start + end) / 2; 	//중간점
		// 노드 지정
		Node node = new Node(a[mid]);
		node.left = makeTreeR(a, start, mid-1);
		node.right = makeTreeR(a, mid+1, end);
		return node;
	}
	
	//트리가 잘 만들어졌는지 이진검색 함수로 확인
	public void searchBTree (Node n, int find) {
		//찾아야하는 값이 현재노드의 데이터(n.data)보다 작은지 비교
		if (find < n.data) {
			System.out.println("Data is smaller than " + n.data);
			//찾는 값이 더 작으니까 왼쪽노드의 주소를 넘기고, 찾는 값을 넘김 (반복 호출)
			searchBTree(n.left, find);
		}else if (find > n.data) {
			System.out.println("Data is bigger than " + n.data);
			//찾는 값이 더 크니까 오른쪽노드의 주소를 넘기고, 찾는 값을 넘김 (반복 호출)
			searchBTree(n.right, find);
		}else {
			System.out.println("Data Found!");
		}
	}
}
public class TreeTest {
	public static void main(String[] args) {
		int [] a = new int [10];
		for(int i=0;i<10;i++) {
			a[i] = i;
		}
		
		Tree t = new Tree();
		//해당 배열로 트리 만들고, 멤버변수 root에 저장
		t.makeTree(a);
		//검색을 시작할 위치 (t.root), 찾는 값 지정
		t.searchBTree(t.root, 6);
	}
}

 

 

[ 참고 ]

교수님 강의 : www.youtube.com/watch?v=TdakkF5Xh6o
실습 : www.youtube.com/watch?v=9ZZbA2iPjtM

jiwondh.github.io/2017/10/15/tree/