📌 Questions

1. BST와 Binary Tree에 대해서 설명하세요. (N사 전화면접)
2. Tree가 무엇인가?
3. 이진검색트리에서 검색속도가 가장 느린케이스는 데이터가 어떻게 저장되어 있는 경우인가?
4. 최소 스패닝 트리(Minimum Spanning Tree)에 대해서 설명해주세요.
5. AVL 트리란?

Tree의 개념

: 비선형 구조로, 원소들 간에 1:n 관계를 가지는 자료구조

💡 데이터를 어떻게 삽입하고 삭제할 것인지에 대해 관심이 많았던 선형 자료구조에 비해 비선형 자료구조는 데이터의 삽입/삭제보다는 ‘표현’에 포커스가 맞춰져있다.
트리를 이용해서 무엇인가를 저장하고 꺼내기 보다 트리는 ‘무엇인가를 표현하는 도구’로 자주 사용되기 때문이다.

드디어 큐를 마지막으로 선형(linear)자료구조 내용이 마무리되고 이제부터는 비선형 자료구조에 대한 내용이 시작된다. 비선형 자료구조의 대표적인 자료구조는 바로 트리(Tree)자료구조다.

가계도나 조직도 등 선형 자료구조로 계층형 구조를 표현하기 어려울 때가 있다. 계층형 구조를 가진 문제를 해결하기 위한 자료구조 형태가 트리이다.

Tree 구성요소

• Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
• Root Node : 트리 맨 위에 있는 노드
• Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 = 부모노드
• Child Node : 어떤 노드의 상위 레벨에 연결된 노드 = 자식노드
• Ancestor node : 어떤 노드보다 위(루트쪽)에 위치한 노드(연결되 있어야 됨) -> 10,5는 6의 조상노드 / 15는 6의 조상노드가 아님.
• descendant node : 조상노드의 역 -> H는 F,G,I의 후손노드.
• Sibling (Brother Node) : 동일한 Parent Node를 가진 노드. = 형제노드
• Leaf Node (Terminal Node) : Child Node가 하나도 없는 노드. = 단말노드
• Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Depth : 트리에서 Node가 가질 수 있는 최대 Level
• Sub Tree : 어떤 노드를 루트로 하고 그 자손으로 구성된 트리
• Null Tree : 노드와 가지가 전혀 없는 트리, 널 트리라고도 함

Tree의 특징

• 그래프의 한 종류이다. ‘최소 연결 트리’ 라고도 불린다.
• 트리는 계층 모델이다.
• 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류이다.
• Loop나 Circuit이 없다. 당연히 Self-loop도 없다.
• 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.
• 루트에서 어떤 노드로 가는 경로는 유일하다.
• 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
• 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS안에 있다.
• 트리의 종류
  • 이진트리
  • 스레드 이진 트리
  • 최소 신장 트리
  • 이진탐색트리
  • 균형트리 (AVL Tree, Red Black Tree)
  • 이진 힙

Binary Tree

: 프로그래밍에서 가장 많이 쓰이는 트리

• 이진 트리는 모든 노드들이 두 개의 서브 트리를 갖는 특별한 형태의 트리이다.
• 각 노드가 자식 노드를 최대 두 개까지만 가질 수 있기 때문에 각 노드의 자식 노드를 왼쪽 자식 노드, 오른쪽 자식 노드라고 한다.

Binary Tree의 특징

• 레벨 i 에서의 노드의 최대 개수 : 2ⁱ개

• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수 : (h+1)개

                                                                        최대 개수 : **2^(h+1)-1**개
  

  

Binary Tree의 종류

이진트리는 자식노드가 어떻게 구성되어 있냐에 따라 다음과 같이 5가지로 구분된다.

● Perfect Binary Tree (포화 이진 트리)

• 모든 레벨의 노드가 포화 상태 (left, right 자식노드가 모두 존재) 이진 트리

• 높이가 h일 때 최대의 노드 개수인 2^(h+1)-1개의 노드를 가진다.

• 루트를 1번으로 하여 2^(h+1)-1까지 정해진 위치에 대한 노드 번호를 가진다.

● Complete Binary Tree (완전 이진 트리)

