트리

트리

자료의 구현이 단순하고 다양한 변형이 가능

주로 계층적인 구조를 표현하기 위한 자료구조

데이터가 저장되어 있는 노드, 노드와 노드를 연결하는 간선(edge, 링크)로 이루어짐

간선으로 연결된 노드는 상하 관계를 형성

 

상하 관계에서 상위에 위치한 노드는 부모 노드, 하위에 위치한 노드는 자식 노드

노드는 하나 이상의 자식 노드를 가질 수 있지만 부모 노드는 하나만 존재

 

같은 부모 노드를 공유하는 노드는 형제 노드

부모 노드와 그 부모 노드들은 조상 노드, 자식 노드와 그 자식 노드들은 자손 노드

부모 노드가 없는 최상단 노드는 루트 노드, 자식 노드가 없는 최하단 노드는 리프노드

 

차수 : 각 노드가 가지는 자식 노드의 수

레벨(깊이) : 루트 노드에서 특정 노드까지 거치는 간선의 수

높이 : 가장 높은 레벨
서브 트리 : 트리 안에 포함되어 있는 트리

 

하나의 노드는 데이터와 자식 노드의 메모리 주소를 저장

 

트리의 순회

트리의 모든 노드를 한 번씩 방문하는 것

 

전위 순회

루트 노드 -> 왼쪽 서브트리 전위 순회-> 오른쪽 서브 트리 전위 순회

void preOrderTraversial(const Node* node){
	if (node == nullptr)
		return;

	// node->data;

	preOrderTraversial(node->leftChild);
	preOrderTraversial(node->rightChild);
}

 

중위 순회

왼쪽 서브트리 중위 순회 -> 루트 노드 -> 오른쪽 서브 트리 중위 순회

void inOrderTraversial(const Node* node)
{
	if (node == nullptr)
		return;

	inOrderTraversial(node->leftChild);
	
	// node->data;

	inOrderTraversial(node->rightChild);
}

 

후위 순회

왼쪽 서브트리 후위 순회 -> 오른쪽 서브트리 후위순회 -> 루트노드

void postOrderTraversial(const Node* node)
{
	if (node == nullptr)
		return;

	inOrderTraversial(node->leftChild);
	inOrderTraversial(node->rightChild);
	
	// node->data;
}

 

레벨 순서 순회

레벨의 순서대로 노드를 순회하는 방법

void levelTraversial(const Node* rootNode)
{
	queue<const Node*> nodeTraversialQueue;
	nodeTraversialQueue.push(rootNode);

	while (nodeTraversialQueue.empty() == false)
	{
		const Node* currentNode = nodeTraversialQueue.front();
		nodeTraversialQueue.pop();

		// currentNode->data;

		nodeTraversialQueue.push(currentNode->leftChild);
		nodeTraversialQueue.push(currentNode->rightChild);
	}
}

 

트리의 종류

이진 트리(binary tree)

자식 노드의 개수가 2개 이하인 트리

 

편향된 이진 트리(skewed binary tree)

모든 자식 노드가 한 쪽으로 치우친 이진 트리

 

정 이진 트리(full binary tree)

자식 노드의 개수가 0개 또는 2개인 이진 트리

리프 노드를 제외하면 자식 노드의 개수가 2개

 

포화 이진 트리(perfect binary tree)

리프 노드를 제외한 모든 노드들이 자식 노드를 2개씩 가지고 있고, 모든 리프 노드의 레벨이 동일한 이진 트리

 

완전 이진 트리(complete binary tree)

마지막 레벨을 제외한 모든 레벨이 2개의 자식 노드를 가지고 있으며 마지막 레벨의 모든 노드들이 왼쪽부터 존재하는 이진 트리

 

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

특정 노드의 왼쪽 자식 노드는 해당 노드보다 작은 값, 오른쪽 자식노드는 해당 노드보다 큰 값이 있는 구조의 이진 트리

 

탐색 성능

O(logn), 최악의 경우(편향된 이진 트리)  O(n)

삭제와 삽입을 반복하는 과정에서 편향된 이진 트리가 될 수 있는 문제

 

힙(Heap)

부모 노드의 우선 순위가 자식 노드의 우선순위보다 높은 완전 이진 트리

노드 간 크기의 비교는 숫자 뿐만 아니라 우선순위를 지정할 수 있음

우선순위 큐가 힙으로 구현됨

 

최댓값과 최솟값을 빠르게 찾기 위해 사용됨

탐색 성능은 이진 탐색 트리와 유사

 

최대힙

