코드 8-3은 본격적으로 삽입, 삭제, 탐색 함수를 구현하기 전에 필요한 메서드를 준비해 두는 것입니다. __make_left와 __make_right 메서드만 살펴보겠습니다. 이 두 메서드는 cur 노드의 왼쪽 자식을 left로 만들거나 오른쪽 자식을 right로 만듭니다. TreeNode의 멤버에 parent가 있기 때문에 부모 노드의 참조에 자식 노드를 연결할 때는 반드시 자식 노드의 parent 참조도 부모를 가리켜야 합니다. 이를 매번 코드로 치는 것보다는 함수로 기능을 만들어 두고 다른 메서드 내에서 불러 쓰는 것이 가독성을 높이는 길입니다.
insert 메서드는 새로운 키를 삽입합니다. 이때 새로운 노드는 반드시 리프 노드가 되도록 합니다. 먼저 코드를 보고 그림으로 간단한 예를 살펴보겠습니다.
코드 8-4
def insert(self, key):
new_node = TreeNode(key)
cur = self.root
if not cur:
self.root = new_node
return
while True:
parent = cur
if key < cur.key:
cur = cur.left
if not cur:
self.__make_left(parent, new_node)
return
else:
cur = cur.right
if not cur:
self.__make_right(parent, new_node)
return