[Data Structure] Binary Search Tree(BST)

Binary Search Tree(BST)

- 이진 탐색 트리

- 데이터를 효율적으로 저장, 검색, 삽입, 삭제하기 위해 사용되는 일종의 트리 자료구조

- 각 노드가 최대 두 개의 자식 노드를 가진다.

 

특징

- 왼쪽 자식 노드 : 부모 노드의 값보다 항상 작거나 같은 값을 가진다.

- 오른쪽 자식 노드 : 부모 노드 값보다 큰 값을 가진다.

- 탐색 : 위 같은 규칙을 통해 특정 값을 찾을 때마다 탐색 범위가 절반씩 줄어들어 평균적으로 O(logN)의 시간 복잡도를 가진다.

 

 

용도

- 인 메모리 데이터 관리에 사용