[알고리즘/C++] - 트리(Tree)

위 위 슈워메리 크리스마스

위 위 슈워메리 크리스마스

위 위 슈워메리 크ㄹ스마스

 

엔 어 해 피 뉴 이어..

사실 뉴 이어라고 하기엔 7월은,, 너무 중간이네요 

 

아무튼 오늘 배울 내용은 Tree 구조입니다

반응형

---

트리의 탄생 - 비선형 자료구조의 필요성

리스트나 배열 등의 자료구조만으로는 순차적으로 데이터가 저장되지 않는 등의 상황에서의 데이터 관리가 어려웠던 문제로 인해 새롭게 두 개의 자료구조가 탄생했습니다.

저장되는 데이터들이 계층적인 구조를 가진 경우, 

노드와 노드를 연결하는 간선으로 구성되는 경우,

두가지로 추가적인 데이터를 관리하는 자료구조가 그렇게 탄생하게 됩니다.

트리란?

위 두가지의 자료구조 중, 계층적 구조를 가진 것이 바로 트리입니다.

트리란, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프입니다.

여기서 말하는 노드는 트리의 데이터를 저장하는 원소의 단위.를 의미하고,  노드와 노드를 연결하는 간선인 에지 를 통해 데이터 간 부모-자식 계층 관계를 나타내고 데이터가 이동하고 검색되는 등의 순회가 진행됩니다.

 

쉽게 말해, 부모-자식간의 관계들로 이루어진 가계도 등의 구조들을 트리라고 합니다.

그리고 이런 트리에는 여러가지 종류가 있습니다.

우리가 자주 프로그래밍에 사용될 트리는 이진트리이며, 이진트리는 완전 이진트리와 탐색이진트리로 구분됩니다.

그리고 완전이진트리와 탐색이진트리는 완전히 둘로나뉘는 것이 아니고 두가지 성질을 모두 가진 트리가 존재하기도 합니다.

간단하게 이에 대한 상관관계를 아래 그림을 통해 표현해보았습니다!

이진 트리

이진트리란 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 합니다.

왼쪽 트리는 가장 상위층의 노드가 세개의 자식노드를 가지고 있지만, 오른쪽 노드는 모든 노드가 최대 2개의 노드를 가집니다.

이것이 이진트리입니다.

장점

1. 구현의 간단함: 이진트리는 구조가 단순하여 구현이 쉽습니다.
2. 효율적인 탐색: 평균적으로 O(log n) 시간 복잡도로 탐색, 삽입, 삭제가 가능합니다.
3. 트리의 균형 유지: 균형 이진트리는 삽입과 삭제 후에도 성능을 유지합니다.
4. 다양한 응용: 다양한 자료구조와 알고리즘에 활용됩니다.

단점

1. 편향 트리 문제: 불균형한 트리는 최악의 경우 O(n) 성능을 보입니다.
2. 공간 효율성 문제: 자식 노드 포인터 때문에 공간 효율이 떨어질 수 있습니다.
3. 복잡한 균형 유지: 균형을 유지하려면 추가 로직이 필요합니다.
4. 트리의 재구성: 삽입, 삭제 시 트리를 재구성해야 할 수 있습니다.

전체적으로 예외적인 상황을 제외하고는 이진트리는 상당히 많은 분야에서 유용하게 쓰이므로, 다양한 자료구조와 알고리즘에서 이진 트리를 활용하곤 합니다.

- 완전 이진 트리

완전이진트리는 이진트리의 한 종류로, 두가지의 조건이 만족합니다.

1. 트리의 모든 레벨이 가득 차 있어야 한다.

2. 마지막 레벨은 왼쪽에서 오른쪽으로 순서대로 채워져야 한다.

 

이미지의 왼쪽 트리는 마지막 레벨이 가득 차 있지 않으므로, 그냥 이진트리이지만, 오른쪽의 트리의 경우 모든 레벨이 가득 차 있기 때문에 완전 이진 트리입니다 (모든 데이터가 왼쪽에서 오른쪽으로 순서대로 채워졌다는 가정 하에)

- 이진 탐색 트리

이진탐색트리는, 마찬가지로 이진트리의 한 종류이며, 각 노드의 왼쪽 자식노드는 현재노드보다 작고, 오른쪽 노드는 현재노드보다 크다는 특징을 가집니다.

이진 "탐색"트리라는 이름을 가진만큼 이런식의 트리 구조는 효율적인 검색이 가능합니다!

 

...

