binary search Tree란❓

• 바이너리 트리 중에서 트리의 데이터가 노드를 기준으로 왼쪽은 작은 값을, 오른쪽은 큰 값을 가지고 있는 트리를 바이너리 서치 트리 (Binary search tree), 또는 이진 탐색 트리라고 한다.

• 각 노드의 왼쪽 서브트리는 해당 노드의 값보다 작거나 같은 값을 가진다.
• 각 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값을 가진다.
• 왼쪽과 오른쪽의 서브트리는 또한 각각 이진 탐색 트리의 형태를 유지하고 있다.
• 어떤 값을 찾을 때 root 에서부터 두 갈래 길을 선택해서 가다 보면 그 값을 찾을 수 있다. 찾으려는 값과 비교해서 작으면 왼쪽, 크면 오른쪽으로 내려가면서 탐색한 다

DFS와 BFS

바이너리 서치 트리를 순회하는 방법에는 DFS(깊이 우선 탐색, Depth-First Search)와 BFS(너비 우선 탐색, Breadth-First Search) 두 가지가 있다.

• DFS : 루트를 시작으로 점차 깊이 들어갔다가 가장 깉은 depth에 도달했을 때 다시 나오고, 또다시 깊이 들어가는 방식을 반복하며 전체 트리를 순회한다.
• BFS : sibling을 먼저 탐색하고, 그 후 다음 depth로 들어가 해당 depth의 sibling을 탐색하는 식으로 전체 트리를 순회한다.

Binary Tree Traversals(트리의 3가지 순회방법)

바이너리 트리는 순회 방법에 따라 테이터 출력 순서가 달라진다.

아래 세 가지 검색 방법은 모두 깊이 우선 검색(Depth-First Search : DFS)에 속한다.

• Inorder : Left - Root - Right 순으로 탐색
• Preorder : Root - Left - Right
• Postorder : Left - Right - Root

BST의 Property(속성)