[Algorithm] Tree

트리 (Tree)

• 그래프 자료구조 중 하나
  • 그래프와 트리의 차이점
    1. 싸이클 존재 여부 : 트리는 싸이클이 없다!
    2. 루트 노드가 반드시 하나
    3. 부모 노드가 반드시 하나
  • 트리는 일반적인 경우, 암묵적으로 방향 표기x (단방향)
• 비선형 구조 : 원소들 간에 1 : n 관계
• 원소들 간에 계층관계를 가지는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조

 

용어 정리

• 트리 : 한 개 이상의 노드로 이루어진 유한 집합
• 부 트리 (subtree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리, 최상위 노드를 제외한 나머지 노드들은 분리집합으로 분리가능 -> 이는 각각 하나의 트리가 되며 (재귀적 정의) 루트의 부 트리
• 노드 (node) : 트리의 원소 (A, B, C, D, E, F, G, H, I, J K)
  • 루트 노드 (root node) : 트리의 시작 노드 (최상위 노드) (A)
  • 단말 노드 (리프 노드) : 차수가 0인 노드, 자식 노드가 없는 노드
  • 형제 노드 (sibling node) : 같은 부모 노드의 자식 노드들 (B, C, D)
  • 조상 노드 : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 (K의 조상 노드 : F, B, A)
  • 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들 (B의 자손 노드 : E, F, K)
• 간선 (edge) : 노드를 연결하는 선, 부모 노드와 자식 노드를 연결

• 차수 (degree)
  • 노드의 차수 : 노드에 연결된 자식 노드의 수 (B의 차수 : 2)
  • 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값 (트리 T의 차수 : 3)
• 높이 (height)
  • 노드의 높이 : 루트에서 노드에 이르는 간선의 수, 노드의 레벨 (B의 높이 : 1, F의 높이 : 2)
  • 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨 (트리 T의 높이 : 3)
  • 높이는 0부터 시작하기도 하고 1부터 시작하기도 함

 

이진 트리

• 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리
• 각 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리
  • 왼쪽 자식 노드 (left child node)
  • 오른쪽 자식 노드 (right child node)

• 레벨 i 에서의 노드의 최대 개수는 2^i개
• 높이 h 인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1), 최대 개수는 (2^(h+1) -1)

 

포화 이진 트리 (Full Binary Tree)

• 모든 레벨에 노드가 포화상태로 차있는 이진 트리
• 높이가 h일 때, 최대 노드 개수인 (2^(h+1) -1)의 노드를 가진 이진 트리
• 루트를 1번으로 하여 (2^(h+1) -1)까지 정해진 위치에 대한 노드 번호를 가짐

 

완전 이진 트리 (Complete Binary Tree)

• 높이가 h이고 노드 수가 n개일 때 (단, h+1 <= n < 2^(h+1) -1), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈자리가 없는 이진 트리

 

편향 이진 트리 (Skewed Binary Tree)

• 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리
  • 왼쪽 편향 이진 트리, 오른쪽 편향 이진 트리

 

순회 (traversal)

• 트리의 각 노드를 중복되지 않게 전부 방문하는 것, 트리의 노드들을 체계적으로 방문하는 것
• 전위순회 (preorder traversal) : VLR, 부모 노드 방문 후, 자식 노드를 좌/우 순서로 방문
• 중위순회(inorder traversal) : LVR, 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드 순으로 방문
• 후위순회 (postorder traversal) : LRV, 자식노드를 좌/우 순서로 방문한 후, 부모 노드 방문

 

전위 순회 (preorder traversal)

• 수행 방법
  • 현재 노드 n을 방문하여 처리 -> V
  • 현재 노드 n의 왼쪽 서브트리로 이동 -> L
  • 현재 노드 n의 오른쪽 서브트리로 이동 -> R

def preorder_travers(T):
    if T:
        visited[T] = 1
        preorder_traverse(T.left)
        preorder_traverse(T.right)

 

중위 순회 (inorder traversal)

