BST Insertion | Data Structure | Pusan National University

탐색이 멈춘 자리루트에서 비교하며 내려가다 가야 할 자식 노드 자리가 비어 있으면 거기에 붙인다.

자리는 하나뿐빈 자리마다 허용 범위가 겹치지 않으므로 새 키가 들어갈 수 있는 빈 자리는 정확히 하나다.

같은 키이미 있는 키를 넣으면 새 노드를 만들지 않고 기존 노드의 값만 새 값으로 바꾼다.

지나온 노드 수한 번의 삽입은 지나온 노드마다 키를 한두 번 비교하므로 비교 횟수는 지나온 노드 수에 비례한다.

일곱 키를 차례로 넣으면 각 키는 탐색이 멈춘 자리에 단말 노드로 붙는다

50, 30, 70, 20, 40, 60, 80을 순서대로 넣는다. 넣은 키 수를 옮기면 방금 넣은 키가 지나온 길, 붙은 자리, 그리고 지금까지의 삽입 기록이 바뀐다.

넣은 키 수 4

초록 원이 방금 넣은 키, 옅은 파란 원이 그 키가 지나온 노드, 굵은 초록 선이 지나온 길이다. 오른쪽 표는 넣은 순서대로 지나온 길과 붙은 자리를 적은 것이며 초록 행이 방금 넣은 키다.

위에서 만든 일곱 노드 트리에 키 하나를 더 넣는다. 넣을 키를 바꾸면 탐색 경로, 멈추는 빈 자리, _put에서 실행하는 줄이 바뀐다. 이미 있는 키를 고르면 노드 수는 그대로다.

넣을 키 45

점선 상자는 단말 노드 아래의 빈 자식 노드 자리이고 상자 안 괄호는 그 자리에 올 수 있는 키의 열린 범위다. 초록 선과 초록 상자가 넣을 키의 탐색 경로와 멈춘 자리이고, 초록 원은 같은 키를 가진 노드다. 아래 코드의 초록 줄은 마지막에 실행한 줄이다.