[Python] 자료구조 - 트리

[Python] 자료구조 - 트리

---

 

 

이진트리와 이진 탐색 트리 (Binary Search Tree)

 

• 이진트리의 자료구조를 만드는 과정은 글로 설명하기보다 다음 그림처럼 이진 탐색트리를 만드는 과정을 통해 보도록 하겠다.
• 이진트리를 구성하는 방법은 다양하다. 그 중 이진 탐색트리의 예시는 다음과 같이 생성된다
• 이진 탐색트리란 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지게끔 구조를 생성하는 것이다.

 

출처:  www.mathwarehouse.com

 

 

이진트리 자료구조에서 Binary Search vs 정렬된 array에서의 Search

 

출처:  www.mathwarehouse.com

총 노드수를 n이라고 했을 때, 특정값을 Searching 할 때 발생하는 시간복잡도를 고려해보면,

Binary Search Tree에서의 시간복잡도는 일반적으로 O(log_2(n))입니다.

(∵ 트리의 깊이를 h라 하면, 시간복잡도는 O(h)이다. 그리고 n = 2^h - 1 = 2^0 + 2^1 + … + 2^h-1 로부터,

n ≒ 2^h (h ≒ log_2(n)) 가 성립하기 때문입니다.)

Sorted array에서의 시간복잡도는 일반적으로 O(n)이다.