[Data Structure] 이진트리

turtleJ·2022년 6월 20일
0
post-thumbnail

이진트리(Binary tree)

모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진트리라 한다.

  • 서브 트리는 공집합일 수 있다.
  • 서브 트리 간의 순서가 존재해 왼쪽 서브 트리와 오른쪽 서브 트리로 구별된다.

이진트리의 성질

  1. n개의 노드를 가진 이진트리는 정확히 n-1개의 간선을 가진다.
  2. 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2^h - 1개의 노드를 가진다.
  3. n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소[log2(n+1)]이 된다.
    • 높이가 h인 이진트리가 가질 수 있는 노드의 최대값은 2^h - 1
    • 따라서 n <= 2^h - 1이 성립 양변에 로그를 취하면, h >= log2(n + 1)
    • h는 성수여야 함으로 h >= [log2(n + 1)] (대괄호는 올림 연산을 의미한다.)
profile
꾸준함을 무기로 성장하는 개발자가 되겠습니다.

0개의 댓글