• 수행 방법
  • 현재 노드 n의 왼쪽 서브트리로 이동 -> L
  • 현재 노드 n을 방문하여 처리 -> V
  • 현재 노드 n의 오른쪽 서브트리로 이동 -> R

def inorder_traverse(T):
    if T:
        inorder_traverse(T.left)
        visited[T] = 1
        inorder_traverse(T.right)

 

후위 순회 (postorder traversal)

• 수행 방법
  • 현재 노드 n의 왼쪽 서브트리로 이동 -> L
  • 현재 노드 n의 오른쪽 서브트리로 이동 -> R
  • 현재 노드 n을 방문하여 처리 -> V

def postorder_traverse(T):
    if T:
        postorder_traverse(T.left)
        postorder_traverse(T.right)
        visited[T] = 1

 

이진 트리의 순회 - 배열을 이용한 이진 트리의 표현

• 이진 트리에 각 노드 번호를 부여 (루트의 번호 1, 왼쪽부터 오른쪽으로 2^n부터 2^(n+1) -1까지 번호 부여)
• 노드 번호의 성질
  • 노드 번호가 i 인 노드의 부모 노드 번호 : i/2
  • 노드 번호가 i 인 노드의 왼쪽 자식 노드 번호 : 2*i
  • 노드 번호가 i 인 노드의 오른쪽 자식 노드 번호 : 2*i + 1
• 노드 번호를 배열의 인덱스로 사용

• 배열을 이용한 이진 트리의 표현의 단점
  • 편향 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생
    
  • 트리의 중간에 새로운 노드를 삽입하거나 기존의 노드를 삭제할 경우 배열의 크기 변경 어려워 비효율적
  • 이를 보완하기 위해 연결리스트를 이용하여 트리를 표현할 수 있음
    • 연결 자료구조를 이용한 이진트리의 표현
      : 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로 일정한 구조의 단순 연결 리스트 노드를 사용하여 구현
    

 

이진 탐색 트리

• 탐색작업을 효율적으로 하기 위한 자료구조
• 모든 원소는 서로 다른 유일한 키를 가짐
• key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)
  

  

• 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리임
• 중위 순회하면 오름차순 정렬된 값을 얻을 수 있음

 

탐색 연산

• 루트에서 시작
• 탐색할 키 값 x를 루트 노드의 키 값과 비교
  • x = 루트 노드 : 원하는 원소를 찾았으므로 탐색연산 성공
  • x < 루트 노드 : 루트노드의 왼쪽 서브트리에 대해 탐색연산 수행
  • x > 루트 노드 : 루트노드의 오른쪽 서브트리에 대해 탐색연산 수행
• 서브트리에 대해서 순환적으로 탐색 연산 반복

 

삽입 연산

1. 먼저 탐색 연산 수행
   • 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인
   • 탐색에서 탐색 실패가 결정되는 위치가 삽입 위치가 됨
2. 탐색 실패한 위치에 원소를 삽입

 

연산의 성능

• 탐색 (searching), 삽입 (insertion), 삭제 (deletion) 시간은 트리의 높이만큼 시간이 걸림
  • O(h), h : BST의 깊이(height)
• 평균의 경우 : 이진 트리가 균형적으로 생성되어 있는 경우
  • O(log n)
• 최악의 경우 : 한 쪽으로 치우친 경사 이진트리의 경우
  • O(n)
  • 순차탐색과 시간복잡도가 같음

 

+) 검색 알고리즘의 비교

• 배열에서의 순차 검색 : O(N)
• 정렬된 배열에서 순차 검색 : O(N)
• 정렬된 배열에서의 이진 탐색 : O(logN)
  • 고정 배열 크기와 삽입, 삭제 시 추가 연산 필요
• 이진 탐색 트리에서의 평균 : O(logN)
  • 최악의 경우 : O(N)
  • 완전 이진 트리 또는 균형 크리로 바꿀 수 있다면 최악의 경우를 없앨 수 있음
    • 새로운 원소를 삽입할 때 삽입 시간을 줄임
    • 평균과 최악의 시간이 같음 O(logn)
• 해쉬 검색 : O(1)
  • 추가 저장 공간이 필요