이진트리

이진 트리

• 모든 노드가 최대 두개의 자식을 가지는 트리
• 하위 노드가 3개 이상이면 안되고 무조건 0, 1, 2개 있어야 한다!

완전 이진 트리

• 노드를 삽입할 때 최하단 왼쪽부터 차례로 삽입하는 이진 트리

 

완전 이진 트리를 배열로 표현

• BFS로 탐색을 할 때 왼쪽에서부터 읽어서 넣는다고 생각하자!

완전 이진 트리 노드 갯수

• 레벨을 n이라고 하면각 레벨에 최대로 들어갈 수 있는 노드의 수는 2^k개이다.

완전 이진 트리의 높이

• 트리의 높이는 루트 노드부터 가장 아래 리프노드 까지의 길이이다.
• 아래 같은 경우 2 - 0 = 2, 즉 높이가 2다

 

• 만약 높이가 h 일때, 최대 노드 갯수가 N이라고 하면 N = 2^(h+1) - 1개이다!
• N = 2^(h+1) - 1 → h = log2(N+1) - 1 으로 노드의 개수를 이용해 높이를 표현할 수 있다!

시간 복잡도

• 완전 이진 트리 노드의 개수가 N 일때 최대 높이가 log2(N+1) - 1이므로 높이만큼 탐색하는데 O(log(N))의 시간으로 처리할 수 있다!
• 즉, 선형 자료구조일 때 O(N)이였던 것이 이진탐색트리를 구성하면 O(logN)에 처리할 수 있다!