• 높이가 h이고 노드 수가 n개일 때, 정 이진 트리의 노드 번호 1~n번까지 빈자리가 없는 이진 트리

• 마지막 레벨을 제외한 나머지 노드가 꽉 차 있어야 하며(마지막 레벨을 제외하고 포화 이진 트리이어야 하며), 마지막 레벨의 노드는 왼쪽 부터 차있어야 한다.

● Full Binary Tree (정 이진 트리) :

• 모든 레벨에서 노드들이 모두 채워져 있는 트리

= Leaf Node를 제외한 모든 노드의 차수가 2개로 이루어져 있음

• 해당 차수에 몇 개의 노드가 존재하는지 바로 알 수 있으므로 노드의 개수를 파악할 때 용이함

● Skewed Binary Tree (편향 이진 트리)

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

• 왼쪽 편향 이진 트리, 오른쪽 편향 이진 트리가 있음

• 편향 이진 트리는 검색에 성능 이슈가 있음

⇒ 이런 문제점을 극복하기위해  균형트리(AVL트리, 레드-블랙트리) 같은 변종이 생겨났다.

● Balanced Binary Tree (균형 이진 트리) :

• 트리에 삽입과 삭제가 일어나는 경우에 자동으로 그 높이(루트에서부터 내려갈 수 있는 최대 레벨)를 작게 유지하는 노드기반 이진 탐색 트리

• 왼쪽 그림은 균형이 맞지 않는(unbalanced) 트리

                          : 루트 → 특정 노드 : 평균 3.27회의 노드 접근
  

• 오른쪽 그림은 동일한 자료를 유지하면서 트리를 높이 균형을 맞춘 후의 상태 (균형이진트리)

                              : 평균 이동 비용이 3.00 노드 접근(node access)
  

• AVL트리, 레드-블랙트리가 있다.

Binary Tree의 순회

순서 트리와 무순서 트리

트리는 형제 노드의 순서 관계가 있는지에 따라 2종류로 분류된다. 형제 노드의 순서 관계가 있으면 순서트리, 구별하지 않으면 무순서 트리라고 한다.

순서 트리의 순회

• 너비 우선 검색(BFS)

  : 낮은 레벨부터 왼쪽에서 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법, 즉 맨 위에서부터 왼쪽에서 오른쪽, 왼쪽에서 오른쪽으로 검색하는법

• 깊이 우선 검색(DFS)

  : 리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 하는 방법, 리프에 도달해서 더 이상 검색할 곳이 없으면 일단 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려간다.

  • 전위순회 : 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식
  • 중위순회 : 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식
  • 후위순회 : 왼쪽 자식 -> 오른쪽 자식 -> 노드 방문

Preorder Traversal (전위순회)

전위 순회는 VLR 순서로 순회한다.

1. V : 현재 노드를 출력한다
2. L : 현재 노드 왼쪽 서브트리로 이동한다
3. R : 현재 노드 오른쪽 서브트리로 이동한다

def preorderTraversal(self, node):
    print(node, end='')
    if not node.left  == None : self.preorderTraversal(node.left)
    if not node.right == None : self.preorderTraversal(node.right)

해당 노드를 출력하고 왼쪽으로 이동한다. 왼쪽 노드가 존재하면 계속해서 왼쪽으로 이동하여 출력하고 왼쪽이 끝나는 노드부터 오른쪽 노드를 순회한다.

Inorder Traversal (중위순회)

중위 순회는 LVR 순서로 순회한다. 왼쪽 순회가 우선이고 출력이 중앙에 위치한다.

def inorderTraversal(self, node):
    if not node.left  == None : self.inorderTraversal(node.left)
    print(node, end='')
    if not node.right == None : self.inorderTraversal(node.right)

Postorder Traversal (후위순회)

후위 순회는 LRV로 순회한다. 출력이 마지막에 위치한다.

def postorderTraversal(self, node):
    if not node.left  == None : self.postorderTraversal(node.left)
    if not node.right == None : self.postorderTraversal(node.right)
    print(node, end='')

Binary Tree의 표현방법