그리고 이러한 이진 탐색트리를 구성하는 방법에는 여러가지가 있으며, 대표적인 방법으로는

AVL, 레드-블랙 트리가 있습니다. 

둘의 모습을 이미지를 통해 확인해보도록 하겠습니다.

순서대로 2,1,5,6,3,2를 넣은 모습입니다. 

red-black트리(왼) AVL트리(오)

 

둘은 모두 "자가 균형 이진 탐색 트리"를 가지지만, 위의 그림을 보면 구조가 조금 다릅니다. 둘은 균형을 유지하는 기준이 다르기 때문입니다.

각각의 특징을 살펴보도록 하겠습니다.

Red_Black트리

각 노드가 그림처럼 말 그대로 블랙, 레드의 색을 가지며, 최상단의 루트노드는 항상 블랙입니다. 레드의 자식은 항상 블랙이고, 어떤 노드를 지정하든 해당 노드에서 루트 노드까지 경로를 진행하는 과정에서 만나게 되는 블랙 노드의 수가 모두 같습니다. 

생각보다 복잡한 규칙을 가지고 있지만 간단하게 보드게임을 하고있다,,라고 생각하며 규칙을 이해해보고자 하면 조금은 이해가 될 것 같습니다.

이 트리구조는 평균적으로 자주 일어나는 삽입 및 삭제 과정의 경우에 대해 성능이 탁월합니다. 

사용 예: set, map와 같은 표준 라이브러리 컨테이너

AVL트리

각 노드의 왼쪽 및 오른쪽 서브트리의 높이 차이가 최대 1입니다. 절대 위 레드-블랙 트리처럼 2레벨이상의 차이가 나지 않습니다. 만약 이 차이 조건이 위배되는 경우에 균형을 위한 회전 연산을 수행합니다. 

때문에 삽입이나 삭제 연산이 실행되면 그 노드로부터 루트까지의 모든 노드 안에서의 균형 재조정이 진행됩니다.

이런 엄격한 균형 재조정으로 인해 검색 작업이 빠르게 이루어집니다.

사용 예: 데이터베이스 인덱스 등의 읽기 작업이 빈번한 캐싱 시스템

 

 

Red_Black트리는 비교적으로 엄격하지는 않은 정렬 기준을 가져 삽입 및 삭제의 과정에서 큰 회전을 필요로 하지 않아, 엄격한 기준으로 인해 모든 삽입 및 삭제에서 전체회전을 진행하는 AVL트리에 비해 높은 효율을 보이지만, 반면 특정 값을 검색하는 과정에서는 미리 정렬된 AVL이 더 높은 효율을 보입니다. 
때문에 두 트리 중 어떤 작업을 더 많이 진행할지를 고려하고 구조를 설계하는 것이 좋을 것 같습니다.

 

 

---

이해를 도울 수 있도록 트리구조에서 사용되는 용어모음을 공유합니다.

+용어모음

Node:  트리에서 데이터를 저장하는 기본 요소

Edge: 각 Node들이 연결된 선

Root Node: 트리 맨 위에 있는 노드

Level: 최상위 노드를 Level 0으로 했을 떄, 하위 Branch로 연결된 노드의 깊이를 나타냄 (==층)

Parent Node: 어떤 노드의 다음 레벨에 연결된 노드

Child Node: 어떤 노드의 상위 레벨에 연결된 노드

Leaf Node: Child Node가 하나도 없는 노드

Sibling: 동일한 Parent Node를 가진 노드

Depth: 트리에서 Node가 가질 수 있는 최대 Level

 

+이외의 트리들

힙 (Heap)

• 구조: 완전 이진 트리의 일종으로, 최대 힙의 경우 부모 노드가 자식 노드보다 크고, 최소 힙의 경우 부모 노드가 자식 노드보다 작음.
• 용도: 우선순위 큐 구현 등에 사용

트라이 (Trie)

• 구조: 노드가 문자열의 문자들을 저장하는 트리 구조.
• 용도: 문자열 검색 및 자동 완성 기능 구현에 사

B-트리 (B-Tree)

• 구조: 이진 트리의 일반화로, 노드가 여러 자식을 가질 수 있음.
• 용도: 데이터베이스 및 파일 시스템에서 대용량 데이터 검색에 사용.

이 외에도 여러가지의 트리들이 존재하니 궁금하신 분들은 아래 레퍼런스를 참고하여 공부해보시면 좋을 것 같습니다.

도움이 되었길 바라며 그럼 저는 20000!!

---

참고자료

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

트리 구조 - 위키백과, 우리 모두의 백과사전