[Seoul National Univ: Data Science] Lecture 6. Trees

본 포스팅은 서울대학교 이준석 교수님의 M2480.001100 Principles & Applications of Data Science을 수강하고 공부한 내용을 정리하기 위한 포스팅입니다.

 

https://youtu.be/SSLNiP438OA?si=EN1kEtPXvAqPP2pp

 

 

1. Binary Tree

 각 노드가 최대 2개의 자식만 갖는 트리를 의미한다.

 

• Root: 가장 위의 노드
• Parent / Child: 부모 / 자식 노드
• Sibling: 형제 노드(같은 부모)
• External node (Leaf) : 자식이 없는 노드
• Internal node: 자식이 1개 이상 있는 노드
• Subtree: 어떤 노드를 루트로 하는 작은 트리

 

Traversal 

 

 

1) Preorder (Root → Left → Right)

1. 현재 노드 방문
2. 왼쪽 서브트리 순회
3. 오른쪽 서브트리 순회

재귀 의사코드 & C++코드

Algorithm preorder(v)
    visit(v)
    if isExternal(v) preorder(left(v))
    if isExternal(v) preorder(right(v))
    
void preorder(Node* v, NodePtrList& pl) const {
    pl.push_back(v);
    if (v->lChild != NULL) preorder(v->lChild, pl);
    if (v->rChild != NULL) preorder(v->rChild, pl);
}

 

2) Inorder (Left → Root → Right)

1. 왼쪽 서브트리 순회
2. 현재 노드 방문
3. 오른쪽 서브트리 순회

** Binary Search Tree (BST) **에서 Inorder 순회를 하면 key 값이 오름차순으로 나오게 된다.

 

재귀 의사코드 & C++코드

Algorithm Inorder(v)
    if isExternal(v) Inorder(left(v))
    visit(v)
    if isExternal(v) Inorder(right(v))
    
void inorder(Node* v, NodePtrList& pl) const {
    if (v->lChild != NULL) inorder(v->lChild, pl);
    pl.push_back(v);
    if (v->rChild != NULL) inorder(v->rChild, pl);
}

 

3) Postorder (Left → Right → Root)

1. 왼쪽 서브트리 순회
2. 현재 노드 방문
3. 오른쪽 서브트리 순회

재귀 의사코드 & C++코드

Algorithm Postorder(v)
    if isExternal(v) Postorder(left(v))
    if isExternal(v) Postrder(right(v))
    visit(v)
    
void postorder(Node* v, NodePtrList& pl) const {
    if (v->lChild != NULL) postorder(v->lChild, pl);
    if (v->rChild != NULL) postrder(v->rChild, pl);
    pl.push_back(v);
}

 

         A
       /   \
      B     C
     / \     \
    D   E     F
       / \
      G   H

 

• Preorder : A → B → D → E → G →  H → C → F
• Inorder : D  → B → G → E → H → A → C → F 
• Postorder: D → G → H → E → B→ F→ C → A

 

 

2. Proper Binary Tree

 각 내부 노드가 자식을 0개 또는 2개만 가지는 Binary Tree를 의미한다.

    A
   / \
  B   C
     / \
    D   E

• External node (Leaf) → 자식 0개
• Internal node → 자식 2개

 

Properties of Proper Binary Trees

Notation

• i = 내부 노드 개수
• e = 리프(외부 노드) 개수
• n = 전체 노드 수 (n = i + e)
• h = 트리 높이 (root 깊이 0 기준)

Properties

• h <= (n - 1) / 2
• h >= log2(n + 1) - 1

 

3. Binary Search Tree (BST)

  Binary Search Tree (BST)는 Binary Tree + Sort가 합쳐져 있는 Tree이다. 각 노드에 key 값이 있다고 할 때, 모든 노드에 대해 항상 아래 조건을 만족해야 한다.

        50
      /    \
    30      70
   /  \    /  \
 20   40  60  80

 

• 왼쪽 서브트리의 모든 key < 현재 노드의 key
• 오른쪽 서브트리의 모든 key > 현재 노드의 key

 

 

 

1) Retrieval

• Preorder
• Inorder: 항상 오름차순으로 정렬된 순서로 key들이 반환된다.
• Postorder

 

2) Search

값 x를 찾고 싶으면:

1. 현재 노드 key가 x면 → 성공
2. x < key → 왼쪽 자식으로 이동
3. x > key → 오른쪽 자식으로 이동
4. NULL까지 갔는데 못 찾으면 → 없음

Balanced BST면 h ≈ log n → O(log n)

