Binary Tree   이진 트리

1. 이진 트리 (Binary Tree)

  ㅇ 모든 노드의 차수/자식이 2 이하(최대 2)인 특수한 형태의 순서 트리
     - 자식이 0,1,2개 만을 갖음 (빈 트리도 유효한 이진 트리임)


2. 이진 트리의 특징

  ㅇ 각 노드의 차수가 2 이하의 자식 노드를 갖음
     - 자식 노드가 좌,우로 구분됨
  ㅇ 이진 트리는 순서 트리 임
     - 노드 위치 및 순서가 중요한 의미를 갖음
        
  ㅇ 루트 노드 레벨(level)은, 0 으로 함
  ㅇ 레벨 깊이(depth) i일 경우, 갖을 수 있는 최대 노드 수는, 2i - 1


3. 이진 트리의 종류

  ㅇ 전 이진 트리, 포화 이진 트리 (Full Binary Tree)
     - 각 레벨에 노드들이 꽉 차있는 이진 트리
        . 모든 노드의 차수/자식이 2 이어야 함
     - 즉, 각 레벨이 허용되는 최대 차수(최대 자식 노드 개수)를 갖음
     - 단, 마지막 레벨(단말 노드)은 비어있을 수가 있음 

  ㅇ 완전 이진 트리 (Complete Binary Tree)
     - 부모, 왼쪽 자식, 오른쪽 자식 순으로, 채워지며 만들어지는 이진 트리
        . 또는, 포화 이진 트리의 맨아래 단말 노드들을 오른쪽부터 하나씩 제거하여 얻어지는 트리
     - 마지막 레벨을 제외하고는, 각 레벨의 노드들이 모두 차 있음
        . 마지막 레벨에서는, 노드가 꽉 차있지 않아도 되지만, 중간에 빈 곳이 있으면 안됨
     - 여기서, 완전(complete)은, 
        . 부모가 자식을 왼쪽부터 채운다는 말임  ☞ 순서 트리 참조

  ㅇ 이진 힙 (Binary Heap)
     - 포화 이진 트리의 일종
        . 부모,자식 간에는 대소 관계가 있으나, 형제들 간에 대소 관계가 정해지지 않음
        . 이에따라, 부분 순서 트리(Partial Ordered Tree) 라고도 함

  ㅇ 균형 트리 (Balanced Tree)
     - 이진 트리에서 하위 노드 구조가 좌우 대칭이 되도록 한 것 (例, B-tree)


4. 이진 트리의 표현, 구현

  ㅇ 선형 자료구조인 `일차원 배열`로써 표현, 구현
     - 저장 공간 활용 비효율적, 부모 자식 노드 구분이 어려움
     - 다만, 완전이진트리에는 좋은 성능을 갖음
     - 프로그램 구현 용이

  ㅇ 비선형 자료구조인 `연결 리스트`로써 표현, 구현 
     - 저장 공간 효율적 활용 등으로 보다 유용함


5. 이진 트리의 순회 (Binary Tree Traversal)                                   ☞ 트리 순회 참조

  ㅇ 각 노드를 한번씩 만 방문하며 저장 정보를 확인하는 것

  ㅇ 순회 종류 : 방문 순서에 따른 구분
     - 중위 순회 (Inorder)  : 왼쪽 서브트리 → 자신 → 오른쪽 서브트리
     - 후위 순회 (Postorder)
     - 전위 순회 (Preorder)


6. 이진 트리의 응용

  ㅇ 이진 검색 트리 (Binary Search Tree, BST)
     - 이진 트리 구조를 갖으나, 자료의 검색,삭제,삽입에 효율적이게 한 트리 자료구조
     - 각 노드는 2개의 자식 노드를 각각 가리키는 2개의 포인터를 갖음

  ㅇ AVL 트리 (AVL Tree, Adelson-Velskii and Landis's Tree)
     - 한 노드를 중심으로 좌우 부분의 트리 높이(height)의 차가 1 이하가 되도록 하는 이진 탐색 트리
     - 가장 초기에 나온 균형 잡힌(Balanced) 이진 탐색 트리 

  ㅇ B 트리 (B-Tree, Balanced Tree)
     - 이진 탐색 트리를 보다 일반화시킨 트리 자료구조를 말함
     - 데이터베이스 및 파일시스템에 널리 쓰이는 자료구조

  ㅇ 한편, 
     - 이진 검색 트리 : 최대 2개의 자식 노드를 가질 수 있음
     - 다진 검색 트리 : 최대 3 이상의 자식 노드를 갖는 검색 트리 (k진 검색 트리)