tree
Q&A 정리: tree
Tree 자료구조를 사용하는 이유는?
정보가 자연스럽게 계층 구조를 이루는 경우에 트리를 사용한다. 회사의 조직도나 컴퓨터의 폴더 구조처럼 상위-하위 관계가 있는 데이터를 표현하기에 적합하다.
One reason to use trees might be because you want to store information that naturally forms a hierarchy.
Tree의 DFS 순회 방법은?
DFS(깊이 우선 탐색)는 한 갈래를 끝까지 파고든 뒤 되돌아오는 방식이다. 미로에서 한 길을 막다른 곳까지 가본 뒤 갈림길로 돌아와 다른 길을 탐색하는 것과 같다. 방문 순서에 따라 In-Order, Pre-Order, Post-Order로 나뉜다.
Explore one branch fully before backtracking.
- In-Order (LNR): Left → Node → Right (retrieves BST elements in sorted order).
- Pre-Order (NLR): Node → Left → Right (used for tree reconstruction).
- Post-Order (LRN): Left → Right → Node (helps in deleting or evaluating expressions).
Tree의 BFS 순회 방법은?
BFS(너비 우선 탐색)는 같은 층의 노드를 모두 방문한 뒤 다음 층으로 내려가는 방식이다. 건물의 각 층을 순서대로 둘러보는 것과 같다. 최단 경로를 찾는 알고리즘에 활용된다.
Visit nodes level by level.
- Level-Order: Processes nodes from top to bottom (used in shortest path algorithms).
- Zig-Zag Traversal: Alternates left-to-right and right-to-left at each level (used in hierarchical structures).
Tree의 기본 용어는?
트리의 기본 용어를 가족 관계에 비유하면 이해하기 쉽다. Leaf는 자식이 없는 끝 노드, Ancestor는 위쪽 조상 노드, Sibling은 같은 부모를 둔 형제 노드, Edge는 노드 사이를 잇는 연결선이다.
- Leaf Node (External Node): The nodes which do not have any child nodes are called leaf nodes.
- Ancestor of a Node: Any predecessor nodes on the path of the root to that node are called Ancestors of that node.
- Neighbour of a Node: Parent or child nodes of that node are called neighbors of that node.
- Sibling: Children of the same parent node are called siblings.
- Internal Node: A node with at least one child is called Internal Node.
- Subtree: Any node of the tree along with its descendant.
- Edge: A connection between two nodes.