이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조.
각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드를 가질 수 있음.

        A
       / \
      B   C
     / \
    D   E

특징
노드 수: 각 노드는 0개, 1개, 또는 2개의 자식 노드를 가질 수 있음.
구조적 다양성: 이진 트리는 균형 이진 트리, 완전 이진 트리 등 다양한 형태로 나뉠 수 있음.


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

이진 검색 트리는 이진 트리의 특수한 형태로, 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값이, 오른쪽 서브트리에는 큰 값이 위치하는 구조.

        4
       / \
      2   6
     / \ / \
    1  3 5  7

특징
검색 효율성: O(log n)의 시간 복잡도로 데이터를 검색할 수 있음 (균형 상태일 때).
정렬: 자동으로 정렬된 구조를 가짐.


힙 (Heap)

힙은 완전 이진 트리의 일종으로, 각 노드가 특정한 순서 속성을 가지는 구조.
최대 힙(Max Heap)에서는 부모 노드가 자식 노드보다 크거나 같고, 최소 힙(Min Heap)에서는 부모 노드가 자식 노드보다 작거나 같음.

특징
우선순위 큐: 힙은 우선순위 큐를 구현하는 데 자주 사용됨.
완전 이진 트리: 모든 레벨이 꽉 차 있고 마지막 레벨은 왼쪽부터 채워짐.
시간 복잡도: 삽입과 삭제는 O(log n), 접근은 O(1).

이진 힙 (Binary Heap)

이진 힙은 힙의 특성을 가지는 이진 트리로, 최대 힙과 최소 힙으로 나뉘며, 완전 이진 트리의 형태를 유지함.

      최대 힙
        10
       /  \
      9    8
     / \  / \
    7  6 5   4

      최소 힙
        1
       / \
      2   3
     / \ / \
    4  5 6  7

특징
최대/최소 값 접근: O(1)로 최대값(최대 힙) 또는 최소값(최소 힙)에 접근할 수 있음.
구현: 배열로 쉽게 구현할 수 있음.


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

레드-블랙 트리는 자가 균형 이진 검색 트리로, 각 노드가 빨간색 또는 검은색으로 표시됨.
특정 규칙을 통해 균형을 유지함.

        B
       / \
      R   R
     / \ / \
    A  C D  E

특징
균형 유지: 약간의 불균형을 허용하지만, 트리의 높이를 O(log n)으로 유지함.
효율적인 삽입/삭제: 삽입과 삭제 후에도 균형을 유지할 수 있도록 재구성됨.


B+ 트리 (B+ Tree)

B+ 트리는 B-트리의 변형으로, 모든 값이 리프 노드에만 저장됨. 내부 노드는 검색에만 사용됨.

          [ 10 | 20 ]
         /      |      \
     [5 | 8]  [15 | 18] [25 | 30]

특징
높은 차수: 많은 자식 노드를 가질 수 있어 디스크 I/O를 줄일 수 있음. 리프 노드 체인: 리프 노드가 연결되어 있어 범위 검색이 효율적임.


요약

데이터 구조 정의 특징
이진 트리 최대 2개의 자식 노드를 가지는 트리 구조적 다양성, 검색 비효율적
이진 검색 트리 정렬된 이진 트리 O(log n) 검색, 자동 정렬
힙 완전 이진 트리로 특정 순서 속성을 가짐 우선순위 큐로 사용, O(log n) 삽입/삭제
이진 힙 힙의 특성을 가지는 이진 트리 최대/최소 값 접근 O(1)
레드-블랙 트리 자가 균형 이진 검색 트리 O(log n) 균형 유지, 효율적 삽입/삭제
B+ 트리 모든 값이 리프 노드에 저장되는 B-트리 변형 높은 차수, 범위 검색 효율적

참고