2.1이진 탐색 트리의 추상 자료형

먼저 이진 탐색 트리의 추상 자료형을 살펴보겠습니다.

1| BST.insert(data) -> None
이진 탐색 트리에 데이터를 삽입합니다.

2| BST.search(target) -> node
이진 탐색 트리에서 대상 데이터를 가진 노드를 반환합니다. 데이터가 없으면 None을 반환합니다.

3| BST.remove(target) -> node
이진 탐색 트리에 대상 데이터가 있다면 데이터를 가진 노드를 삭제하면서 반환합니다. 데이터가 없으면 None을 반환합니다.

4| BST.insert_node(node) -> None
데이터가 아니라 노드를 삽입합니다. remove에서 반환받은 노드의 데이터를 수정한 후 다시 삽입할 때 사용합니다.

BST에서 insert()와 search() 메서드는 구현하기가 어렵지 않지만, remove() 메서드는 구현하기가 매우 까다롭습니다. 그 이유는 삭제하려는 노드가 리프(leaf) 노드인지, 자식 노드가 하나인지 두 개인지에 따라 삭제하는 방법이 다르기 때문입니다.