BST에 새 원소 삽입하기

이번에는 원소 삽입에 대해 알아보겠습니다. BST에 새로운 원소를 삽입하는 과정을 그림 2-6에 나타냈습니다.

▲ 그림 2-6 이진 검색 트리에 원소 추가

새로운 원소를 추가하려면 먼저 원소가 삽입될 위치의 부모 노드를 찾아야 합니다. 이 과정은 앞서 설명한 원소 검색과 비슷한 접근 방식을 사용하면 됩니다. 즉, 루트 노드부터 시작하여 각 노드를 추가할 원소와 비교하면서 원소가 삽입될 위치로 이동해야 합니다. 그림 2-6에서 새 원소 18을 추가하기 위해 먼저 17이 저장된 노드까지 이동했으며, 18이 17보다 크므로 17의 오른쪽 자식 노드에 18을 추가했습니다.