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(속성)
- value : 노드의 값
- left : 왼쪽 자식 노드
- right : 오른쪽 자식 노드
BST의 Method(메서드)
- insert : child노드를 추가한다
- contains : 트리가 해당 노드 값을 가지고 있는지 탐색한다
- dfs : 깊이 우선 탐색 시의 데이터를 출력한다.
- bfs : 너비 우선 탐색 시의 데이터를 출력한다.