Tree

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

관련 용어

트리의 활용

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

트리의 순회

Tree Traversal

트리를 조회하는 방식

전위 순회(Preorder)

• 깊이 우선 순회(DFT, Depth-First Traversal) 라고도 하며, 주로 트리를 복사하거나 전위표기법을 구하는데 사용한다.[1]
• 복사할 때 사용하는 이유는 트리의 노드부터 복사해야하기 때문이다.
• 다음과 같은 방법으로 진행한다.
  1. 노드를 방문한다.
  2. 왼쪽 서브 트리를 전위 순회한다.
  3. 오른쪽 서브 트리를 전위 순회한다.

중위 순회(Inorder)

• 대칭 순회(symmetric) 라고도 하며, 이진 탐색 트리(BST, Binary Search Tree) 에서 값을 가져올 때 주로 사용한다.
• 다음과 같은 방법으로 진행한다.
  1. 왼쪽 서브 트리를 중위 순회한다.
  2. 노드를 방문한다.
  3. 오른쪽 서브 트리를 중위 순회한다.

후위 순회(Postorder)

• 값을 삭제할 때 주로 사용한다. 그 이유는 루트 노드를 지우기 전에 하위 노드를 먼저 지워야하기 때문이다.
• 다음과 같은 방법으로 진행한다.
  1. 왼쪽 서브 트리를 후위 순회한다.
  2. 오른쪽 서브 트리를 후위 순회한다.
  3. 노드를 방문한다.

레벨 순서 순회(level-order)

• 너비 우선 순회(breadth-first traversal) 라고도 한다.
• 모든 노드를 낮은 레벨부터 차례대로 순회한다.

이진 트리

Binary Tree