[DS] 이진트리(Binary Tree)와 완전이진트리 (Complete Binary Tree)

이진트리

  모든 노드들의 자식 노드가 두 개 이하인 트리

  자식 노드는 Sub Tree라고 볼 수 있다.

  자식 노드를 왼쪽 노드(Left Node/Left Sub Tree)와 오른쪽 노드(Left Node/Right Sub Tree)로 구분함

 

완전 이진트리

  이진트리의 일부

  단말 노드(Leaf)를 제외한 나머지 노드가 2 개의 자식 노드를 가지고 있는 트리 

 

완전이진트리의 특성

  특정 높이 k에 있는 최대 노드 개수는 2^(k-1)  

  높이가 h인 포화이진트리의 노드 개수는 2^h -1

  노드 개수(N)과 높이(h)의 관계 -> h = Log2(N+1)

  Array에 저장된 경우 추가적인 특성이 존재

    Left Child와 Parent의 관계 -> (Left Child Index) = (Parent Index * 2)

    Right Child와 Parent의 관계 -> (Right Child Index) = (Parent Index * 2)

    위의 특성들은 Root의 Index가 1일 때만 성립

 

해당 내용은

Data Structure에서 가장 기본적인 내용이라 볼 수 있다.

하지만, 면접으로 해당 질문이 들어왔을 때

오랜만에 들어서인지 설명이 미숙하다는 느낌을 받았다.

그래서 정리하는 차원해서 포스팅 해보았다.