Tree

• 계층적인 구조를 나타내기 위한 자료구조로, 하나의 루트(Root) 노드에서 시작하여 다수의 자식(Child) 노드를 가질 수 있으며, 각 자식 노드는 다시 하위 자식 노드를 가질 수 있는 구조이다.

노드

• 트리에서는 노드(Node)라는 개념이 중요한데, 각 노드는 데이터를 저장하는 역할을 하며, 다른 노드들과 링크(Link)로 연결되어 있다.
• 루트 노드는 트리의 시작점을 나타내며, 자식 노드는 부모 노드에서 링크로 연결된 하위 노드를 의미한다.

트리 구조

• 트리 용어
  • 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
  • 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
  • 내부(internal) 노드: 단말 노드가 아닌 노드
  • 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
  • 형제(sibling): 같은 부모를 가지는 노드
  • 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
  • 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
  • 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
  • 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
  • 트리의 차수(degree of tree): 트리의 최대 차수
  • 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

 

트리의 종류(이진 트리, 이진 탐색 트리, 균형 트리, 이진 힙)

이진 트리

• 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리
• 왼쪽 자식 노드와 오른쪽 자식 노드가 존재하며, 각 노드의 값은 키(Key)로 사용된다.

이진 트리

이진트리는 주로 검색 알고리즘, 정렬 알고리즘 등에 사용된다.

이진트리는 자료의 삽입, 삭제, 검색 등의 작업이 빠르게 수행될 수 있으며, 일반적으로 O(log n) 시간 복잡도를 가지는 알고리즘을 사용하여 이러한 작업이 수행된다.

 

이진 탐색 트리

• 이진 탐색 트리는 이진 트리의 일종으로, 모든 노드에서 왼쪽 자식 노드의 값은 현재 노드의 값보다 작아야 하고, 오른쪽 자식 노드의 값은 현재 노드의 값보다 커야 하는 특징이 있다.
• 이진 탐색 트리는 다음 조건을 모두 만족해야한다.
  • 노드의 왼쪽 서브트리에 있는 모든 노드의 키(key) 값은 해당 노드의 키 값보다 작다.
  • 노드의 오른쪽 서브트리에 있는 모든 노드의 키 값은 해당 노드의 키 값보다 크다.
  • 왼쪽 서브트리와 오른쪽 서브트리도 모두 이진탐색트리여야 한다.

이진트리 삽입

이진탐색트리는 데이터를 검색하는 데 효율적이다.

이진탐색트리에서는 노드를 검색할 때 현재 노드와 비교하여 찾고자 하는 노드가 현재 노드보다 작으면 왼쪽 서브트리를, 크면 오른쪽 서브트리를 탐색한다. 이러한 방법으로 검색 시간은 O(log n)으로 빠른 편에 속한다.

이진탐색트리는 삽입, 삭제, 검색 등의 작업도 빠르게 수행할 수 있으며, 이를 위해 일반적으로 재귀(recursive)적인 방법을 사용한다.

다만, 이진탐색트리의 구조가 한쪽으로 치우쳐질 경우, 트리의 높이가 길어져 검색 성능이 저하될 수 있어서, 이를 방지하기 위해 균형 이진탐색트리(AVL 트리, 레드-블랙 트리 등)를 사용하기도 한다.

이진 탐색 트리 활용 사례

1. 데이터베이스 인덱스: 데이터베이스에서 인덱스는 데이터 검색을 빠르게 하기 위한 자료구조이다. 인덱스는 이진 탐색 트리를 활용하여 구현되는데, 데이터베이스의 검색 성능을 높이기 위해서는 인덱스의 효율적인 사용이 필수적이다.
2. 자동 완성: 자동 완성 기능은 입력된 문자열을 이진 탐색 트리에 저장하여 검색할 때, 빠르게 일치하는 문자열을 찾아내는 방식으로 동작한다.
3. 알고리즘: 정렬 알고리즘 중 하나인 퀵 정렬에서는 피벗(pivot)을 이진 탐색 트리에 추가하여 정렬을 수행한다.

 

균형 트리

• 이진 탐색 트리의 성능을 개선하기 위한 자료구조, 균형 트리는 높이를 최소한으로 유지하는 자료구조
• 이진 탐색 트리는 삽입 순서에 따라 편향되어 불균형한 상태가 될 수 있어 탐색 시간이 선형적으로 증가하여 검색 성능이 저하된다.
• 균형 트리는 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 구성된다.
• 대표적인 균형 트리로는 AVL 트리, 레드-블랙 트리, B-트리 등이 있다.

 

AVL 트리

• 높이 균형을 유지하기 위해 삽입, 삭제 시에 회전 연산을 수행한다.

장점

• AVL 트리는 특정 연산 시간이 삽입과 삭제에서 최악의 경우에도 O(log n)이 되도록 보장한다.

단점

• 회전 연산이 빈번하게 일어나므로 실제 상황에서는 레드-블랙 트리 등의 다른 균형 트리가 더 많이 사용된다.
• 데이터가 많아지면 트리의 전체적인 높이가 증가한다.

 

레드-블랙 트리

레드-블랙 트리

• AVL 트리보다 조금 덜 균형을 유지하지만 회전 연산이 덜 필요하므로 성능이 더 우수하다.
• 레드-블랙 트리는 각 노드에 레드 또는 블랙 색을 부여하여 높이 균형을 유지한다.

장점

• 검색, 삽입, 삭제 연산이 모두 O(log n)으로 보장된다.
• 높이 균형을 유지하기 위해 적은 수의 회전 연산만 필요로 하기 때문에 AVL 트리보다 회전 연산이 덜 필요하며, 실제 상황에서도 높은 성능을 보인다.
• 새로운 노드를 삽입하거나 삭제하는 과정에서 빠른 균형 재조정이 가능하다.

