목록2022/12/01 (1)

넘치게 채우기

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

이진 탐색 트리? 이진 탐색 트리는 다음과 같은 조건이 있다: 같은 key값을 가지는 노드는 없다. 루트노드의 왼쪽 서브트리는 루트노드보다 작은 값들만 있어야 한다. 루트노드의 오른쪽 서브트리는 루트노드보다 큰 값들만 있어야 한다. 루트노드의 서브트리들 모두 이진 탐색 트리여야 한다. 이 조건들로, 이진 탐색 트리를 순회할 때 에는 보통 중위 순회를 이용한다. 이진 탐색 트리에는 세 가지 연산이 있다. 탐색(Search) 삽입(Insert) 삭제(Delete) 탐색 만약, 루트와 같은 값을 가진다면, 탐색을 멈춘다. 루트가 없는 경우 역시 탐색을 멈춘다. 만약, 루트보다 작은 값을 가진다면 왼쪽 서브트리에서, 더 큰 값을 가지면 오른쪽 서브트리에서 재귀한다. 구현 def _search(self, root..
컴퓨터과학/자료구조 2022. 12. 1. 23:54
이전 Prev 1 Next 다음