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

189

6

장

이진 트리

6.2

이진 탐색 트리

이진 트리는 모든 재귀적 자료구조의 대부다.

이진 탐색 트리

binary

search

tree

는 효율적인 탐색, 삽

입 및 삭제 연산을 가지는 값의 컬렉션을 저장할 수 있다.

이진 배열 탐색의 성능이

O

(

log

N

)이 되려면 값을 정렬된 배열에 저장해야 한다. 사용자가

정보를 더 쉽게 볼 수 있도록 정보를 정렬된 순서로 생성하는 데는 무수히 많은 이유가 있다.

실용적인 관점으로 보면, 매우 큰 고정 배열은 기반 운영체제에서 할당되는 연속적인 메모리

를 필요로 하므로 운영하기가 쉽지 않다. 게다가 배열의 크기를 변경하면 다음과 같은 문제가

있다.

●

배열에 값을 추가하기 위해 더 큰 배열이 새로 생성되고, 이전 배열에 있던 값들은 (새 값을 위한 공간을

추가한) 새로 생성한 배열로 복사된다. 마지막으로 이전 배열을 위한 메모리가 해제된다.

●

배열에서 값을 제거하기 위해, 제거된 값의 오른쪽에 있는 모든 값이 왼쪽으로 하나의 인덱스만큼 이동

해야 한다. 코드는 배열의 끝에 ‘사용하지 않는’ 인덱스 위치가 있음을 기억해야 한다.

파이썬 프로그램은 프로그래머가 따로 처리하지 않아도 내장

list

자료형이 증가하고 축소할

수 있어 이런 어려움을 피할 수 있지만, 최악의 경우에 파이썬

list

에 값을 추가하는 성능은

O

(

N