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

이진 탐색 트리(Binary Search Tree)

이진 탐색과 연결 리스트를 결함한 자료구조의 일종으로, 탐색 작업을 효율적으로 할 수 있다.

 

이진 탐색 트리의 특징

• 이진 트리 구조로 이루어져 있다.
• 노드의 왼쪽 서브 트리에는 노드 값보다 작은 값이 포함되어 있고, 오른쪽 서브 트리에는 노드 값보다 큰 값이 포함되어 있다.
• 서브 트리 또한 이진 탐색 구조로 이루어져 있다.
• 모든 원소의 키는 유일한 키를 가진다. (중복 값이 없다.)

 

이진 탐색 트리를 사용하는 이유

트리를 사용하는 이유는 일반적으로 데이터를 빠르게 탐색하기 위해 사용한다.

선형 자료구조에서는 하나의 데이터 뒤에 오직 하나의 데이터만 존재한다. 때문에 특정 값을 탐색할 때 맨 끝까지 순차적으로 탐색하는 최악의 경우에 시간 복잡도가 O(n)이 된다.

반면에 이진 탐색 트리는 부모 노드를 기준으로 좌우 데이터 값을 다르게 갖는 특징을 통해 데이터를 탐색할 때 최적의 경우 시간 복잡도가 O(logN)이 된다.