[WEEK03] 트리, BFS, DFS, 이진 탐색 트리

트리 (Tree)

• 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)
• DAG (Directed Acyclic Graph, 방향성이 있는 비순환 그래프)

 

용어 정리

• 노드 (Node) / 가지 (Edge)
• 루트 (Root) : 트리의 가장 위쪽에 있는 노드, 트리에 하나만 존재
• 리프 (Leaf) : 가장 아래쪽에 있는 노드 = terminal node = external node
• 비단말노드 (Non-terminal node) : 리프를 제외한 노드 = internal node
• 자식 (Child) : 어떤 노드와 아래쪽 가지로 연결된 노드, 리프는 자식을 갖지 않음
• 부모 (Parent) : 어떤 노드와 위쪽 가지로 연결된 노드, 어떤 노드의 부모는 하나뿐. 루트는 부모를 갖지 않음
• 형제 (Sibling) : 부모가 같은 노드
• 조상 (Ancestor) : 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드
• 자손 (Descendant) : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드
• 레벨 (Level) : 루트에서 얼마나 멀리 떨어져있는지를 나타냄. 루트의 레벨은 0
• 차수 (Degree) : 각 노드가 갖는 자식의 수
• n진 트리: 모든 노드의 차수가 n 이하인 트리
  • 이진 트리 (binary tree) : 모든 노드의 차수가 2 이하인 트리
• 높이 (Height) : 루트에서 가장 멀리 있는 리프까지의 거리 = 리프 레벨의 최대값
• 서브트리 (Subtree) : 어떤 노드를 루트로 하고, 그 자손으로 구성된 트리
• 빈 트리 (None tree) : 노드와 가지가 전혀 없는 트리 = null tree
• 순서 트리 (Ordered tree) : 형제 노드와 순서 관계가 있는 트리
• 무순서 트리 (Unordered tree) : 순서를 구별하지 않는 트리

 

순서 트리의 검색

BFS (Breadth-First Search)

= 너비 우선 검색 = 폭 우선 검색 = 가로 검색 = 수평 검색

• 낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법
• 탐색 순서 : 0 → 1 → 2 → 3 → 4 → 5 → 6

DFS (Depth-First Search)

= 깊이 우선 검색 = 세로 검색 = 수직 검색

• 리프에 도달할 때까지 아래쪽으로 내려가면서 검색
• 리프에 도달해서 더이상 검색할 곳이 없으면 일단 부모 노드로 돌아가서 다시 자식 노드로 내려감
• 탐색 순서 : 0 → 1 → 3 → 4 → 2 → 5 → 6

• 트리 순회
  • 아래 트리에서, DFS 수행 중 노드 A를 총 3번 지나감
    1. A에서 B 내려가기 전
    2. B에서 C 내려가기 전
    3. C에서 A 돌아올 때
  • 각 노드를 최대 3번 지나가게 되는데, 어느 시점에 ‘실제로 방문’ 하는지에 따라 세 종류의 스캔 방법으로 구분함 - 전위 순회 (Preorder), 중위 순회 (Inorder), 후위 순회 (Postorder)

• 전위 순회 (Preorder)
  • 노드 방문 → 왼쪽 자식 → 오른쪽 자식
  • A → B → D → H → E → I → J → C → F → K → L → G
• 중위 순회 (Inorder)
  • 왼쪽 자식 → 노드 방문 → 오른쪽 자식
  • H → D → B → I → E → J → A → K → F → L → C → G
• 후위 순회 (Postorder)
  • 왼쪽 자식 → 오른쪽 자식 → 노드 방문
  • H → D → I → J → E → B → K → L → F → G → C → A

 

이진 탐색 트리 (Binary Search Tree)

 

이진 트리(Binary Tree)

• 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리
• Left subtree : 왼쪽 자식을 루트로 하는 서브트리
• Right subtree: 오른쪽 자식을 루트로 하는 서브트리

완전 이진 트리 (Complete Binary Tree)

• 마지막 레벨을 제외하고 모든 레벨에 노드가 가득 차있다
• 마지막 레벨의 노드들은 왼쪽부터 오른쪽으로 채워져 있음
• 높이가 k인 완전 이진 트리가 가질 수 있는 노드의 수는 최대 2^(k+1) - 1개
• N개의 노드를 저장할 수 있는 완전 이진 트리의 높이(h)는 logN

 

이진 탐색 트리 (Binary Search Tree)

• 모든 노드가 다음 조건을 만족해야 함
  • 왼쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작아야 한다.
  • 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 커야 한다.

• 특징
  • 구조가 단순함
  • DFS inorder 방식으로 순회하면 노드값을 오름차순으로 얻을 수 있음
  • 빠른 탐색 속도 : 평균 시간복잡도 O(logN)
  • 노드의 insertion/deletion 이 빠르다 : 평균 시간복잡도 O(logN)
  • 그러나 최악의 경우 insert/delete/search 의 시간 복잡도가 O(N)이 될 수 있음
  • ex. 키의 오름차순으로 노드가 삽입되는 경우 트리의 높이가 깊어짐 O(h) = O(N)
• 균형 탐색 트리 (Self-Balancing Search Tree) : 높이를 O(logN)으로 제한하여 연산의 시간 복잡도를 O(logN)으로 보장함
  • AVL tree, red- black tree : BST
  • B tree, 2-3 tree : non-BST