자료구조 & 알고리즘(4)
이 글은 자료구조와 알고리즘을 '코딩 인터뷰'를 준비하기 위해서 정리한 글입니다.
이번 글은 트리를 다루겠습니다.
(1) 서론
- 트리에서 탐색(search)하는 것이 배열이나 연결리스트처럼 선형으로 구성된 자료구조에서
탐색하는 것보다 훨씬 까다롭습니다.
또한, 최악의 수행 시간과 평균적 수행 시간이 매우 크게 바뀔 수 있어서,
알고리즘을 살펴볼 때에는 두 가지 측면 모두를 반드시 따져 봐야 합니다.
트리와 그래프를 밑바닥부터 능숙하게 구현할 수 있는 능력을 갖추면
분명 도움이 될 것입니다.
(2) 트리
- 트리를 이해하기 위한 좋은 방법 중 하나는 재귀적 설명법을 사용하는 것입니다.
트리는 노드로 이루어진 자료구조입니다.
트리의 특징은 다음과 같습니다.
(1)트리는 하나의 루트 노드를 갖습니다.
(2)루트 노드는 0개 이상의 자식 노드를 갖습니다.
(3)그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고,
이는 반복적으로 정의됩니다.
트리에는 사이클(cycle)이 존재할 수 없습니다.
노드들은 특정 순서로 나열될 수도 있고 그럴 수 없을 수도 있습니다.
각 노드는 어떤 자료형으로도 표현 가능합니다.
각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있습니다.
트리 및 그래프 문제들은 대부분 세부사항이 모호하거나 가정 자체가 틀린 경우가 많습니다.
따라서 아래의 이슈들에 유의하고, 필요하면 명확하게 해줄 것을 요구해야 합니다.
(2-1) 트리 vs 이진 트리
- 이진 트리(binary tree)는 각 노드가 최대 두 개의 자식을 갖는 트리를 말합니다.
모든 트리가 이진 트리는 아닙니다. 이진 트리가 아닌 것에는 삼진 트리(ternary tree)가 존재합니다.
자식이 없는 노드는 말단노드라고 부릅니다.
(2-2) 이진 트리 vs 이진 탐색 트리
- 이진 탐색 트리는 모든 노드가 다음과 같은 특정 순서를 따르는 속성이 있는 이진 트리를 일컫습니다.
'모든 왼쪽 자식들 <= n <= 모든 오른쪽 자식들'
이 속성은 모든 노드 n에 대해서 반드시 참이어야 합니다.
많은 지원자들이 트리 문제가 주어지면 이진 탐색 트리일 것이라고 가정해 버립니다.
이진 탐색 트리인지 아닌지 확실히 묻도록 해야 합니다.
(2-3) 균형 vs 비균형
- 많은 트리가 균형 잡혀 있긴 하지만 전부 그런 것은 아닙니다.
면접관에게 어느 쪽인지 묻도록 해야 합니다.
균형을 잡는다는 것이 왼쪽과 오른쪽 부분 트리의 크기가 완전히 같게 하는 것을
의미하지는 않습니다.
균형 트리인지 아닌지 확인하는 방법 중 하나는 '너무 불균형한건 아닌지'
확인하는 것 이상의 의미를 갖습니다. O(logN)시간에 insert와 find를 할 수 있을 정도로
균형이 잘 잡혀 있지만, 그렇다고 꼭 완벽하게 균형 잡혀 있을 필요는 없습니다.
균형 트리의 일반적인 유형으로는 레드-블랙 트리와 AVL트리 이렇게 두 가지가 있습니다.
(2-4) 완전 이진 트리
- 완전 이진 트리(complete binary tree)는 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리를 말합니다.
마지막 단계(level)는 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 합니다.
(2-5) 전 이진 트리
- 전 이진 트리(full binary tree)는 모든 노드의 자식이 없거나 정확히 두 개 있는 경우를 말합니다.
즉, 자식이 하나만 있는 노드가 존재해서는 안됩니다.
(2-6) 포화 이진 트리
- 포화 이진 트리(perfect binary tree)는 전 이진 트리이면서 완전 이진 트리인 경우를 말합니다.
모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 갯수는 최대가 되어야 합니다.
(3) 이진 트리 순회
- 면접에 들어가기 앞서 중위(in-order), 후위(post-order), 전위(pre-order) 순회에 대해서
익숙해져야 합니다. 그 중 가장 빈번하게 사용되는 순회 방식은 중위 순회입니다.
(3-1) 중위 순회
- 중위 순회(in-order traversal)은 왼쪽 가지(Left) - 현재 노드(Root) - 오른쪽 가지(Right) 순서로
노드를 방문하는 방법을 말합니다.
(3-2) 전위 순회
- 전위 순회(pre-order traversal)은 현재 노드(Root) - 왼쪽 가지(Left) - 오른쪽 가지(Right) 순으로
노드를 방문하는 방법을 말합니다.
(3-3) 후위 순회
- 후위 순회(post-order traversal)은 왼쪽 가지(Left) - 오른쪽 가지(Right) - 현재 노드(Root) 순으로
노드를 방문하는 방법을 의미합니다.
Q&A
(1) 서론
Q. 왜 트리에서 탐색(search)하는 것이 배열이나 연결리스트처럼 선형으로 구성된 자료구조에서 탐색하는 것보다 훨씬 까다로운가?
A.
Q. 왜 최악의 수행 시간과 평균적 수행 시간이 매우 크게 바뀔 수 있습니까?
A.
Q. 왜 트리와 그래프를 밑바닥부터 능숙하게 구현할 수 있는 능력을 갖추면 분명 도움이 됩니까?
A.
(2) 트리
Q. 왜 트리를 이해하기 위한 좋은 방법 중 하나는 재귀적 설명법을 사용하는 것입니까?
A.
Q. 왜 트리에는 사이클(cycle)이 존재할 수 없습니까?
사이클(cycle)이란 무엇입니까?
A.
Q. 왜 트리 및 그래프 문제들은 대부분 세부사항이 모호하거나 가정 자체가 틀린 경우가 많습니까?
A. 어떤 트리냐에 따라서 실제 어떤 코드로 구현해야 하는 것들이 달라질 수 있습니다.
이 때, 실제 어떤 트리인지 정확하게 확인해야만 그에 알맞는 코드로 구현을 할 수 있습니다.
(2-2) 이진 트리 vs 이진 탐색 트리
Q. 왜 이진 탐색 트리가 존재합니까? 왜 이진 탐색 트리는 위와 같은 정의를 가집니까?
A. 이진 탐색 트리의 용어 중 이진 탐색(binary search)에 주목해야 합니다.
즉, 이진 탐색 트리는 자료의 효율적인 탐색을 위한 트리입니다.
이진 탐색 트리는 O(logn)의 시간 복잡성을 지닙니다.
참고: https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/
Q. 왜 이진 탐색 트리인지 아닌지 확실히 물어야 합니까?
A. 실제 이진 탐색 트리는 이진 트리의 한 가지 종류일뿐입니다.
따라서 어떤 문제가 주어졌을 때, 그 문제의 이진 트리가
이진 탐색 트리인지 아닌지 반드시 확인해야 합니다.
즉, 이진 트리에 관한 문제일 때, 그 이진 트리가 반드시 이진 탐색 트리인 것은 아닙니다.
(2-3) 균형 vs 비균형
Q. 왜 균형을 잡는다는 것이 왼쪽과 오른쪽 부분 트리의 크기가 완전히 같게 하는 것을 의미하지는 않습니까?
A.
Q. 왜 O(logN)시간에 insert와 find를 할 수 있을 정도로 균형이 잘 잡혀 있는지 따져봐야 합니까?
A.
(3) 이진 트리 순회
Q. 왜 중위 순회, 후위 순회, 전위 순회와 같은 순회들이 존재합니까?
A. 순회란 이진 트리에서 각각의 노드를 체계적으로 한 번만 방문하는데 쓰이는 방식을 의미합니다.
Q. 왜 중위 순회는 존재합니까?
A.
Q. 왜 후위 순회는 존재합니까?
A.
Q. 왜 전위 순회는 존재합니까?
A.
Q. 왜 중위 순회가 가장 빈번하게 사용되는 순회 방식입니까?
A. 중위 순회는 이진 탐색 트리(binary search tree)에 사용되는 순회 방식입니다.
- 이 글의 내용은 '코딩 인터뷰 완전 분석'을 참조했습니다.