Unbalanced BST면 h ≈ n-1 → O(N)

 트리의 균형이 잘 잡혀져 있다면 Height ≈ O(log n)에 근사한다. 따라서 대부분의 연산이 O(log n)에 끝나게 된다. 하지만 트리의 균형이 망가져 연결리스트의 형태에 가까워지게 되면 Height ≈  n -1에 근사한다. 따라서 O(N)이 된다. 

 

재귀 의사코드

Algorithm TreeSearch(k, v)
    if v.isExternal()
        return v
    if k < v.key()
        return TreeSearch(k, v.left())
    else if k == v.key()
        return v
    else
        return TreeSearch(k, v.right())

 

 

3) Insertion

[Case 1] key == item: 이미 key가 존재하는 경우

[Case 2] key < item: key가 item보다 더 작으므로 왼쪽 subtree로 이동

[Case 3] key > item: key가 item보다 더 크므로 오른쪽 subtree로 이동

• O(h) ≈ O(log n)

 

→ [Case 2 & 3]의 경우에는 마지막 leaf에 도달할 때까지 반복된다. 도달하게 되면 해당 지점에 새로운 노드를 삽입한다.

 

4) Deletion

 

[Case 1] 자식이 0개인 경우: 해당 노드 포인터를 끊으면 된다.

• O(h) ≈ O(log n)

[Case 2] 자식이 1개인 경우: 부모 노드와 자식을 연결시킨다.

• O(h) ≈ O(log n)

[Case 3] 자식이 2개인 경우:

• 해당하는 노드를 먼저 삭제하다.
• 삭제한 노드의 오른쪽 서브트리에서 가장 작은 노드를 찾는다. (가장 왼쪽 노드를 찾으면 된다.)
• 그 값으로 현재 노드의 key를 바꾸고, 원래 있던 위치의 노드를 삭제한다.
• O(h) ≈ O(log n)

 

 

 아래 슬라이드는 같은 값들의 구성이라도, 삽입 순서에 따라 BST 모양이 완전히 달라지는 것을 보여준다. 즉, BST의 모양은 어떤 순서로 삽입했는지에 의해 결정된다. 

 

 

 따라서 Tree가 균형잡히도록 만들어주는 것이 중요한데, 이러한 방법으로 AVL Tree 혹은 Red-Black Tree 같은 self-balancing BST를 사용한다. 두 방법 모두 높이를 O(log N)으로 유지하는것을 목표로 하는 BSTㅇ다.

 

 

Time Complexity

 

node = N, Height = H라고 하면

 

N 개의 데이터를 하나씩 BST에 삽입하는 경우

→ 한 번 삽입 시 O(log N)이므로, N번 반복하면 O(N log N)이 된다.

 

완성된 BST를 Inorder traversal 해서 값들을 출력하는 경우

→ 전체 노드를 한 번씩 거쳐야 하므로 O(N)이 된다.

 

만약 최악의 경우 (Linked List와 같은 형태인 경우)에는 삽입 과정이 O(N^2)이 된다.

4. Applications of Binary Search Tree

 

1. 두 이진 트리가 서로 대칭인지 검사하기

 

(1) 둘 다 NULL → true

(2) 한쪽만 NULL → false

(3) 값이 다르면 → false

(4) 값이 같으면

• a의 왼쪽 ↔ b의 오른쪽
• a의 오른쪽 ↔ b의 왼쪽

(5) 이 두 쌍이 모두 거울이면 true

 

2. Balanced Binary Tree인지 검사하기

 

// 높이를 리턴하다가, 중간에 불균형이면 -1을 리턴하는 헬퍼 함수
function checkHeight(node):
    if node == null:
        return 0          // 빈 트리의 높이 = 0

    leftH  = checkHeight(node.left)
    if leftH == -1:
        return -1         // 왼쪽 서브트리에서 이미 불균형 발견

    rightH = checkHeight(node.right)
    if rightH == -1:
        return -1         // 오른쪽 서브트리에서 이미 불균형 발견

    if abs(leftH - rightH) > 1:
        return -1         // 현재 노드에서 불균형

    return max(leftH, rightH) + 1   // 현재 노드의 높이


// 전체 트리가 균형인지 판별
function isBalanced(root):
    if checkHeight(root) == -1:
        return false
    else:
        return true

 

3. 정렬된 배열에서 균형 잡힌 BST 만들기

function buildBalancedBST(A, low, high):
    if low > high:
        return NULL

    mid = (low + high) / 2          // 정수 나눗셈

    node = new Node(A[mid])

    node.left  = buildBalancedBST(A, low, mid - 1)
    node.right = buildBalancedBST(A, mid + 1, high)

    return node

// 전체 트리 만들기
root = buildBalancedBST(A, 0, n-1)