2.3insert( ) 메서드

본격적으로 BST를 구현해 볼까요? insert() 메서드부터 시작하겠습니다. 삽입하려는 데이터를 루트 노드부터 시작해 차례대로 비교해 내려갑니다. 삽입 데이터가 노드의 데이터보다 작으면 왼쪽 자식 노드로 이동하고, 노드의 데이터보다 크면 오른쪽 자식 노드로 이동해 다시 비교합니다. 그렇게 내려오다 보면 빈 노드를 만나는데, 이때 데이터를 삽입하면 됩니다. 그림을 통해 이해해 보겠습니다.

그림 14-3에서 5는 삽입하려는 데이터입니다. 루트 노드의 데이터부터 비교하기 시작합니다. 두 데이터를 비교했을 때 5가 6보다 작으므로 왼쪽 자식 노드로 내려옵니다.

그림 14-3 insert() 메서드 알고리즘 ①