🌳 트리(tree)란?

트리tree는 자료구조에서 중요한 개념 중 하나로, 데이터를 저장하고 탐색하기에 유용한 구조를 갖고 있다.

트리Tree는 계층적 구조를 나타내는 비선형 자료구조로, 그래프Graph의 일종이다. 하나의 노드에서 시작하여 그 노드를 중심으로 여러 개의 자식 노드들이 연결된 구조를 형성한다. 이 구조에서 각 노드는 데이터를 저장하며, 노드들 간의 관계는 부모-자식 관계로 정의된다.

---

트리의 활용 분야

프로그래밍 분야에서 트리는 계층 구조를 표현하는 용도로 많이 사용된다. 예를 들어 파일 시스템이나 디렉터리 구조 등을 트리로 구성하거나 관리할 수 있다.

• 인공지능: 인공지능의 판단 기준을 만들 때 의사 결정 트리를 사용한다. 이를 통해 외부에서 입력된 데이터를 분류하거나 상황을 예측하는 모델을 만들 수 있다.

• 자동 완성 기능: 트리는 문자열 처리에도 많이 활용된다. 예를 들어 검색 엔진에서 자동 검색어 추천 기능도 트라이trie라는 독특한 트리 구조를 활용한 것이다. 이를 활용하면 접두사나 패턴 검색을 쉽게 할 수 있다.

• 데이터베이스: 데이터를 쉽게 검색, 삽입, 삭제를 할 수 있도록 트리를 활용해서 데이터를 구조화하고 인덱싱한다. 이때 B-트리나 B+트리를 많이 사용한다.

---

트리의 용어

트리는 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놓은 모양이다. 따라서 나무 밑둥root이 맨 위에 있다. 다음 그림은 트리의 구조를 표현한 것이다.

✅ 트리를 구성하는 노드

노드는 트리를 구성하는 요소이다. 노드 중 가장 위에 있는 노드를 루트 노드root node라고 한다. 위 그림에서는 맨 위에 있는 값 1이 들어 있는 노드가 루트 노드이다.

✅ 노드를 연결하는 엣지

노드와 노드 사이에는 이어주는 선이 있다. 이를 간선 또는 엣지edge라고 한다. 그리고 트리는 노드와 노드가 단방향 간선으로 연결되어 있고, 루트 노드에서 각 노트까지의 경로는 유일하다.

루트 노드로부터 특정 노드까지 거쳐가는 최소한의 간선 수를 레벨이라고 표현한다. 예를 들어 루트 노드는 레벨 0, 노드 19,2,13은 레벨 1이다.

✅ 부모-자식, 형제 관계를 가지는 노드

간선으로 연결된 노드들은 서로 부모-자식 관계가 있다고 표현한다. 간선으로 직접 연결된 노드 중 위에 있는 노드를 부모 노드parent node, 아래에 있는 노드를 자식 노드child node라고 한다.

2,7,5의 관계 중 2는 7,5의 부모 노드이며 7,5처럼 같은 부모 노드를 갖는 노드를 형제 노드sibing node라고 한다.

✅ 자식이 없는 리프 노드

자식이 없는 노드는 리프 노트leaf node라고 한다.

✅ 아래로 향하는 간선의 개수, 차수

차수degree란 특정 노트에서 아래로 향하는 간선의 개수이다. 예를 들어 노트 1은 차수가 3이다. 왜냐하면 아래로 향하는 간선이 3개이기 때문이다.

💡 코딩 테스트에서는 이진 트리만 알면 된다!
트리 종류는 굉장히 다양하지만 코딩 테스트에서는 이진 트리binary tree만 제대로 알고 있으면 충분하다. 이진 트리란 모든 노드의 최대 차수가 2를 넘지 않는 트리를 말한다. (간선이 최대 2개인 트리)

---

이진 트리(Binary Tree)

이진 트리는 배열이나 포인터로 구현할 수 있다. 여기서는 배열로 이진 트리를 구현하는 방법을 알아본 후, 포인터로 구현하는 방법을 알아볼 예정이다. 이진 트리는 다음 그림과 같이 노드 하나가 최대 2개의 자식 노드를 갖는다.

배열로 표현하기

배열은 선형 자료구조이고 트리는 계층 자료구조이다. 따라서 배열로 트리를 표현하려면 다음 3가지 규칙이 필요하다.

