트리

Tree

Root를 중심으로 하위 노드들을 가지며 가지처럼 뻗어나가는 비선형, 비순환 구조

관련 용어

용어	의미
차수(degree)	노드의 부족 트리의 개수 트리 전체의 차수: 트리에 속한 최대 차수
단말 노드(leaf, terminal)	차수가 0인, 가장 끝의 노드
내부 노드(internal)	차수가 1 이상인, 단말이 아닌 노드
부모(parent)	바로 상위 노드
자식(child)	바로 하위 노드
형제(sibling)	부모가 같은 노드
조상(ancestor)	상위 노드, 부모 노드들의 집합
자손(descendant)	하위 노드, 자식 노드들의 집합
레벨(level)	상위 노드를 기준으로 한 깊이
깊이(depth)	트리에 속한 최대 레벨

트리의 활용

• 검색: log(n)의 효율
• 인덱스: B 트리, AVL 트리, T 트리 등
• 정렬: Heap 구조 이용

트리의 순회

Tree Traversal

트리를 조회하는 방식

• 전위(Preorder)
• 중위(Inorder)
• 후위(Postorder)

이진 트리

Binary Tree