자료구조
Tree : 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
Tree는 비선형 구조, 계층적으로 표현되고 아래로만 뻗어나가기 때문에 사이클이 없음
용어정리
• 노드(Node) : 트리 구조를 이루는 모든 개별 테이터
• 루트(Root) : 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent node) : 두 노드가 상하 관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child node) : 두 노드가 상하 관계로 연결되어 있을 떄 상대적으로 루트에서 먼 노드
• 리프(Leaf) : 트리 구조의 끝지점이고, 자식 노드가 없는 노드
깊이(Depth)
트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있음
루트 A의 depth는 0, B,C의 depth는 1
레벨(Level)
트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현 가능
루트 A의 level은 1, B,C의 level은 2
같은 레벨에 나란히 있는 노드를 형제노드라 부름
높이(Height)
트리 구조에서 리프 노드를 기준으로 루트까지의 높이를 표현할 수 있음
각 리프의 높이를 0, B와 C의 높이는 2
서브 트리(Sub tree)
트리 구조에서 루트에서 뻗어 나오는 큰 트리의 내부에 트리 구조를 갖춘 작은 트리
트리의 실사용 예제 : 파일 탐색기
Binary Search Tree
| 이진 트리 종류 | 영어 표기 | 설명 |
|---|---|---|
| 정 이진 트리 | Full binary tree | 각 노드가 0개 혹은 2개의 자식노드를 가짐 |
| 포화 이진 트리 | Perfect binary tree | 정 이진 트리이면서 완전 이진 트리인 경우, 노드의 레벨이 동일, 모든 레벨이 가득 채워져있음 |
| 완전 이진 트리 | Complete binary tree | 마지막 레벨을 제외한 노드가 가득차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 함 |
Tree traversal(트리 순회)
특정 목적을 위해 트리의 노드를 한번씩 방문하는 것, 트리 구조는 계층적 구조라는 특징을 가지기 때문에 모든 노드를 순회하는 방법엔 크게 3가지가 있음
-
전위 순회 : 가장 먼저 방문할 노드는 루트, 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽 노드의 탐색이 끝나면 오른쪽 노드를 탐색함
-
중위 순회 : 제일 왼쪽 끝에 있는 노드부터 순회, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색
-
후위 순회 : 루트를 가장 마지막에 순회, 제일 왼쪽 끝에 있는 노드부터 순회하기 시작, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문
BFS / DFS
그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한번씩 방문(탐색)하는 것이 목적
그래프를 탐색하는 방법에도 여러가지가 있지만 가장 대표적인 두가지 방법은 BFS, DFS
BFS(Breadth-First Search) : 너비를 우선적으로 탐색하는 방법, 주록 두 정점 사이의 최단 경로를 찾을 때 사용
DFS(Depth-First Search) : 깊이를 우선적으로 탐색하는 방법, 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용 (탐색시간은 오래걸리지만 모든 노드를 탐색 가능)
여담 : 자료구조 너무 어려워ㅓㅓ....
.jpeg)