이 규칙은 루트 노드 = 배열 인덱스 1번이라고 상정하여 작성한 규칙이다.

• 루트 노드는 배열 인덱스 1번에 저장한다.
• 왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 * 2이다.
• 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 * 2 + 1이다.

위 규칙에 맞게 인덱스를 붙이면 다음과 같다.

루트 노드를 인덱스 0으로 하면 왼쪽 자식 노드는 부모 노드의 배열 인덱스 * 2 + 1이 되고, 오른쪽 자식 노드는 부모 노드의 배열 인덱스 * 2 + 2가 된다. 입력값에 따라 루트 노드를 0 또는 1로 정해야 하는 경우가 있다.

💡 루트 노드의 인덱스가 0일 때와 1일 때의 차이

• 인덱스가 0일 때: left_child = 2*i + 1, right_child = 2*i + 2
• 인덱스가 1일 때: left_child = 2*i, right_child = 2*i + 1

트리로 표현한 배열을 보면 빈 값이 꽤 보인다. 노드들의 부모-자식 관계를 곱셈 처리하다 보니 실제 개수보다 더 많은 공간을 사용할 수 밖에 없다. 즉, 배열로 트리를 표현하면 메모리가 낭비된다는 단점이 있다. 그렇다고 해서 배열 표현 방법이 나쁘다는 것은 아니다. 이진 트리를 배열로 표현하는 방식은 구현 난이도가 쉽고, 대부분의 코딩 테스트에서는 배열로 이진 트리를 구현해도 문제가 없다.

💡 이진 트리 생성 시간: O(N)

포인터로 표현하기

포인터로 트리를 표현하려면 노드부터 정의해야 한다. 다음 그림처럼 노드는 노드의 값, 왼쪽 자식 노드와 오른쪽 자식 노드를 가진다.

이 노드 구성을 트리에 적용하면 다음과 같다.

포인터로 표현한 트리는 배열과 달리 인덱스 연산을 하지 않으므로 메모리 공간을 낭비하지 않는다. 그러나 실제 노드를 따라가도록 구현해야 하므로, 구현 난이도는 배열로 표현한 트리에 비해 조금 높다.

---

🏃‍♂️ 이진 트리 순회하기

순회란 어떤 데이터가 있을 때 그 데이터를 빠짐 없이 방문하는 것을 의미한다. 배열에서 인덱스로 데이터를 검색할 때 순회하는 것처럼 트리도 순회할 방법이 필요하다. 이진 트리에서의 순회는 총 3가지 방법이 있다.

• 전위 순회preorder: 현재 노드를 부모 노드로 생각했을 때 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 방문한다.

• 중위 순회inorder: 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서로 방문한다.

• 후위 순회postorder: 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드 순서로 방문한다.

순회에서 주목해야 할 표현은 현재 노드를 부모 노드로 생각했을 때이다. 이 말을 이해해야 순회를 쉽게 이해할 수 있다. 이제 각 순회 과정의 설명을 보며 더 깊게 알아보자.

전위 순회 과정

전위 순회는 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 방문하는 방식이다.

전위 순회는 거치는 노드를 우선 방문(출력)하므로 직관적으로 이해하기 쉽다. 전위 순회는 트리를 복사할 때 많이 사용한다.

중위 순회 과정

중위 순회는 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서로 방문하는 방식이다.

중위 순회는 거쳐가는 노드, 즉, 현재 노드를 거치기만 할 뿐 방문하지 않는다. 중위 순회는 이진 탐색 트리에서 정렬된 순서대로 값을 가져올 때 사용된다.

후위 순회 과정

후위 순회는 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드 순서로 방문한다.

노드를 삭제할 때는 부모를 먼저 삭제하면 안 된다. 자식 노드부터 삭제해야 트리를 유지하며 재귀로 루트 노드까지 삭제할 수 있기 때문이다 그래서 자식 노드부터 방문한다는 특성이 있는 후위 순회는 트리 삭제에 자주 활용한다.

---

🔍 이진 탐색 트리

이진 트리에서 가장 중요한 것은 바로 탐색을 효율적으로 할 수 있도록 트리를 구축하는 것이다. 여기서는 이진 탐색 트리binary search tree를 만들고, 이를 활용해 원하는 노드를 효율적으로 찾는 방법을 알아보자.

