이진 탐색 트리

• 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작다.
• 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 크다.
  위의 두 성질을 만족하는 이진 트리를 이진 탐색 트리라고 한다.

데이터 원소의 추가와 삭제가 용이하다는 장점이 있지만,
데이터 뿐만 아니라 왼/오 자식을 기록해야 하기 때문에 공간 소요가 크다는 단점이 있다.

탐색 복잡도는 항상 O(logn)을 갖는다 -> 그렇지 않는 경우가 있다.

연산의 정의

• insert(key, data)

def insert(self, key, data):
        if self.key > key:
            if self.left:
                self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        elif self.key < key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)
        else:
             raise KeyError 

• remove(key)

1. 키를 이용해서 노드를 찾는다. 없으면, 삭제할 것도 없다. 있으면 찾은 노드의 부모 노드를 알고 있어야 한다.
2. 찾은 노드를 제거하고도 이진 탐색 트리 성질을 유지하기 위해 트리의 구조를 정리한다.

   삭제된 노드가 말단 노드인 경우 -> 그냥 그 노드를 없애면 된다.
   삭제된 노드가 자식을 하나 가지고 있는 경우 -> 삭제된 노드 자리에 그 자식을 대신 배치
   삭제된 노드가 자식을 둘 가지고 있는 경우 -> 삭제된 노드보다 바로 다음 키를 가지는 노드를 찾아 그 자리에 대신 배치

def remove(self.key):
	node, parent = self.lookup(key)
    if node:
    	return True
    else:
    	return False

• lookup(key)
• inorder()