단점

• AVL 트리보다 균형을 유지하는 정도가 약간 낮기 때문에, 삽입 및 삭제 연산에서 최악의 경우 균형을 맞추기 위한 회전 횟수가 더 많아질 수 있다.
• AVL 트리에 비해 조금 더 복잡한 규칙을 가지고 있어서 구현이 더 복잡할 수 있다.

 

B-트리

B-트리

• 대용량의 데이터를 저장할 때 사용되는 자료구조이다. 각 노드가 여러 개의 자식을 가지며, 이로 인해 각 노드의 키의 수가 다른 균형 트리와 달리 일정하게 유지된다.
• 균형을 유지하기 위해 노드의 삽입과 삭제에 대해 균형 재조정 연산을 수행한다. 이를 통해 데이터의 불규칙한 분포에도 불구하고 트리의 높이를 일정하게 유지할 수 있다.
• 대용량의 데이터 집합을 빠르게 검색할 수 있다.

장점

• B-트리는 대용량 데이터 처리를 위한 자료구조로 설계되어 있기 때문에 메모리의 한계를 초과하는 데이터도 처리할 수 있다.
• 노드의 크기가 상대적으로 작기 때문에, 디스크에서 데이터를 읽는 횟수가 줄어들어 빠른 속도로 데이터를 처리할 수 있다.
• 균형을 유지하기 위해 균형 재조정 연산을 수행하기 때문에 검색, 삽입, ㅅ가제 연산의 평균 시간 복잡도는 O(log n)이다.

단점

• B-트리의 구현이 복잡하다. 구현하기 위해 필요한 로직이 많아서 코드의 길이가 길어지고, 코드의 복잡도가 높아진다.
• 노드의 크기가 상대적으로 작기 때문에, 각 노드에 저장되는 키 값의 개수가 적어진다. 이로 인해 키 값이 매우 적을 때는 B-트리의 효율성이 떨어질 수 있다.
• 높은 가지의 수를 가진 B-트리의 경우에는 검색, 삭제, 삽입 연산의 속도가 느려질 수 있다.

 

이진 힙

• 이진 힙(Binary Heap)은 이진트리(Binary Tree)를 기반으로 하는 자료구조 중 하나로서, 최대값 또는 최소값을 빠르게 찾을 수 있도록 설계되었다.
• 이진 힙은 보통 배열(Array)을 이용하여 구현되며, 각 노드는 그 위치에 따른 인덱스(Index)를 가지게 된다.
• 이진 힙은 다음의 특징을 갖는다.
  • 완전 이진 트리의 형태를 가진다.
  • 최대값 또는 최소값을 O(1)의 시간 복잡도로 찾을 수 있다.
  • 삽입과 삭제의 시간 복잡도는 O(log n)이다.
  • Heapify 과정을 통해 배열을 이용한 초기화가 가능하다.

이진 힙

최대 힙

• 부모 노드가 항상 자식 노드보다 크거나 같은 값을 가지는 이진 힙
• 최대 힙에서는 루트 노드의 값이 최대값이 되며, 삽입(Insert) 연산은 새로운 값을 마지막 노드에 위치시킨 후 부모 노드와 값을 비교하며 상위 노드로 올라가면서 위치를 찾아가는 방식으로 이루어진다.
• 삭제 연산은 루트 노드를 삭제한 후, 마지막 노드를 루트 노드로 이동시키고, 삭제 노드들과 값을 비교하며 하위 노드로 내려가면서 위치를 찾아가는 방식으로 이루어진다.

최소 힙

• 부모 노드가 자식 노드보다 작거나 같은 값을 가지는 이진 힙
• 최소 힙에서는 가장 작은 값이 루트 노드에 위치하며 삽입 연산은 새로운 값을 마지막 노드에 위치시킨 후 부모 노드와 값을 비교하며 상위 노드로 올라가면서 위치를 찾아가는 방식으로 이루어진다.
• 삭제 연산은 루트 노드를 삭제한 후, 마지막 노드를 루트 노드로 이동시키고, 자식 노드들과 값을 비교하며 하위 노드로 내려가면서 위치를 찾아가는 방식으로 이루어진다.

최대 힙과 최소 힙은 우선순위 큐(Priority Queue)와 같은 자료구조에서 활용되며, 다익스트라 알고리즘(Dijkstra's Algorithm) 등과 같은 알고리즘에서 최소값 또는 최대값을 찾을 때 활용된다.

 

트리의 순회

• 트리의 순회는 루트 노드를 언제 방문하느냐에 따라 전위, 중위, 후위 순회로 분류된다.

전위 순회

전위 순회(preorder)는 다음과 같은 방법으로 진행한다.

1. 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.

전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다.

• 전위 순회: F, B, A, D, C, E, G, I, H (root, left, right)

중위 순회

중위 순회(Inorder)은 다음의 순서로 진행된다.

1. 왼쪽 서브 트리를 중위 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브 트리를 중위 순회한다.

중위 순회는 대칭 순회(symmetric)라고도 한다.

• 중위 순회: A, B, C, D, E, F, G, H, I (left, root, right)

후위 순회

후위 순회(postorder)는 다음과 같은 방법으로 진행한다.

1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 노드를 방문한다.

• 후위 순회: A, C, E, D, B, H, I, G, F (left, right, root)

---

출처

열혈 자료구조(윤성우)

위키백과 - 트리의 순회

[자료구조] 트리(Tree)란 - Heee's Development Blog (gmlwjd9405.github.io)

[자료구조] 트리(Tree)란 — 개발자 Miro (tistory.com)

[자료구조] 트리 (Tree) (velog.io)

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

B 트리 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

[Algorithm] 이진 힙 Binary Heap — 심심한 개발 블로그 (tistory.com)