Portfolio

트리 용어 특징 순회 방법 트리의 종류 Refer

트리

트리는 그래프의 일종으로, 사이클 순환이 없는 연결 그래프이자 계층척 구조를 표현하기 위한 자료구조 입니다.

실생활 비유

기업의 조직도

컴퓨터 파일시스템

나무

용어

노드(node): 트리를 구성하는 기본 원소

루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점

부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드
형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
리프 노드(leaf node/leaf): 루트 노드를 제외한 차수가 1인 정점을 뜻한다. 쉽게 말해 자식이 없는 노드. 단말 노드라 부르기도 한다.

깊이(depth): 루트 경로의 길이

레벨(level): 루트 노드(level=0)부터 노드까지 연결된 간선 수의 합

높이(height): 가장 긴 루트 경로의 길이

차수(degree): 각 노드의 자식의 개수

트리의 차수(degree of tree): 트리의 최대 차수

크기(size): 노드의 개수

너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기

특징

계층적: 각 간선은 방향성을 가지며 부모에서 자식으로만 연결, 간선의 개수는 반드시 노드의 개수 -1 개

방향성: 모든 경로는 루트노드로 부터 시작

비순환성: 임의의 노드에 출발하여 자기 자신으로 되돌아 오지 않는 비순환적

장점

데이터 삽입,삭제, 탐색의 효율성이 높다 := 시간 복잡도 평균 O(N)

계층적 관계 표현 용이

단점

구현 복잡성(수정,삭제)

균형 문제(편향 트리)

배열과는 대조적으로 메모리 사용량이 많음 → link

순회 방법

중위 순회(in-order traversal): 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문하는 순회 방법. 이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있습니다.

전위 순회(pre-order traversal): 자신, 왼쪽 자손, 오른쪽 자손 순서로 방문하는 순회 방법.

후위 순회(post-order traversal): 왼쪽 자손, 오른쪽 자손, 자신 순서로 방문하는 순회 방법.

레벨 순서 순회(level-order traversal): 너비 우선 순회(Breadth-First traversal)라고도 한다. 노드를 레벨 순서로 방문하는 순회 방법.

위의 세 가지 방법은 스택을 활용하여 구현할 수 있는 반면 레벨 순서 순회는 큐(BFS)를 활용해 구현할 수 있습니다.

위의 트리를 순회하면 다음과 같습니다.

In-order: 1 3 4 6 7 8 10 13 14

Pre-order: 8 3 1 6 4 7 10 14 13

Post-order: 1 4 7 6 3 13 14 10 8

Level-order: 8 3 10 1 6 14 4 7 13

트리의 종류

이진트리 : 각 노드가 최대 2개의 자식노드를 갖는 트리

정이진트리 Full Binary Tree == Strict Binary Tree: 모든 노드가 2개의 자식을 갖거나 자식이 없는 경우 즉, 자식이 한개인 경우는 없어야 합니다.

완전이진트리 Complete Binary Tree: 노드의 자식은 반드시 왼쪽부터 채워줘야 합니다.

포화이진트리 Perfect Binary Tree: 마지막 레벨의 노드를 제외하고 모든 노드가 2개의 자식 노드를 갖는 트리입니다.

힙 트리: 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리. 짧게 힙(Heap)이라고 줄여서 부르기도 합니다

시간복잡도

삽입: logN

메커니즘 (부모와 대소비교를 하며 위치를 찾아나간다)

가장 끝의 자리에 노드를 삽입한다. (완전 이진트리 성질로 가장 왼쪽 자식부터 채운다)

그 노드와 부모 노드를 서로 비교한다.

규칙에 맞으면 그대로 두고, 그렇지 않으면 부모와 교환한다. (부모노드는 삽입된 위치의 인덱스 번호에서 /2를 하면 쉽게 구할 수 있다.)

규칙에 맞을 때까지 3번 과정을 반복한다.

삭제: logN (가장 늦게 삽입된 데이터를 root로 대치, root에 위치한 노드는 아래로 내려가며 자리를 잡아간다.)

루트 노드를 제거한다.

루트 자리에 가장 마지막 노드를 삽입한다.[3]

올라간 노드와 그의 자식 노드(들)와 비교한다.

조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다.

최대 힙

부모보다 더 큰 자식이 없으면 교환하지 않고 끝낸다.

부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환하면 된다.

부모보다 더 큰 자식이 둘 있으면 자식들 중 큰 값과 교환한다.

최소 힙

부모보다 더 작은 자식이 없으면 교환하지 않고 끝낸다.

