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

이진 탐색 트리(Binary Search Tree)

• 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조
• 이진 탐색 트리의 특징
• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
• 부모 노드보다 왼쪽 자식 노드가 작다
• 부모 노드보다 오른쪽 자식 노드가 크다

 

 

이진 탐색 트리의 데이터 조회

• 찾고자 하는 원소 : 37
• [Step 1] 루트 노드부터 방문하여 탐색을 진행한다
• 현재 노드와 찾는 원소 37을 비교
• 찾는 원소가 더 크기 때문에 오른쪽 방문
• [Step 2] 현재 노드와 값을 비교한다
• 현재 노드와 찾는 원소 37을 비교
• 찾는 원소가 더 작기 때문에 왼쪽 방문
• [Step 3] 현재 노드와 값을 비교
• 현재 노드와 찾는 원소 37을 비교
• 원소를 찾았으므로 탐색을 종료

• 이처럼, 이진 탐색 트리를 이용해서 데이터를 조회할 경우 이상적인 경우 O(log(n))