Tree, Traversal, Binary Search Tree

Tree

• 정의 : '노드'와 '간선'으로 구성 된 자료구조로, 그래프의 한 종류이다.

 

용어

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

 

트리 종류

• Binary Tree (이진 트리) : 각 노드가 최대 두 개의 자식을 갖는 트리 

• Complete Binary Tree (완전이진트리) : 트리의 마지막 레벨을 제외한 모든 레벨이 채워져있고, 마지막 레벨은 왼쪽에서 오른쪽으로 채워진 트리
• Full binary Tree (전이진트리) : 모든 노드가 0개 또는 2개의 자식을 갖는 트리
• Perfect Binary Tree (포화이진트리) : 트리의 모든 레벨이 꽉찬 이진트리. 완전이진트리이자 전이진트리

• Binary Search Tree (이진탐색트리) : 왼쪽 자식 <= 부모 <= 오른쪽 자식 을 만족하는 이진트리
• Balanced Tree (균형트리) : AVL tree, red-black tree
• Binary Heap (이진 힙) : min heap, max heap

 

Traversal, 순회

• pre-order (전위 순회) : 부모노드 -> 왼쪽자식노드 -> 오른쪽자식노드
• in-order (중위 순회) : 왼쪽자식노드 -> 부모노드 -> 오른쪽자식노드
• post-order (후위 순회) : 왼쪽자식노드 -> 오른쪽자식노드 -> 부모노드