[자료구조] 06. 이진 탐색 트리 (Binary Search Tree)

12 Oct 2019 in Computer-Science

이진 탐색 트리 (Binary Search Tree)의 정의와 특징에 대하여 알아보고 사용예시를 살펴본다.

1. 정의

이진 탐색 트리는 다음의 두 가지 조건을 만족하는 형태의 트리이다.

1. 노드의 최대 Branch가 2인 트리(이진 트리)
2. 선택한 노드를 기준으로 왼쪽 노드는 선택한 노드보다 작고, 오른쪽 노드는 선택한 노드보다 큰 값을 가짐

2. 특징

데이터를 탐색할때 탐색속도가 빠르다.

3. 시간 복잡도

• depth(h) 기준 : O(h)
• 노드의 개수(n) : O(logn)