[자료구조] 이진 트리(Binary Tree) 완벽 정리: 작동 원리와 코딩 테스트 활용 전략
카테고리: Algorithm Theory
태그: algorithm binary tree implementation coding test data structure binary tree
1. 🔍 트리(Tree)의 개념
- 트리는 데이터를 저장하고 탐색하기에 유용한 구조를 갖고 있다.
- 트리가 데이터를 어떤 방식으로 저장하고 탐색하는지 알아보자.
트리 용어 정리
- 트리는 나무 기둥에서 가지가 벋어나가는 모습을 거꾸로 뒤집어 놓은 모양이다. 따라서 나무 밑둥(
root)이 맨 위에 있다. - 노드는 트리를 구성하는 요소이다. 노드 중 가장 위에 있는 노드를 루트 노드(root node)라고 한다.
- 위 그림에서는 맨 위에 1이 들어 있는 노드가 루트 노드이다.
- 노드와 노드 사이에는 이어주는 선이 있다. 이를 간선 또는 엣지(edge) 라고 한다.
- 트리는 노드와 노드가 단방향 간선으로 연결되어 있고, 루트 노드에서 각 노드까지의 경로는 유일하다.
- 루트 노드로부터 특정 노드까지 거쳐가는 최소한의 간선 수를 레벨로 표현한다.
- 예를 들어 루트 노드는 레벨 0, 노드 19, 2, 13은 레벨 1이다.
- 간선으로 연결된 노드들은 서로 부모-자식 관계가 있다고 표현한다.
- 간선으로 직접 연결된 노드 중 상대적으로 위에 있는 노드를 부모 노드(parent node), 아래에 있는 노드를 자식 노드(child node) 라고 한다.
- 위 그림에서 2가 상대적으로 7, 5의 부모 노드가 된다.
- 7, 5처럼 같은 부모 노드를 갖는 노드를 형제 노드(sibling node) 라고 한다.
- 자식이 없는 노드는 리프 노드(leaf node) 라고 한다.
- 차수(degree) 란 특정 노드에서 아래로 향하는 간선의 개수이다.
- 예를 들어 노드 1은 차수가 3이다.(아래로 향하는 엣지가 3개)
코딩 테스트에서는 이진 트리(binary tree) 만 제대로 알고 있으면 충분하다. 이진 트리란 모든 노드의 최대 차수가 2를 넘지 않는 트리를 말한다(간선이 최대 2개인 트리).
트리의 특성을 활용하는 분야
계층 구조를 표현하는 용도로 많이 사용한다. ex) 파일 시스템이나 디렉터리 구조 등을 트리로 구성하거나 관리함.
- 인공지능: 인공지능의 판단 기준을 만들 때 의사 결정 트리를 사용한다. 이를 통해 외부에서 입력된 데이터를 분류하거나 상황을 예측하는 모델을 만들 수 있다.
- 자동 완성 기능: 트리는 문자열 처리에도 많이 활용된다. 예를 들어 검색 엔진에서 자동 검색어 추천 기능도 트라이(trie)라는 독특한 트리 구조를 활용한 것이다. 이를 활용하면 접두사나 패턴 검색을 쉽게 할 수 있다.
- 데이터베이스: 데이터를 쉽게 검색, 삽입, 삭제할 수 있도록 트리를 활용해서 데이터를 구조화하고 인덱싱한다. 이때 B-Tree나 B+Tree를 많이 사용한다.
2. ✨ 이진 트리 표현하기
이진 트리는 배열이나 포인터, 인접 리스트로 구현할 수 있다. 최소한 인접 리스트와 배열로 구현하는 방식은 반드시 기억하자.
배열로 표현하기
- 루트 노드는 배열 인덱스 1번에 저장한다.
- 왼쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 x 2이다.
- 오른쪽 자식 노드의 배열 인덱스는 부모 노드의 배열 인덱스 x 2 + 1이다.
- 배열로 트리를 표현하면 자식이 없거나 쓰지 않는 인덱스들은 모두 빈 값이므로 메모리가 낭비된다는 단점이 있다.
- 이진 트리를 배열로 표현하는 방식은 구현 난이도가 낮으므로 메모리만 넉넉하다면 구현 시간을 단축하는 용도로 좋다.
- 다행히도 대부분 코딩 테스트에서는 배열로 이진 트리를 구현해도 괜찮은 경우가 많다.
- 노드가 $N$개일 때, 배열로 이진 트리를 생성하면 $O(N)$이 걸린다.
포인터로 표현하기
포인터로 트리를 표현하려면 노드부터 정의해야 한다.
- 포인터로 표현한 트리는 배열과 달리 인덱스 연산을 하지 않으므로 메모리 공간을 낭비하지 않는다.
- 실제 노드를 따라가도록 구현해야 하므로 구현 난이도는 배열로 표현한 트리에 비해 높다.
인접 리스트로 표현하기
인접 리스트로 트리를 표현하려면 리스트를 노드 수만큼 만들어야 한다.
- 노드 개수만큼만 메모리 공간을 사용하고, 구현 난이도도 포인터에 비해 낮다.
- 하지만 특정 노드를 찾기 위해 연결 노드를 하나씩 따라가야 하는 단점이 있다.
3. ⚡ 이진 트리 순회하기
순회란 데이터가 있을 때 그 데이터를 빠짐없이 방문하는 것을 의미한다. 이진 트리에서의 순회는 총 3가지 방법이 있다.
- 전위 순회(preorder): 현재 노드를 부모 노드로 생각했을 때, 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 방문한다.
- 중위 순회(ineorder): 현재 노드를 부모 노드로 생각했을 때, 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서로 방문한다.
- 후위 순회(postorder): 현재 노드를 부모 노드로 생각했을 때, 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드 순서로 방문한다.
전위 순회
현재 노드가 부모 노드이고 부모 노드를 가장 먼저 방문하기 때문에 루트 노드부터 시작하면 아래 순서대로 탐색을 하게 된다.
- 전위 순회는 트리를 복사할 때 많이 사용한다.
중위 순회
중위 순회의 경우 현재 노드와 처음 방문해야 하는 노드가 일치하지 않으므로 방문하지 않고 지나치는 노드들이 생긴다.
- 중위 순회는 이진 탐색 트리에서 정렬된 순서대로 값을 가져올 때 사용된다.
후위 순회
후위 순회 또한 현재 노드와 처음 방문해야 하는 노드가 일치하지 않으므로 방문하지 않고 지나치는 노드들이 생긴다.
- 노드를 삭제할 때는 부모 노드를 먼저 삭제하면 안된다.
- 자식 노드부터 삭제해야 트리를 유지하면 재귀로 루트 노드까지 삭제할 수 있기 때문이다.
- 자식 노드부터 방문한다는 특성이 있는 후위 순회는 트리 삭제에 자주 활용된다.
4. 📌 이진 탐색 트리
이진 탐색 트리에서 가장 중요한 것은 탐색을 효율적으로 할 수 있도록 트리를 구축하는 것이다.
이진 탐색 트리 구축하기
데이터가 3, 4, 2, 8, 9, 7, 1 순서로 들어온다고 가정하자.
- 이진 탐색 트리는 데이터 크기를 따져 크기가 작으면 왼쪽 자식 노드로, 크거나 같으면 오른쪽 자식 위치에 배치하는 독특한 정렬 방식을 갖는다.
- 결과적으로 삽입과 동시에 정렬을 하면서 이진 탐색 트리가 구축된다.
이진 탐색 트리 탐색하기
- 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료하고 크면 오른쪽 노드를 탐색한다.
- 본인이 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드를 탐색한다.
- 값을 찾으면 종료한다. 노드가 없을 때까지 계속 탐색했는데 값이 없으면 현재 트리에 값이 없는 것이다.
배열 탐색과 비교하면 어떨까?
- 5가 없다는 것을 알기 위해 배열은 전체 모든 값에 대해 체크를 해야 하지만 이진 탐색 트리의 경우 2번만 비교 연산을 하면 알아낼 수 있다.
- 이진 탐색 트리의 경우 데이터 크기에 따라 하위 데이터 중 한 방향을 검색 대상에서 제외하므로 검색을 빠르게 만들어준다.
이진 탐색 트리의 시간 복잡도
- 이진 탐색 트리의 시간 복잡도는 트리의 균형에 의존한다.
- 트리의 균형이 잡혔다는 건 각 노드의 차수가 비슷하게 유지되면서 각 노드의 자식 노드 수가 비슷하게 유지되는 것을 말한다.
- 균형이 유지되었다고 가정하고 이진 탐색 트리에 저장된 노드가 $N$개라고 하면 삽입과 탐색 연산 시 시간 복잡도는 $O(logN)$이다.
- 균형이 맞지 않을 경우 시간 복잡도가 배열과 비슷하다.
- degenerate binary tree의 경우 탐색 시간 복잡도가 $O(N)$이다.
균형 이진 탐색 트리(balanced binary search tree)
세부적으로 AVL 트리, 레드-블랙 트리 등으로 구분하여 부른다. 균형 이진 탐색 트리를 활용하면 이진 트리의 탐색 연산 횟수가 트리 높으에 비례하고 트리의 높이는 $logN$이므로 탐색 시간 복잡도를 $O(logN)$으로 유지할 수 있다. 다만 균형 이진 탐색 트리 구현은 난이도가 너무 높아서 코딩 테스트에는 나오지 않을 가능성이 매우 높다.