• 배열

  • 1차원 배열에 저장하는 방법

    

    • 완전이진트리의 순서와 동일하게 인덱싱한다.
    • 편의상 배열의 첫 번째 요소는 사용하지 않는다.

    

  • 이진 트리의 경우, 2차원 배열에 자식 노드를 저장하는 방법

    

    • 모든 트리가 가능한 것 아님.

      이진 트리는 각 노드가 최대 두 개의 자식을 갖는 트리이기 때문에 2차원 배열로 가능함

    • A[i][0]은 왼쪽 자식, A[i][1]은 오른쪽 자식

  • 장단점

    장점 : 노드의 위치를 색인에 의해 쉽게 접근할 수 있다.

              배열을 기반으로 했을 때 용이한 트리 관련 연산도 존재한다.
    

    단점 : 특정 트리에서 기억 공간 낭비가 심할 수 있다.

    

• 연결 리스트로 표현
  • 이진트리를 표시하는 가장 일반적인 방법

  • 연결리스트 기반에서는, 트리의 구조와 리스트의 연결 구조가 일치

    ⇒ 구현과 관련된 직관적인 이해가 더 좋은 편

  • 왼쪽 자식을 가리키는 포인터 필드, 요소 필드, 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현하는 방법
  • 모든 이진 트리의 노드들은 데이터타입이 binaryTreeNode인 오브제로 표현된다.
  • 필요한 공간 : n * sizeof(binaryTreeNode)

  

  • 장단점

    장점 : 기억 장소를 절약할 수 있고, 노드 삽입과 삭제가 용이

    단점 : 이진 트리가 아닌 일반 트리의 경우 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 하기 때문에 접근상의 어려움이 있음

Binary Tree Traversal

• 전위 순회 (preorder traversal)

  DLR 순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 먼저 수행

• 중위 순회 (inorder traversal)

  LDR 순서로, 현재 노드를 방문하여 처리하는 작업 D를 작업 L과 작업 R의 중간에 수행

• 후위 순회 (postorder traversal)

  LRD 순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 나중에 수행

Threaded Binary Trees

스레드 이진 트리

                                                           헤드 노드를 제외한 이진 스레드 트리

• n개의 노드를 가지고 있는 이진트리에는 2n개의 링크가 존재
• 총 2n개의 링크 중 n+1개의 링크값은 null
  • Edge(간선) 수가 n-1개이기 때문
  • 루트 노드 제외(- 1), 모든 노드(n)가 부모 노드를 향한 Edge를 가지고 있음
• n + 1개의 할당 공간이 아깝다고 생각한 사람들이 n + 1개의 링크에 다른 유용한 정보를 집어 넣자고 생각

• Null 링크를 다른 노드에 대한 포인터로 대체 → 스레드(Threads)

  ※ 운영체제, 프로그래밍 언어에서 이야기하는 스레드와 완전히 다른 것

• 스레드를 포함하고 있는 트리: 스레드 이진 트리

Threaded Binary Tree의 특징

• 트리의 노드는 순서대로 채워진다.
• 트리의 다른 노드에 대한 thread라는 포인터로 null 링크를 변경한다
• 자식 노드와 연결되지 않는 링크는 중위 선행자 (Inorder Predecessor) 또는 중위 후행자 (Inoder Successor)와 연결된다.

• 중위 선행자 또는 중위 후행자가 없는 노드의 링크는 가상의 노드 head를 가리킨다.

• 장점 : 트리 전체의 모든 링크를 활용한다.

          중위 순회의 편의성이 증대된다**.**
  

Thread의 이용

• ptr -> leftChild = null인 경우, ptr → left_child를 ptr의 중위 선행자를 가리키도록 변경

  • 중위 선행자(Inorder Predecessor): 해당 노드 바로 앞에 나온 노드

• ptr -> rightChild = null인 경우, ptr → right_child를 ptr의 중위 후속자를 가리키도록 변경

  • 중위 후속자(Inorder Successor): 해당 노드 바로 뒤에 나오는 노드

head 노드의 특징

