여러가지 트리

전위순회

후위순회

중위순회

 

 

결정트리(Decision Tree)

 

internal node: 질문지

external node: 선택지

 

 

 

 

완전이진트리의 특징

 

모든 Internal Node(자식)의 수가 2일 때

external node의 수 = internal node의 수 +1

총 노드 수 = 2 * external node의 수 - 1

height ≤ internal node의 수 (left or right node로만 이루어진 트리일 때 가장 큼)

height ≤ (총 노드 수 - 1) / 2

external node의 수 ≤ 2^height

height ≥ log2e

h ≥ log2(n+1) - 1 ⇒ 시간 복잡도 하한 O(logn))

 

 

이진탐색트리

 

중위 순회를 사용하면, 오름차순으로 데이터 visit 가능

최악: O(n)

최선: O(logn)

 

 

 

자가균형이진탐색트리(AVL Trees)

 

트리의 높이는 logn

모든 연산의 수행 시간이 O(log n) time

출처: 위키백과

 

 

 

레드-블랙 트리

 

AVL 트리의 한 종류. 

자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다.

트리에 n개의 원소가 있을 때 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.

출처: 위키백과