이진 트리 (Binary Tree)

각각의 노드의 자식노드 수가 2개 이하로 구성되어 있는 트리

1. 정이진 트리(Full Binary Tree) : 자식 노드가 0 또는 2개인 이진트리, 잎새노드를 제외한 모든 노드가 자식노드를 2개 가진 트리

        1
       / \
      2   3
     / \
    4   5

 

2. 완전 이진 트리 (Complete Binary Tree) : 왼쪽부터 채워져 있는 이진 트리

           마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있고 마지막 래밸의 경우 왼쪽부터 채워져 있음

                   1
                /    \
              2        3
            /   \     /   \
          4      5   6     7
         / \
        8   9
       /
      10

 

3. 변질 이진 트리 (Degenerate Binary Tree) : 리프노드 제외 , 자식 노드가 하나밖에 없는 이진트리

        1
         \
          2
           \
            3
             \
              4

 

4. 포화 이진 트리 (Perfect Binary Tree) : 모든 노드가 꽉 차 있는 이진 트리

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

 

5. 균형 이진 트리 (Balanced Binary Tree) : 모든 노드에 대해 , 그 노드의 왼쪽하위 트리와 오른쪽 하위 노드의 높이 차이가 1이하인 이진 트리 , 즉 트리의 어느한쪽이 지나치게 치우치지 않도록 구조가 유지된 트리// 그 구조 덕분에 탐색, 삽입, 삭제 등의 연산에서 시간 복잡도가 O(log N)으로 보장될 수 있다

  // 균형이진트리의 높이 차이는 각 하위 트리의 전체 높이를 기준을 계산(e.g. 한 노드의 왼쪽 하위 트리의 높이가 1이고 오른쪽 하위 트리의 높이가 0이면 이 노드의 하위트리 높이 차이는 1이다)

                4
              /   \
            2       8
          /  \     /  \
         3    -   6    9
             / \  / \
            5   7 -  -

 

6. 레드-블랙 트리(Red-Black Tree)는 균형 이진 트리의 한 예로, 자가 균형을 유지하기 위한 특정한 규칙들을 갖춘 이진 탐색 트리.  이 규칙들덕분에 레드-블랙트리는 최악의 경우에도 효율적인 연산을 보장하며,C++의 std::map과 std::set 같은 데이터 구조의 내부 구현에 사용됨

특징: 노드가 빨간색(Red) 또는 **검은색(Black)**으로 색칠됩니다.

• 균형 규칙:
  1. 각 노드는 빨간색 또는 검은색
  2. 루트 노드는 항상 검은색
  3. 모든 리프 노드는 검은색(NULL 노드 포함).
  4. 빨간색 노드의 자식은 반드시 검은색 (연속된 빨간색 노드 불가).
  5. 루트 노드에서 모든 리프 노드까지의 경로에 있는 검은색 노드의 수가 동일

        (B) 7
       /    \
     (R) 3   (B) 18
       /       \
     (B) 1      (R) 22

 

 

정리

트리 종류정의특징

정 이진 트리	자식 노드가 0 또는 2개인 이진 트리	한 노드에 자식이 하나만 있는 경우 없음
완전 이진 트리	마지막 레벨을 제외하고 모든 레벨이 채워져 있으며 왼쪽부터 채움	노드를 왼쪽부터 차례로 채움
변질 이진 트리	각 노드에 자식 노드가 하나만 있는 이진 트리	구조가 연결 리스트와 유사
포화 이진 트리	모든 노드가 자식 2개를 가지고 리프 노드가 동일한 레벨에 존재	모든 레벨이 완벽하게 채워짐
균형 이진 트리	왼쪽과 오른쪽 하위 트리의 높이 차이가 1 이하인 트리	연산의 시간 복잡도가 O(log N)으로 보장됨
레드-블랙 트리	균형을 유지하는 규칙을 가진 이진 탐색 트리	탐색, 삽입, 삭제의 시간 복잡도가 O(log N)으로 보장