• head 노드의 왼쪽 링크는 root 노드를 가리킨다. (root 노드는 이진 트리의 첫번째 노드입니다.
• head 노드의 오른쪽 링크는 head, 즉, 자기 자신을 가리킨다.
• head 노드에 저장된 데이터는 없다.
• head를 제외한 이진 트리를 중위 순회 할 때 첫번쨰 노드의 왼쪽 링크와 마지막 노드의 오른쪽 링크는 head를 가리킨다.

                                 An Empty Threaded Binary Tree

Threaded Binary Tree의 중위 순회

• 스레드를 추가해서 얻는 이득: 중위 순회를 아주 쉽게 수행 가능

Step 1. 중위 후속자 찾기

• ptr이 현재 노드를 가리킨다고 가정

• If ptr → right_thread == TRUE

  ⇒ 중위 순회에서 ptr 다음 노드 = ptr → right_child

• Otherwise

  ⇒ ptr의 right_child로 간 다음, left_child를 따라 계속 내려간다.

  ⇒ 언제까지? left_thread == TRUE인 노드를 만날 때 까지

Step 2. 중위 후속자 발견 알고리즘 : insucc

struct thread_tree *insucc(struct thread_tree *ptr)
{   // 스레드 이진 트리에서 ptr이 가리키는 노드의 inorder successor return
    struct thread_tree *temp = ptr->right_child;

    if (!ptr->right_thread)        // right_child가 자식 노드이면
        while (!temp->left_thread) // 왼쪽 끝까지 가자
            temp = temp->left_child;

    return temp;
}

Step 3. 중위 순회 알고리즘 : tinorder

void tinorder(struct thread_tree *tree)
{   // 스레드 이진 트리를 중위 순회. 헤드 노드부터 시작
    struct thread_tree *temp = tree;

    for ( ; ; )
    {
        temp = insucc(temp);
        if (temp == tree) // 해당 노드의 중위 후속자가 헤드 노드면(다 돌았으면)
            break;

        printf("%3c", temp->data);
    }
}

• 순환 알고리즘 사용하지 않고 중위 순회 알고리즘 구현 가능

  ⇒ 더욱 효율적인 알고리즘

• 순환 알고리즘 이용시 overhead가 커짐

Threaded Binary Tree에서 Node 추가하기

새로운 노드를 parent 노드의 right child 로 추가한다고 가정해보자.

• Case 1 : parent → right_thread 값이 true일 경우
• Case 2 : parent → right_thread 값이 false일 경우

Case 1 : parent→right_thread == TRUE

• 3가지 포인터 변경이 필요
  • B에서 D로 연결되는 링크
  • 새로 추가된 노드 D의 left, right child

Case 2 : parent→right_thread == FALSE

• 이미 기존 노드가 오른쪽 자식으로 연결되어 있는 경우

  → 기존 노드의 중위 후속자의 중위 선행자까지 바꿔야 (총 4가지 포인터)

오른쪽에 추가하는 알고리즘

void insert_right(struct thread_tree *parent, struct thread_tree *child)
{   // 스레드 이진 트리에서 parent 오른쪽에 child 추가
    struct thread_tree *temp;

    child->right_child = parent->right_child;   // child의
    child->right_thread = parent->right_thread; // 정보부터
    child->left_child = parent;                 // 변경
    child->left_thread = TRUE;                  // 하자

    parent->right_child = child;
    parent->right_thread = FALSE; // child가 존재하므로 thread는 false
    if (!child->right_thread)
    {
        temp = insucc(child);     // parent의 원래 successor를 찾아서
        temp->left_child = child; // 새로운 predecessor로 변경
    }
}

• 참고자료
  • 윤성우의 열혈 자료구조
  • SW Expert Academy
  • https://www.fun-coding.org/Chapter10-tree.html
  • https://blex.me/@baealex/파이썬으로-구현한-자료구조-트리
  • https://jackpot53.tistory.com/7
  • https://smujihoon.tistory.com/153
  • https://blog.naver.com/PostView.naver?blogId=boldfaced7&logNo=222261232275&parentCategoryNo=&categoryNo=28&viewDate=&isShowPopularPosts=true&from=search
  • https://lsoovmee-rhino.tistory.com/47
  • https://blog.naver.com/PostView.naver?blogId=boldfaced7&logNo=222261232275&parentCategoryNo=&categoryNo=28&viewDate=&isShowPopularPosts=true&from=search