트리 (Tree)
트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조입니다.
트리는 다음과 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사합니다.
트리는 또한 트리 내에 다른 하위 트리가 있고 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 합니다.
컴퓨터의 direcory구조가 트리 구조의 대표적인 예가 될 수 있습니다.
트리 구조에서 사용되는 기본 용어
노드 (Node)
•
트리를 구성하고 있는 기본 요소
•
노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음.
•
A, B, C, D, E, F, G, H, I, J
간선 (Edge)
•
노드와 노드 간의 연결선
루트 노드 (Root Node)
•
트리 구조에서 부모가 없는 최상위 노드
•
root node : A
부모 노드 (Parent Node)
•
자식 노드를 가진 노드
•
H, I에 부모 노드는 D
자식 노드 (Child node)
•
부모 노드의 하위 노드
•
노드 D의 자식 노드는 H, I
형제 노드 (Sibling node)
•
같은 부모를 가지는 노드
•
H, I는 같은 부모를 가지는 형제 노드
외부 노드(external node, outer node), 단말 노드 (terminal node), 리프 노드(leaf node)
•
자식 노드가 없는 노드
•
H, I, J, F, G
내부 노드 (internal node, inner node), 비 단말 노드 (non-terminal node), 가지 노드 (branch node)
•
자식 노드 하나 이상 가진 노드
•
A, B, C, D, E
깊이 (depth)
•
루트에서 어떤 노드까지의 간선(Edge) 수
•
루트 노드의 깊이 : 0
•
D의 깊이 : 2
높이 (height)
•
어떤 노드에서 리프 노드까지 가장 긴 경로의 간선(Edge) 수
•
리프 노드의 높이 : 0
•
A 노드의 높이 : 3
트리 종류
편향 트리 (skew tree)
•
모든 노드들이 자식을 하나만 가진 트리
•
왼쪽 방향으로 자식을 하나씩만 가질 때 left skew tree, 오른쪽 방향으로 하나씩만 가질 때 right skew tree라고 함.
이진트리 (Binary Tree)
•
각 노드의 차수(자식 노드)가 2 이하인 트리
이진 탐색 트리 (Binary Search Tree, BST)
•
순서화된 이진 트리
•
노드의 왼쪽 자식은 부모의 값보다 작은 값을 가져야 하며 노드의 오른쪽 자식은 부모의 값보다 큰 값을 가져야 함.
m 원 탐색 트리(m-way search tree)
•
최대 m개의 서브 트리를 갖는 탐색 트리
•
이진 탐색 트리의 확장된 형태로 높이를 줄이기 위해 사용함.
균형 트리 (Balanced Tree, B-Tree)
•
m원 탐색 트리에서 높이 균형을 유지하는 트리
•
height-balanced m-way tree라고도 함.
사용 사례
계층 적 데이터 저장
•
트리는 데이터를 계층 구조로 저장하는 데 사용됩니다.
•
예를 들어 파일 및 폴더는 계층적 트리 형태로 저장됩니다.
효율적인 검색 속도
•
효율적인 삽입, 삭제 및 검색을 위해 트리 구조를 사용합니다.
힙(Heap)
•
힙도 트리로 된 자료 구조입니다.
데이터 베이스 인덱싱
•
데이터베이스 인덱싱을 구현하는데 트리를 사용합니다.
•
예) B-Tree, B+Tree, AVL-Tree..
Trie
•
사전을 저장하는 데 사용되는 특별한 종류의 트리입니다.
트리 하드코딩 하기
인접행렬로 표현하는 경우
char value[5] = { 'D','E','F','Q','A' };
int matrix[5][5] =
{
0,1,1,1,0,
0,0,0,0,1,
0,0,0,0,0,
0,0,0,0,0,
0,0,0,0,0,
};
Python
복사
리스트로 표현 하는 경우
1차원 배열로 표현하는 경우
char map[256] = " ERWG RW K";
Python
복사
rootNode를 1번으로
왼쪽자식은 부모 index * 2
오른쪽 자식은 부모 index *2 + 1
자식노드 출력해보기
입력받은 노드 번호에 자식노드를 전부 출력해보자.
#include<iostream>
int main()
{
char value[10] = "DEFQZVM";
int map[7][7] =
{
0,1,1,1,0,0,0,
0,0,0,0,1,0,0,
0,0,0,0,0,0,0,
0,0,0,0,0,1,1,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
};
int n = 0;
std::cin >> n;
for (size_t i = 0; i < 7; i++)
{
if (map[n][i] > 0)
{
std::cout << value[i] << std::endl;
}
}
return 0;
}
Python
복사
부모 노드 출력 해보기
#include<iostream>
int main()
{
char map[15] = " ERWG RW K ";
int n = 0;
std::cin >> n;
std::cout << map[n / 2] << std::endl;
return 0;
}
Python
복사
그래프와 트리를 순회하기 위해서는 반복문이 아닌 특정 알고리즘이 필요하다..
DFS
재귀호출,스택을 사용하여 노드를 탐색한다. Depth First Search(깊이 우선 탐색)
노드를 깊숙히 안쪽으로 들어가면서 탐색한다.
트리,그래프 둘다 연습해야한다.
BFS
큐를 이용하여 , 노드를 탐색한다. Breadth First Search(너비 우선 탐색)
노드의 레벨 또는 너비를 우선적으로 탐색한다.
트리,그래프 둘다 연습해야한다.
트리냐 그래프냐에 따라서 큰 순회방법은 비슷하지만
특정조건이 들어갈수 있기때문에 구현방법이 달라질수 있다.
Plain Text
복사
트리 순회 (dfs)
char value[6] = "TBECD";
char path[6] = "";
int map[5][5] =
{
0,1,1,0,0,
0,0,0,1,1,
0,0,0,0,0,
0,0,0,0,0,
0,0,0,0,0,
};
void run(int now, int level)
{
std::cout << value[now];
for (size_t i = 0; i < 5; i++)
{
if (map[now][i] == 1)
{
path[level + 1] = value[i];
run(i, level + 1);
path[level + 1] = 0;
}
}
}
int main()
{
path[0] = 'T';
run(0, 0);
return 0;
}
C++
복사
2진트리의 경우 1차원배열로도 표현 가능하다.
왼쪽 자식과 오른쪽 자식의 번호가 규칙성이 있어 이를 배열의 인덱스로 활용이 가능하다.
위 같은 트리를 인덱스를 사용해 재귀함수 활용이 가능하다.
char map1D[7] = " TBECD";
void run1D(int now)
{
if (now >= 7 || map1D[now] == ' ')
{
return;
}
std::cout << map1D[now];
run1D(now * 2);
run1D(now * 2 + 1);
}
int main()
{
run1D(1);
return 0;
}
C++
복사
그래프 순회 (dfs)
그래프 순회는 트리순회에서 중복 방문 여부만 체크해주면 된다.
#include <iostream>
char value[6] = "TEQWA";
char path[6] = "";
int visited[5] = {};
int map[5][5] =
{
0,1,0,0,0,
0,0,1,1,0,
0,0,0,0,0,
1,0,0,0,1,
0,0,0,0,0,
};
void run(int now, int level)
{
std::cout << value[now];
for (size_t i = 0; i < 5; i++)
{
if (map[now][i] == 1
&& visited[i] == 0)
{
path[level + 1] = value[i];
visited[i] = 1;
run(i, level + 1);
path[level + 1] = 0;
}
}
}
int main()
{
path[0] = 'T';
visited[0] = 1;
run(0, 0);
return 0;
}
C++
복사
“강의는 많은데, 왜 나는 아직도 코드를 못 짤까?”
혼자 공부하다 보면 누구나 이런 고민을 하게 됩니다.
•
강의는 다 들었지만 막상 손이 안 움직이고,
•
복습을 하려 해도 무엇을 다시 봐야 할지 모르겠고,
•
질문할 곳도 없고,
•
유튜브는 결국 정답을 따라 치는 것밖에 안 되는 것 같고.
문제는 ‘연습’이 빠졌기 때문입니다.
단순히 강의를 듣는 것만으로는 실력이 늘지 않습니다.
실제 문제를 풀고, 고민하고, 직접 구현해보는 시간이 반드시 필요합니다.
그래서, 얌얌코딩 코칭은 다릅니다.
그냥 가르치지 않습니다.
스스로 설계하고, 코딩할 수 있게 만듭니다.
얌얌코딩 코칭에서는 단순한 예제가 아닌,
스스로 문제를 분석하고 구현해야 하는 연습문제를 제공합니다.
이 연습문제들은 다음과 같은 역량을 키우기 위해 설계되어 있습니다:
•
문제를 스스로 쪼개고 설계하는 힘
•
다양한 조건을 만족시키는 실제 구현 능력
•
기능 단위가 아닌, 프로그램 단위로 사고하는 습관
•
마침내 자신의 힘으로 코드를 끝까지 작성하는 경험
지금 필요한 건 더 많은 강의가 아닙니다.
코드를 스스로 완성해 나가는 훈련,
그것이 지금 실력을 끌어올릴 가장 현실적인 방법입니다.
자세한 안내 보기: 프리미엄 코칭 안내 바로가기 또는 카카오톡 상담방: 얌얌코딩 상담방