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

194

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

BinaryTree

의

insert

(

val

)

함수는 재귀

_

insert

(

node

,

val

)

헬퍼 함수

1

를 수행해,

self

.

root

가 루트인 하위 트리에

val

을 삽입한 결과의 하위 트리가 되도록

self

.

root

를 설

정한다.

캐주얼하고 우아한

insert

()

의 한 줄 구현은 재귀 자료구조를 사용한 프로그램의 기능이다.

_

insert

()

함수는

val

을 삽입하고 결과로 만들어진 하위 트리의 루트를 반환한다.

TIP

예제에서 삽입되는 값들은 모두 고유하지만, 일반적으로 이진 탐색 트리는 중복된 값을 포함할 수 있으므로

_

insert

()

함수는

val

≤

node

.

val

인지를 확인한다.

_

insert

(

node

,

val

)

에서 종료 조건은

node

가

None

일 때 발생하는데, 이는

val

이 존재

하지 않는 하위 트리에 삽입되도록 요청되는 경우에 발생한다. 이 경우에는 새롭게 생성된

BinaryNode

를 루트로 하는 하위 트리를 생성해 반환한다. 재귀 조건은

val

이 왼쪽 하위 트

리

node

.

left

나 오른쪽 하위 트리

node

.

right

에 삽입되는 경우다. 재귀 경우의 마지막에

_

insert

()

는

node

를 루트로 하는 하위 트리에

val

을 추가한 뒤, 하위 트리의 루트인

node

를

반환한다.

_

insert

(