이진 탐색 트리 구축하기

이진 탐색 트리의 대상 데이터가 50, 15, 62, 80, 7, 54, 11 순서로 들어온다고 생각하고 구축해보자. 이진 탐색 트리는 데이터 크기를 따져 크기가 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식을 갖고 있다. 데이터를 하나씩 삽입하며 구축하는 것이다. 즉, 삽입과 동시에 정렬을 한다.

• 1단계: 최초의 데이터 = 루트 노드이므로, 50을 이진 탐색 트리에 루트 노드로 추가한다.

• 2단계: 다음 요소를 읽고 루트 노드 요소보다 작으면 왼쪽 하위 트리의 루트로 삽입한다.

• 3단계: 그렇지 않으면 오른쪽 하위 트리의 오른쪽 루트로 삽입한다.

• 4단계: 이 과정을 반복한다.

이진 탐색 트리 탐색하기

이제 구축한 트리를 탐색해보자. 이진 탐색 트리를 탐색하는 방법은 다음과 같다.

💡 이진 트리 탐색 방법

• 1단계: 찾으려는 값이 현재 노드의 값과 같으면 탐색 종료
• 2단계:
  • 찾으려는 값이 현재 노드의 값보다 더 크면 오른쪽 노드를 탐색
  • 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드 탐색
• 3단계: 값을 찾을 때까지 반복

만약 노드가 없을 때까지 계속 탐색했는데 값이 없으면 현재 트리에 값이 없는 것이다.

---

🆚 이진 탐색 트리 vs 배열 탐색

배열에서는 순차적으로 값을 찾는다. 만약 값이 마지막에 있다면 O(N)만큼 탐색을 진행해야 한다. 그에 반해 이진 탐색 트리는 조건에 맞지 않는 노드들은 탐색하지 않기에 속도가 더 빠르다고 할 수 있다.

이진 탐색 트리는 크면 오른쪽, 작으면 왼쪽

모든 탐색 알고리즘엣 탐색 효율을 개선하는 방법은 같다. 탐색 대상이 아닌 노드를 한 번에 많이 제외할 수 있으면 된다. 이진 탐색 트리의 원리도 동일하다. 이진 탐색 트리의 구축 방식의 특성은 데이터 크기에 따라 하위 데이터 중 한 방향을 검색 대상에서 제외하므로 검색을 빠르게 만들어준다.

⌛ 이진 탐색 트리의 시간 복잡도

이진 탐색 트리의 시간 복잡도는 트리 균형에 의존한다. 균형이 유지되었다고 가정할 때의 시간 복잡도는 O(logN)이다. 하지만 균형이 맞지 않을 때는 배열과 비슷한 O(N) 시간 복잡도를 갖고 있다.

대부분의 상황에서는 이진 탐색 트리의 탐색 성능이 더 좋긴 하지만, 한쪽으로 치우쳐지지 않도록 균형을 유지하는 이진 탐색 트리가 있다.

⚖️ 트리의 균형과 균형 이진 탐색 트리

일반적인 이진 탐색 트리(BST)는 삽입과 삭제 연산에 의해 균형이 깨질 수 있다. 이를 해결하기 위해 여러 자가 균형 이진 탐색 트리(Self-balancing BST)들이 개발되었는데, 대표적인 예로는 AVL 트리와 레드-블랙 트리가 있다.

• AVL 트리: 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하로 유지되도록 하는 이진 탐색 트리이다. 삽입 및 삭제 연산 후에 균형을 유지하기 위해 추가적인 회전 연산을 수행한다. 시간 복잡도는 항상 O(log N)이다.

• 레드-블랙 트리: 각 노드에 색깔(빨강 또는 검정)을 추가하고 특정 규칙을 통해 트리의 균형을 유지하는 이진 탐색 트리이다. 시간 복잡도는 항상 O(log N)이다.

다만 균형 이진 탐색 트리 구현은 난이도가 매우 높은 편으로, 코딩 테스트에 나올 가능성은 매우 낮다. 트리에 대해서는 따로 자료구조를 공부할 때 다루도록 하겠다.

	배열 탐색	이진 탐색 트리 탐색
최선의 경우	O(1)	O(1)
최악의 경우	O(N)	일반 BST: O(N), 균형 트리: O(log N)
평균의 경우	O(N)	일반 BST: O(log N)