부모 노드가 자식 노드의 값보다 큰 값으로 이루어진 완전 이진 트리

 

최소힙

부모 노드가 자식 노드의 값보다 작은 값으로 이루어진 완전 이진 트리

 

자가 균형 이진 탐색 트리(self-balancing binary search tree) : RB(Red Black) 트리

이진 탐색 트리에서 편향된 이진 트리가 될 수 있는 문제를 해결하기 위해 양쪽 서브트리의 높이의 균형을 맞추는 트리

모든 노드를 빨간색 혹은 검은색으로 칠한 트리

C++에서 map과 set 내부 구현에 사용됨

 

특징

루트 노드와 리프 노드는 블랙 노드

레드 노드의 자식 노드는 블랙 노드

루트 노드에서 임의의 리프 노드에 이르는 경로의 블랙 노드 수는 같음

즉, 최대 깊이는 최소 깊이의 2배를 초과할 수 없음

• 모든 노드가 검은색일 때 최소 깊이이므로 h
• 검은색과 빨간색 노드가 번갈아 나올 때 최대 깊이 2h가 됨

이러한 특징은 항상 균형 잡힌 상태를 유지하도록 보장하며, 이는 O(log n)의 시간 복잡도를 보장하는 핵심 요소가 됩니다.

 

리프 노드는 실질적인 데이터가 저장되어 있지 않은 노드, NIL(Null Leaf) 노드라고 부름

 

새 노드를 삽입할 때는 3번 조건을 만족하기 위해 레드 노드로 삽입

노드 삽입 이후 3개의 조건이 모두 만족하지 않을 때 트리를 회전하거나 색상을 재지정해야 함

 

트리의 회전

양쪽 서브트리 높이의 균형을 맞추기 위해 부모 노드와 자식 노드의 관계를 재지정하는 것

왼쪽 혹은 오른쪽 방향으로 회전이 이루어질 수 있고 회전 직후여도 이진 탐색 트리는 유지돼야 함

 

왼쪽 회전

R을 기준으로 왼쪽 회전한다면 N은 R의 왼쪽 자식이 되고 RL이 N의 오른쪽 자식이 됨

 

오른쪽 회전

L을 기준으로 오른쪽 회전한다면 N은 L의 오른쪽 자식이 되고 LR이 N의 왼쪽 자식이 됨

 

색을 재지정 및 트리 회전을 결정하는 알고리즘

노드 삽입시 알고리즘

BST 알고리즘으로 노드 삽입

 

삽입한 노드가 루트 노드일 경우 블랙으로 변경하고 종료

부모가 블랙인 경우 RB 트리 조건을 만족하므로 종료

 

부모가 레드인 경우

• 삼촌이 레드일 경우
  부모와 삼촌을 블랙으로 변경하고 조부모를 레드로 변경
  조부모를 기준으로 부모가 레드라면 윗줄의 과정으로 다시 검사
  루트까지 반복
• 삼촌이 블랙일 경우
  • 부모 노드와 삽입한 노드를 일직선상에 위치해야 함
    부모가 조부모의 왼쪽 자식이고 삽입한 노드가 부모의 오른쪽 자식인 경우 삽입한 노드를 기준으로 왼쪽 회전
    부모가 조부모의 오른쪽 자식이고 삽입한 노드가 부모의 왼쪽 자식인 경우 삽입한 노드를 기준으로 오른쪽 회전
  • 부모가 레드이므로 조부모는 블랙인 상태에서 부모와 조부모의 색을 교환
  • 부모가 조부모의 왼쪽 자식이라면 조부모를 기준으로 오른쪽 회전
    부모가 조부모의 오른쪽 자식이라면 조부모를 기준으로 왼쪽 회전

 

노드 삭제시 알고리즘

BST 알고리즘으로 노드 삭제

 

삭제하려는 노드의 색

삭제하려는 노드의 자녀가 없거나 하나라면 삭제되는 노드의 색으로 결정

삭제하려는 노드의 자녀가 2개라면 successor(삭제하려는 노드 다음으로 값을 가지는 노드)의 색으로 결정

• BST의 특성으로 successor는 항상 왼쪽 자식이 없으므로 삭제하려는 노드의 자녀가 0개 또는 1개와 동일
  succesor의 값을 삭제하려는 노드와 교환하고 successor의 노드를 삭제하기 때문

 

삭제된 노드가 레드인 경우 RB 트리 조건을 만족하므로 종료

 

삭제된 노드가 블랙인 경우

