트리에 대한 연구와 다양한 트리의 종류 쓰는중

트리(Tree)는 노드(Node)와 엣지(Edge)로 이루어진 자료구조로, 계층적인 구조를 가지며 그래프의 한 종류이다.

컴퓨터 과학 분야에서는 탐색에 대한 시간복잡도를 줄이기 위한 다양한 종류의 트리가 연구되어왔다. 이를 연구된 연도 순으로 나열해보면 다음과 같다.

1. 이진 검색 트리(Binary Search Tree) - 1960년대
2. AVL 트리 - 1960년대 후반
3. B-트리(B-tree) - 1970년대
4. 레드-블랙 트리(Red-Black Tree) - 1970년대 후반
5. 2-3 트리(2-3 Tree) - 1970년대 후반
6. 스플레이 트리(Splay Tree) - 1985년
7. 힙(Heap) - 1986년
8. 트라이(Trie) - 1950년대 이후로 연구되었으나, 1990년대에 효율적인 구현 방법이 제안됨
9. B+트리(B+ Tree) - 1990년대
10. R*-트리(R-star Tree) - 1990년대 후반
11. LSM 트리(Log-Structured Merge Tree) - 1996년
12. k-d 트리(k-dimensional Tree) - 1970년대 이후로 연구되었으나, 2000년대 이후로 더욱 활발한 연구 진행 중
13. 해시 트리(Hash Tree) - 2000년대 이후

위의 트리들은 각각의 특징에 따라 특정한 상황에서 더 효율적으로 사용될 수 있으며, 각각의 시간 복잡도 또한 다르다. 따라서 어떤 트리를 선택할지는 사용하려는 상황과 데이터의 특성 등에 따라 결정되어야 한다.

이진 검색 트리 (Binary Search Tree, BST)

• 1960년대 초반에 개발됨
• 이진 검색 트리는 이진 트리의 일종으로, 왼쪽 서브트리는 현재 노드의 값보다 작은 값을, 오른쪽 서브트리는 현재 노드의 값보다 큰 값을 가지도록 구성됩니다. 이러한 구성으로 탐색 속도를 빠르게 할 수 있습니다.
• 평균적으로 O(log n)의 시간 복잡도를 가지나, 트리의 균형이 맞지 않는 상태 중 최악의 경우 O(n)의 시간 복잡도를 가진다.

AVL 트리 (AVL Tree)

• 1962년에 개발됨
• AVL 트리는 균형 이진 트리의 일종으로, 모든 노드의 서브트리의 높이 차이가 1 이하인 트리입니다. 이러한 균형은 삽입, 삭제 시에도 유지되어 탐색 속도가 빠릅니다.

B 트리 (B-Tree)

• 1970년에 개발됨
• 이진 검색 트리와 유사하지만, 자식 노드의 수가 2개 이상입니다.
• B 트리는 대용량 데이터 처리에 효과적인 자료구조로, 여러 개의 키와 자식을 가진 노드로 구성됩니다. 키의 개수에 따라 노드의 크기가 다르며, 한 노드에서 탐색할 수 있는 범위가 넓어 탐색 속도가 빠릅니다.

레드-블랙 트리 (Red-Black Tree)

• 1972년에 개발됨
• 균형 이진 트리의 일종으로, 모든 노드가 레드 또는 블랙 색상을 가집니다. 삽입, 삭제 시에도 균형을 유지하며 탐색 속도가 빠릅니다.
• O(log n)의 시간 복잡도를 가진다.

2-3 트리

• 연구 연대: 1970년대 후반
• B-트리의 변형 중 하나입니다. 2-3 트리는 각 노드에 2개 또는 3개의 자식 노드를 가지며, 노드의 삽입과 삭제 시 노드를 분할하거나 병합하여 트리의 균형을 유지합니다.
• B-트리와 비슷한 대용량 데이터 처리용 트리입니다. 2개 또는 3개의 자식 노드를 가지며, 높이 균형을 맞추어 탐색 시간을 최소화합니다. 탐색 시간 복잡도가 일반적으로 O(log n)입니다.

스플레이 트리

빈번한 연산이 이뤄지는 노드를 루트로 옮겨서 트리 균형을 맞추는 이진 탐색 트리

힙(Heap)

• 연구 연대: 1960년대
• 최솟값 또는 최댓값을 빠르게 찾을

트라이(Trie)

• 연구 연대: 1950년대
• 문자열 탐색에 효율적인 자료구조로 사용됩니다. 키 값을 각 노드의 문자열 일부로 사용하여 자식 노드를 생성합니다. 탐색 시간 복잡도가 O(k), 여기서 k는 키의 길이입니다.