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

1. 이진탐색트리 1.1 이진탐색트리란? 이진탐색트리(BST: Binary Search Tree)는 이진트리 기반의 탐색을 위한 자료구조이다. 이진탐색의 효율적인 탐색 능력을 가지며, 삽입과 삭제가 가능한 것이 특징이다. 1.2 이진탐색트리의 4가지 조건 모든 노드는 유일한 키를 갖는다. 왼쪽 서브트리의 키들은 루트의 키보다 작다. 오른쪽 서브트리의 키들은 루트의 키보다 작다. 왼쪽과 오른쪽 서브트리도 이진탐색트리이다. 1.3 이진탐색트리 특징 이진탐색트리를 순회할 때는 중위순회(In-order Traversal) 방법을 사용한다. (왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순서) 이진탐색트리를 중위 순회한 결과는 트리 내의 모든 값들을 오름차순으로 정렬한 결과를 나타낸다. 예를 들어 위 그림의 트리를..