루트를 삭제하여 자식이 루트가 되고 레드일 때 블랙으로 변경

나머지의 경우 3번 조건을 만족하기 위해(경로에 블랙을 추가하기 위해) 삭제된 색의 위치의 노드에 extra black을 부여

레드에 extra black이 부여된 노드는 블랙으로 변경하여 해결

 

더블 블랙(블랙에 extra black이 부여된 노드)일 경우

 

Case 1 더블 블랙의 오른쪽 형제가 블랙 & 그 형제의 오른쪽 자녀가 레드(부모를 기준으로 좌우 대칭된 케이스도 포함)

결론 : 오른쪽 형제는 부모의 색, 부모와 오른쪽 형제의 오른쪽 자녀는 블랙으로 변경하고 부모를 기준으로 왼쪽 회전

 

부모와 자식간의 색을 교환해도 RB 트리의 조건을 만족
오른쪽 형제와 그 자식들의 색을 교환하여 오른쪽 형제는 레드, 왼쪽 자식은 원래 색 + extra black, 오른쪽 자식은 블랙

부모와 오른쪽 형제의 색을 교환한 후 부모를 기준으로 왼쪽 회전

색을 교환해야 회전한 후 3번 속성을 만족함

 

A와 C의 extra black을 B로 올려 B를 블랙으로 만듦

 

Case 2 더블 블랙의 오른쪽 형제가 블랙 & 그 형제의 왼쪽 자녀가 레드 & 그 형제의 오른쪽 자녀는 블랙

C와 D 색을 교환한 후 D를 기준으로 오른쪽 회전 하면 case 1 첫 번째 사진과 같으므로 case 1 알고리즘 적용

 

Case 3 더블 블랙의 형제가 블랙 & 그 형제의 두 자녀 모두 블랙

더블 블랙의 extra black과 형제의 블랙을 부모에게 전달

부모가 red-and-black이면 블랙으로 변경

부모가 더블 블랙일 때 루트 노드면 블랙으로 변경, 아니라면 부모를 기준으로 케이스에 맞는 case 1~4를 적용

 

Case 4 더블 블랙의 형제가 레드

형제와 부모의 색을 교환한 후 형제를 기준으로 왼쪽 회전 후 A와 C의 블랙을 B로 올려 B는 블랙이 되고, C는 레드가 됨

 

대용량 입출력을 위한 트리

B 트리

균형을 유지하는 트리

이진 탐색 트리가 아닌 다진 탐색 트리

 

한 노드가 가질 수 있는 최대 자식 노드의 개수가 M개인 B 트리를 M차 B 트리라고 부름

M차 B 트리가 (루트와 리프 노드를 제외하고) 가질 수 있는 최소 자식 노드의 개수는 [M/2](M/2 올림, M이 5라면 3)개

• M개를 초과했을 때 분할하면 M/2정도가 되기 때문

 

각 노드에 하나 이상의 키 값이 존재하고 키 값을 기준으로 오름차순으로 저장됨

키 값 자체를 데이터로 할 수 있고, 일반적으로 데이터를 찾기 위한 인덱스로 활용됨

 

자식 노드 사이에 키를 저장하여 키가 자식노드(서브트리)가 가질 수 있는 값의 범위를 나타냄

키 N개인 노드가 가질 수 있는 자식 노드의 수는 반드시 N+1개

따라서 각 자식 노드의 값이 왼쪽 자식노드부터 오른쪽 자식노드까지 정렬된 상태

 

모든 리프 노드의 깊이가 같아 편향된 형태는 발생하지 않음

 

파일 시스템, 데이터베이스와 같이 대량의 데이터를 기반으로 탐색, 접근, 저장을 수행할 때 활용

입출력 연산이 메모리 접근에 비해 수행 속도가 느리므로 한 블록에 여러 키를 저장하여 입출력 연산을 줄임

• 운영체제는 블록 단위로 보조기억장치를 읽고 쓰는데, 한 노드에 하나의 키만 저장되는 이진 탐색 트리에 비해 블록 단위의 여러 키를 저장할 수 있음

 

B+ 트리

B 트리를 그대로 사용하기보다 약간 변형된 형태의 B+ 트리를 사용하는 경우가 많음

 

실질적인 데이터가 모두 리프 노드에 위치

리프 노드가 아닌 노드는 자식노드의 범위를 분할할 용도로 사용되는 키, 자식노드의 주소만 저장

 

리프 노드는 연결 리스트의 형태로, 순차적 접근을 통해 부모 노드와 다른 리프 노드들 간의 범위 연산이 용이