1️⃣ 트리란?
트리라는 말의 어원은 자료구조가 마치 나무가 거꾸로 서있는 듯한 구조를 띈다고 해서 트리라고 명명되었습니다.
아래 그림이 바로 트리의 예입니다.
트리는 여러개의 노드들로 구성이 됩니다.
트리 자료구조에 대해서 한번 용어 정리를 하고 넘어가도록 하겠습니다.
- 제일 꼭대기의 노드 :
루트 노드라고 합니다. - 노드와 노드를 잇는 선 :
간선(Edge)이라고 합니다. - A와 B의 관계: A는 B의
부모노드이다. B는 A의자식노드이다. 라고 보통 말합니다. - 차수 : 한 노드가 가지는 서브트리의 수, 즉 자식 노드의 수를 해당 노드의
차수라고 말합니다. - 자식노드가 없는 노드를
단말노드(Leaf Node)라고 부릅니다. 트리의 높이는 그림 오른쪽의 최대 레벨이 트리의 높이가 됩니다. 즉, 위의 그림에서는 트리의 높이는 3입니다.
2️⃣ 트리의 종류
먼저 이진트리라는 것이 있습니다. 이진 트리는 트리의 모든 노드의 차수를 2이하로 제한하여 전체 트리의 차수가 2이하가 되도록 정의한 것입니다.
보통 자료구조에서 트리는 이진트리냐 아니냐로 부터 크게 나뉩니다.
그 후, 이진트리에서 또다시 편향 이진트리, 완전 이진트리 등으로 나뉩니다.
대략적인 분류를 다이어그램으로 본다면 다음과 같습니다.
- 포화 이진트리 : 높이를 추가하지 않는 한 더 이상 노드를 추가할 수 없는 포화 상태의 이진트리
- 완전 이진트리 : 꽉 차 있지는 않지만 높이가 h이고, 높이 h-1까지의 노드가 다 차있는 경우
- 편향 이진트리 : 이진트리 중에서 최소 개수의 노드를 가지면서 왼쪽이나 오른쪽 서브트리만 갖고 있는 경우
3️⃣ 트리의 순회 방법
트리는 크게 세가지의 순회방식을 갖고 있습니다.
- 중위 순회(In-order) : 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문하는 순회 방법
- 전위 순회(Pre-order) : 자신, 왼쪽 자손, 오른쪽 자손 순서로 방문하는 순회 방법
- 후위 순회(Post-order) : 왼쪽 자손, 오른쪽 자손, 자신 순서로 방문하는 순회 방법
이렇게 세가지로 나뉩니다. 아래 그림을 통해 순회 방식을 익혀보도록 합시다.
- In-order: 1 3 4 6 7 8 10 13 14
- Pre-order: 8 3 1 6 4 7 10 14 13
- Post-order: 1 4 7 6 3 13 14 10 8
위 자료는 트리 나무위키를 참조하였습니다.
4️⃣ 이진 탐색 트리
이진 트리를 탐색을 위한 자료구조로 사용하는 것이 바로 이진 탐색 트리(Binary Search Tree)입니다.
이진 탐색 트리의 특징은 다음과 같습니다.
- 모든 원소는 서로 다른 유일한 키를 갖는다.
- 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다.
- 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 크다.
- 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.
5️⃣ 이진 탐색 트리의 시간복잡도
이진 탐색 트리의 시간복잡도는 O(h) 입니다. 여기서 h는 트리의 높이를 의미합니다.
O(h)인 이유는 트리의 높이를 탐색할때마다 완전이진 트리라면 그 경우의 수가 절반씩 줄어들기 때문입니다.
마치 이분탐색과 같습니다.
하지만 여기서 중요한 것은 트리의 삽입과 삭제가 빈번하게 일어나는데 어떻게 계속 완전 이진트리를 유지할까요?
이렇게 나온 개념이 바로 Red-Black 트리와 AVL 트리입니다. 이에 대해서는 다음시간에 한번 자세하게 더 다뤄 보도록하겠습니다.
여기서는 트리의 높이가 최대 n이 될 수 있어서 최악의 시간복잡도가 O(n)이고 보통 O(h)라고만 알고 계시면 될 것같습니다.
참고로 다음시간에 알아볼 Red-Black 트리와 AVL트리는 최악에도 O(logn)을 넘지 않도록 해줍니다.
6️⃣ 마치며
오늘은 기본적인 트리에 대해서 알아보았습니다.
트리가 깊게 들어간다면 한없이 깊게 들어갈 수 있지만 여기서는 기본적인 면접준비를 위한 자료구조를 훑어 보기 위함이어서
간단하게 넘어간 점 양해 부탁드립니다.
잘못된 점이나 궁금한 점이 있다면 아래 댓글 남겨주세요.
읽어주셔서 감사합니다.
