트리
- 나무를 뒤집어 놓은 듯한 모양이라 하여 트리라는 이름이 생겼다.
특징
- 검정색 동그라미를 노드(node)라 하며, 데이터를 담는 공간이다. 노드와 노드를 이어주는 선을 엣지(edge)라 한다.
- 경로(path)란, 엣지로 연결된(인접한 노드들로 이뤄진) sequence를 가리킨다. 경로의 길이는 경로에 속한 엣지의 수를 나타낸다.
- 트리의 높이(height)는 루트 노드에서 리프 노드에 이르는 가장 긴 경로의 엣지 수이다. 특정 깊이를 가지는 노드의 집합을 레벨(level)이라고 부른다.
- 리프노드(leaf node) 는 자식이 없는 노드이다.
- internal node는 리프노드를 제외한 노드이다.
- 루트노드(root node)는 부모노드가 없는 노드이다.
- 루트노드를 제외한 모든 노드는 단 하나의 부모노드만을 가진다.
성질
- 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다.
- 회로(cycle)가 존재하지 않는다.
- 모든 노드는 서로 연결되어 있다.
- 엣지(edge)를 하나 자르면 트리가 두 개로 분리된다.
- 엣지(edge)의 수 는 노드의 수 - 1 이다
이진 트리
- 자식 노드가 최대 두 개인노드들로 구성된 트리.
- 정이진트리(full binary tree) : 모든 레벨에서 노드들이 꽉 채워진 이진트리(리프노드를 제외한 모든 노드가 자식노드를 2개 가짐)
- 완전이진트리(complete binary tree) : 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리
- 균형이진트리(balanced binary tree) : 모든 리프노드의 깊이 차이가 많아야 1인 트리
순회
- 트리순회(tree traversal)이란, 트리의 모든 노드를 하나도 빠뜨리지 않고 정확히 한 번만 중복없이 방문하기 위한 과정이다. 트리 순회는 노드를 방문하는 순서에 따라 전위순회(preorder), 중위순회(inorder), 후위순회(postorder) 세 가지로 나뉜다.
전위순회(preorder)
- 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 방문. 깊이우선순회(depth-first traversal)라고도 한다.
중위순회(inorder)
- 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순서로 방문. 대칭순회(symmentric traversal)라고도 한다.
후위순회(postorder)
- 왼쪽 서브트리 -> 오른쪽 서브트리 -> 노드 순서로 방문.
참고
Security & Develop