5. 이진 트리 Binary Tree(2)

학교 수업 '자료구조' 복습입니다.

        Binary Tree 구현(Link를 사용한 Implementation)

• 방법 1 : 리프 노드와 내부 노드를 똑같이 구현한다.

interface BinNode<E> {
    E getItem();
    BinNode<E> left();
    BinNode<E> right();
}

• 해당 방법으로 구현시, null 값의 개수가 node의 개수 + 1 개 이다.
• 방법 1의 space overhead
  *space overhead란? total space(사용 메모리의 총량) - data space(담고자하는 데이터를 위한 메모리 사용량)
  위 그림)
  데이터 A,B,C,D,E,F,G,H,I -- 9개의 data space
  total space -- 9 * data + 9 * 2 * pointer
  space overhead = 9 * 2 * pointer
  *Overhead fraction = (space overhead) / (total space) 
  overhead fraction = 18pointer / (9data + 18pointer)
• 데이터를 리프 노드에만 넣는 경우는 어떻게 하는가? ( 토너먼트 같은 경우 )
  해당 경우, space overhead가 엄청 늘어나게 될 것이다.
  예) full tree이고, 내부 노드와 리프 노드를 똑같이 구현하는 경우 (2개의 포인터 1개의 데이터)
  Total space : (2P + D)n
  Overhead : 2Pn
  P = D 인 경우, overhead fraction = 2P/(2P+D) = 2/3 (사실상 메모리의 2/3이 의미없이 차지 되고 있음.)
• Overhead를 어떻게 줄일까?
  리프 노드의 child pointer를 제거하면 어떨까?
  (class를 leaf node, internal node를 나눠서 만들면 어떨까?)
• 방법 2의 리프 노드와 내부 노드를 다르게 구현한다.
  Overhead  fraction : P / (P + D) 
  P = D 인 경우 overhead fraction : 1/2

---

        Array Implementation (for Complete Binary Tree)

• 규칙
  부모의 위치 * 2 = 부모의 왼쪽 자식
  부모의 위치 * 2 + 1 = 부모의 오른쪽 자식
  자식의 위치 / 2 = 부모의 위치
  Parent(r) = floor(r/2)
  Leftchild(r) = 2r
  Rightchild(r) = 2r + 1
  Leftsibling(r) = r - 1 (r이 홀수인 경우)
  Rightsibling(r) = r + 1 (r이 짝수인 경우)
• Space Overhead = 1 ( 매우 효율적 )