부모보다 더 작은 자식이 하나만 있으면 그 자식하고 교환하면 된다.

부모보다 더 작은 자식이 둘 있으면 자식들 중 작은 값과 교환한다.

5. 조건을 만족할 때까지 4의 과정을 반복한다.

이진탐색트리(Binary Search Tree): 이진 트리의 일종으로 노드의 왼쪽 가지에는 노드의 값보다 작은 값들이 있고 오른쪽 가지에는 큰 값들만 있어야 하는 트리입니다.

삽입: 루트노드를 기점으로 시작하여 점차 자식 노드방향으로 향하면서 위치를 찾아갑니다. (대소비교)

삭제:

1) 자식노드가 없을 경우 (똑 떼어내기)

2) 자식노드가 1개있는 경우 (자식 노드를 위로 붙여주기)

5의 오른쪽 포인터의 7을 끊어주고 9로 연결해줍니다. 절대로 값만 대치시켜서는 안됩니다.

만약 9 밑에 많은 노드들이 있는 경우를 보면 값만 대치기 시킨다면 9의 자식 노드, 자식의 자식 노드 모두 버리게 되면서 문제가 발생합니다.

그렇기 때문에 값을 대치시키는 것이 아닌 5의 오른쪽 향하는 부분을 9로 연결해 줘야 합니다.

3) 자식노드가 두개 인 경우 (해당 노드를 대치시킬 노드를 찾아라)

BST는 삽입시 해당 노드에서 작은 값을 왼쪽 큰 값을 오른쪽으로 삽입합니다.

이점을 생각하고 대치시킬 노드를 찾아야합니다. 대치시킬 노드를 찾기 위해서는 서브트리를 이용해야합니다.

지울 노드 기점으로 왼쪽 서브트리에서 가장 오른쪽에 위치한 노드, 오른쪽 서브 트리에서 가장 왼쪽에 위치한 노드를 찾아야 합니다.

[오른쪽 서브트리 기점으로 대치시키기]

대치시킬 노드가 리프 노드일 경우

15를 지우기 위해서 오른쪽 서브트리 기점에서 가장 작은 값인 17을 찾고 그것을 대치시키면 됩니다.

2) 오른쪽 서브트리의 대치시킬 노드가 자식노드가 있는 경우

지울 노드의 값을 17로 대치 시키고 원래 있던 17을 지워줘야 합니다.

이때, 우리는 2개의 자식노드를 지우다가 자식노드가 1개 일때 지우는 것이 필요하게 됩니다.

자식노드가 1개 일때에는 이전에 설명드렸듯이 지울 대상의 자식노드를 붙여주면

자식 노드가 2개 인경우에도 BST 구조가 유지되면서 안정적으로 삭제 할 수 있게 됩니다.

요약하자면 2개의 자식노드가 있는 대상을 지울 때, 자식노드가 1개일 경우 지우는 부분이 필요 할 수도 것입니다.

여기 까지 봤을 때 이런 의문이 들 수 있습니다.

오른쪽 서브트리의 대치시킬 노드가 자식 노드를 2개 가질 수도 있지 않나요?

양쪽이 다 있는 경우일 수 가 없습니다. 왜냐하면 오른쪽 서브트리, 오른쪽 오른쪽 서브트리, 오른쪽 …. 서브트리에서 가장 작은 값을 찾기 위해 수행하기 때문에 자식 노드가 2개라면 이미 가장 작은 값은 왼쪽 노드로 선별 되어 나올 것입니다!

오른쪽 서브트리의 대치시킬 노드가 왼쪽만 있을 수도 있지 않나요?

삭제할 대상의 양쪽 자식이 모두 존재한다는 가정이 있고 오른쪽 서브트리의 가장 작은 값을 찾기 위해서 오른쪽으로 먼저 향한 뒤 왼쪽에만 자식이 존재하는 경우에는 오른쪽으로 먼저 향한 값을 반환할 것입니다.


void deleteKey(int key) {
			root = delete_Recursive(root, key);
		}

		Node delete_Recursive(Node root, int key) {
			if (root == null)
				return root;

			
			if (key < root.key)     
				root.left = delete_Recursive(root.left, key);
			else if (key > root.key)  
				root.right = delete_Recursive(root.right, key);
			else {
			
				// 한쪽 자식만 있는 경우
				if (root.left == null)
					return root.right;
				else if (root.right == null)
					return root.left;

				// 양쪽 자식이 있는 경우
				root.key = minValue(root.right);

				// 오른쪽 서브트리의 자식 이어붙이기
				root.right = delete_Recursive(root.right, root.key);
			}
			return root;
		}