책너두 (코딩 인터뷰 완전분석) 14일차 (~156p, 831p)

메모

04 트리와 그래프

• 트리에서 탐색(search) 하는 것은 배열이나 연결리스트처럼 선형으로 구성된 자료구조에서 탐색하는 것보다 훨씬 까다로움.
• 최악의 수행 시간과 평균적 수행 시간이 매우 크게 바뀔 수 있어서, 알고리즘을 살펴볼 때, 두 가지 측면 모두를 반드시 따져봐야 함.
  • 트리와 그래프를 밑바닥부터 능숙하게 구현할 수 있는 능력을 갖추면 분명히 도움이 될 것임.

트리의 종류

• 트리를 이해하기 가장 좋은 방법은 재귀적 설명법을 사용하는 것임.
• 트리는 노드로 이루어진 자료구조임.
  • 트리는 하나의 루트 노드를 갖는다.
  • 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
  • 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의됨.
• 트리에는 사이클이 존재할 수 없음.
• 노드들은 특정 순서로 나열될 수도 있고, 그럴수 없을 수도 있음.
• 각 노드는 어떠한 자료형으로도 표현 가능함.
• 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있음.

class Node {
    public String name;
    public Node[] children;
}

• 이 노드 클래스를 포함하는 Tree 클래스를 정의할 수도 있음.
• 트리 및 그래프 문제들은 대부분 세부사항이 모호하거나 가정 자체가 틀린 경우가 많음.
  • 아래의 이슈에 대해 유의하여, 필요하면 명확하게 해 줄 것을 요구하자.

트리 vs. 이진 트리

• 이진 트리(binary tree)는 각 노드가 최대 두 개의 자식을 갖는 트리를 말함.
• 모든 트리가 이진 트리는 아님.

• 위 트리는 이진 트리가 아니라 삼진 트리(ternary tree) 라고 부름.
  • 종종 이진 트리가 아닌 트리를 다뤄야 할 때가 있음.
  • ex) 전화번호를 표현할 때 트리를 사용한다고 가정
    • 각 노드가 10개의 자식(하나당 숫자 하나)을 갖는 10차 트리(10-ary tree)를 사용해야 할 것임.
• 자식이 없는 노드는 ‘말단’노드라고 부름.

이진 트리 vs. 이진 탐색 트리

• 이진 탐색 트리는 모든 노드가 다음과 같은 특정 순서를 따르는 속성이 있는 이진 트리를 일컫는다.
  • 모든 왼쪽 자식들 ≤ n < 모든 오른쪽 자식들
    • 모든 노드 n에 대해서 반드시 참이어야 한다.

어떤 곳에서는 트리가 중복된 값을 가지면 안된다고 하며, 또 다른 곳은 중복된 값이, 양쪽에 존재할 수도 있다고 함. 모두 맞는 정의이지만, 면접관에게 미리 명확히 얘기할 필요가 있음.

• 부등식의 경우, 바로 아래 자식뿐만 아니라 내 밑에 있는 모든 자식 노드들에 대해서 참이어야 함.
• 아래의 오른쪽 그림은 12가 8왼쪽에 있으므로 이진 탐색 트리가 될 수 없음.

균형 vs. 비균형

• 많은 트리가 규현 잡혀 있긴 하지만 전부 그런 것은 아님.
• 규현을 잡는다는 것이 왼쪽과 오른쪽 부분 트리의 크기가 완전히 같게 하는 것을 의미하지는 않음.
• ‘균형’ 트리인지 아닌지 확인하는 방법 중 하나는 ‘너무 불균형한건 아닌지’ 확인하는 것 이상의 의미를 갖는다.
• O(logN) 시간에 insert, find 할 수 있을 정도로 균형이 잘 잡혀 있지만, 그렇다고 꼭 완벽하게 균형 잡혀 있을 필요는 없음.
• 균형 트리의 일반적인 유형
  • 레드-블랙 트리(p818), AVL 트리(816p) 두 가지가 있음.
  • 고급 주제에서 더 자세히 다룰 예정

완전 이진 트리

• 완전 이진 트리(complete binary tree) : 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리를 말함.
• 마지막 단계는 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 함.

전 이진 트리

• 전 이진 트리(full binary tree) : 모든 노드의 자식이 없거나 정확히 두 개 있는 경우를 말함.
  • 즉, 자식이 하나만 있는 노드가 존재해서는 안된다.

포화 이진 트리

• 포화 이진 트리(perfect binary tree) : 전 이진 트리이면서 완전 이진 트리인 경우를 말함.
  • 모든 말단 노드는 같은 높이에 있어야 함
  • 마지막 단계에서 노드의 개수가 최대가 되어야 함.
• 포화 이진 트리는 노드의 개수가 정확히 2^(k-1) (k는 트리의 높이) 개여야 함.
• 면접이든 실제든, 흔한 상황은 아님.

이진 트리 순회

• 중위(in-order), 후위(post-order), 전위(pre-order) 순회에 대해 익숙해져야 함.
  • 가장 빈번하게 사용되는 순회 방식은 중위 순회임.

중위 순회

• 중위 순회(in-order traversal) : 왼쪽 가지, 현재 노드, 오른쪽 가지 순서로 노드를 방문하고 출력하는 방법임.

void preOrderTraversal(TreeNode node) {
    if (node != null) {
        preOrderTraversal(node.left);
        visit(node);
        preOrderTraversal(node.right);
    }
}

전위 순회

• 전위 순회(pre-order traversal) : 자식 노드보다 현재 노드를 먼저 방문하는 방법임.

void preOrderTraversal(TreeNode node) {
    if (node != null) {
        visit(node);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

후위 순회

• 후위 순회(post-order traversal) : 모든 자식 노드들을 먼저 방문한 뒤 마지막에 현재 노드를 방문하는 방법임.

void preOrderTraversal(TreeNode node) {
    if (node != null) {
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
        visit(node);
    }
}