똑똑한 코드 작성을 위한 실전 알고리즘

196

똑똑한 코드 작성을 위한 실전 알고리즘

6.3

이진 탐색 트리에서 값 탐색하기

_

insert

()

메서드는 추가할 값을 포함하는 새로운 잎새 노드를 삽입하기 위해 재귀적으로 알

맞은 위치를 찾는다. 같은 재귀적 접근으로 이진 탐색 트리에서 값의 포함 여부를 확인할 수 있

다. 하지만, 실제로는 [코드

6

-

5

]는

while

루프를 통해 값을 찾는 더 단순한 방식으로 구현되

었다.

코드

6-5

BinaryTree

가 값을 포함하는지 결정하기

class BinaryTree:

def __contains__(self, target):

node = self.root

➊

while node:

if target == node.value:

➋

return True

if target < node.value:

➌

node = node.left

else:

node = node.right

➍

return False

➎

➊

root

에서 탐색을 시작한다.

➋

target

값이

node

값과 같으면 성공으로

True

를 반환한다.

➌

target

값이

node

값보다 작으면,

left

하위 트리로

node

를 설정하고 하위 트리로 탐색을 계속한다.

➍

target

값이

node

값보다 크면

right

하위 트리로 탐색을 계속한다.

➎

조사할 노드를 모두 탐색했으면 트리에는 해당 값이 없다고