오늘은 자료구조 중 하나인 트리구조에 대해서 알아봤다.
개념적인 것은 다른 블로그에 잘 정리돼 있으므로 부가적인 개념을 여기에 작성해볼려 한다.
일단 오늘 복습한 내용
- 트리의 종류
일반트리 - 이진트리 - 트리의 성질
- 트리의 분류
포화이진트리 - 완전이진트리 - 트리의 표현
배열 표현법 - 리스트 표현법 - 트리의 순회방법
전위순회 - 후위순회 - 중위순회 - 이진 탐색 트리
트리의 높이에 관한 고찰
총 n개의 노드가 있다면, 최대 높이가 n이 되고 최소 높이는 log(n+1) 이다.
포화이진트리에서 전체 노드의 개수는 2의 등비수열의 합이 된다.
즉 2^n+1 - 1이 된다. 여기서 n+1이 트리의 높이가 된다.
그러므로 이진트리의 최소 높이는 노드의 개수를 n이라고 했을 때 n을 2의 등비수열의 합이라고 가정하고 log를 씌우면 된다.
(h는 높이)
n = 2^h - 1
n+1 = 2^h
logn+1 = log2^h
logn+1 = h
