그림 8-4를 보며 코드를 따라가 보겠습니다.

▲ 그림 8-4 insert

먼저 cur가 루트인 6을 가리키고 있습니다. 삽입해야 할 키 값은 5입니다. 이제 5와 cur의 키 값을 비교합니다. 5가 6보다 작으므로 이 노드 5는 노드 6의 왼쪽 서브 트리에 있어야 합니다. 그러므로 cur를 노드 6의 왼쪽 자식으로 내립니다. 이때 노드 6을 parent로 가리켜 둡니다. 다음으로 5를 cur의 키와 비교합니다. 5는 3보다 크니 노드 5는 노드 3의 오른쪽 서브 트리에 있어야 합니다. 그러므로 cur를 노드 3의 오른쪽 자식 노드로 내리고 parent는 노드 3으로 내려옵니다. 이때 cur는 빈 노드를 의미하는 None을 가리키게 됩니다. 이 자리에 노드 5를 넣으면 됩니다. 그런데 cur가 None이므로 cur를 이용해서 노드 5를 넣을 수는 없습니다. 이때 쓰는 참조가 parent입니다. parent는 cur의 부모이므로 parent의 오른쪽 자식 노드를 가리키는 참조로 노드 5를 가리키면 됩니다.