이진 탐색 트리 (Binary Search Tree)

1. 이진 탐색 트리란?

 

누구나 한번쯤은 숫자 맞추기 게임을 해본 적이 있을 것이다. A가 숫자를 하나 생각하면 B는 그 숫자를 맞추는데, A는 B가 말한 숫자보다 자기가 생각한 숫자가 큰지 작은지 (Up/Down) 를 알려준다.

이런 게임을 한다고 했을 때 일반적으로 생각할 수 있는 가장 좋은 전략은 정답 숫자의 가능한 범위를 반으로 잘라서 정중앙의 숫자를 말하는 것이다. 예를 들어 1~100까지의 숫자 중에서 생각하라고 했다면 처음엔 50을 부르고, Up이 나오면 그 다음엔 75를 부르고... 이런 식으로 범위를 반씩 좁혀나가는 방법이다.

 

이러한 방법을 컴퓨터공학에서 이진 탐색 (Binary Search) 이라고 부른다. 그리고 트리 자료구조를 이용해서 이진 탐색을 할 수 있도록 만든 걸 이진 탐색 트리 (Binary Search Tree: BST) 라고 부른다. 이진 탐색 트리는 이렇게 생겼다.

 

 

이진 탐색 트리 (이하 BST) 의 규칙 및 특성은 다음과 같다.

- 이진 트리 (Binary Tree: 각 노드의 자식의 수가 최대 2개인 트리) 이다.

- 왼쪽 자식 노드의 값은 자신의 값보다 작아야 한다.

- 오른쪽 자식 노드의 값은 자신의 값보다 커야 한다.

- 서브트리도 BST이다.

- 값이 중복되는 노드는 없다.

 

2. 이진 탐색 트리에서의 검색

 

이렇게 BST를 만들어 놓으면 이걸로 어떻게 이진 탐색을 할 수 있을지 딱 바로 눈에 들어온다. 찾는 값이 현재 노드에 써있는 값보다 작으면 왼쪽으로, 크면 오른쪽으로 내려가는 것이다.

왼쪽 그림은 13을 찾는 예시이다. 루트 노드부터 시작해서 값을 비교한다. 찾는 값 (13) 이 노드의 값인 9보다 크므로 오른쪽으로 내려간다. 12보다도 크므로 한번 더 오른쪽으로 갔다가, 15보다는 작으므로 왼쪽으로 간다. 그러면 13을 만난다. 원하는 값을 찾았음을 알려주면 된다.

 

오른쪽은 파이썬으로 구현한 BST를 이용한 이진 탐색이다. 각 노드가 data, left (왼쪽 자식노드), right (오른쪽 자식노드) 를 가지도록 노드 클래스를 구성하고, left/right를 이용해 재귀 호출을 해주면서 내려가는 방식이다. 찾는 값을 만났거나, leaf 노드까지 내려갔음에도 값을 못 찾았으면 종료한다.

 

3. 이진 탐색 트리에서의 노드 삽입

 

BST를 이미 만들어놓은 상태에서 새로운 값을 추가, 그러니까 노드를 삽입하는 방법은 검색을 조금만 변형하면 된다.

일단 BST의 규칙상, BST에 이미 있는 값을 또 넣을 수는 없으므로 그런 경우에는 예외처리를 해준다.

새로운 값인 경우에는 검색을 수행하는 것과 똑같이 쭉 내려가다가, 마지막에 도달한 leaf 노드의 값이랑 새로운 값을 비교한다. 새로운 값이 더 크면 오른쪽에, 더 작으면 왼쪽에 삽입해주면 된다. 삽입을 해준다는 건 노드 객체를 만들어서 left, right 자리에 대입해준다는 소리다.

 

 

4. 이진 탐색 트리에서의 노드 삭제

 

삭제는 삽입보다 좀 더 복잡하다. 삭제할 값을 찾아가는 것까지는 검색할 때랑 똑같이 하면 된다. 삭제할 값을 찾았으면 그걸 지워야 하는데, 문제는 leaf 노드가 아닌 이상 그냥 노드를 지워버리면 그 자리에 구멍이 나서 트리가 쪼개져버린다는 것이다. 트리의 형태를 온전히 유지하려면 그 자리를 메꾸거나 이어줘야 하는데 그걸 어떻게 할 것인가 하는 문제가 생긴다.

 

 

삭제하려는 노드의 자식 수에 따라 케이스를 나눠봤다.

1) leaf 노드일 경우: 밑에 아무것도 없으니 그냥 삭제하면 된다. 제일 편한 케이스다.

2) 자식 노드가 1개일 경우: 노드를 삭제하고 자식 노드를 그 자리에 붙인다. 이렇게 해도 BST의 규칙이 깨지지 않으니 OK다.

3) 자식 노드가 2개일 경우: 좀 골치아프다. 2) 처럼 그 자리에 자식 노드를 붙이자니 자식 노드가 2개라서 둘 중 어느걸 붙여야할지 선택도 해야하고, 골라서 붙였더니 아래 그림처럼 노드가 겹쳐버리거나 BST의 규칙이 깨져버리는 경우가 생긴다.

 

 

이 예시에서는 12를 위로 올리면 되긴 하는데, 12에도 left child가 있다면 마찬가지의 상황이 생긴다.

 

그럼 어떻게 해야할까? 생각해보면 BST에서 노드 하나가 없어져서 그 자리가 비었을 때, 원래 그 자리에 있던 값이랑 제일 가까운 값이 그 자리를 채우면 BST의 규칙이 깨지지 않는다.

비어버린 자리를 기준으로 왼쪽 서브트리에는 원래 있던 값보다 작은 수들이, 오른쪽 서브트리에는 큰 수들이 들어있을 것이다. 그러니까 왼쪽 서브트리에 있는 값들 중에 제일 큰 값 (=제일 오른쪽에 있는 노드), 또는 오른쪽 서브트리에 있는 값들 중에 제일 작은 값 (=제일 왼쪽에 있는 노드) 을 들고오면 된다는 것이다.

 

 

왼쪽 서브트리에서 제일 큰 값 (left_max), 또는 오른쪽 서브트리에서 제일 작은 값 (right_min) 을 가져오는 함수를 먼저 만들어보자. 검색할 때처럼 재귀함수 타면서 내려가면 되는데, 왼쪽이나 오른쪽을 선택할 필요 없이 한쪽으로만 간다는 점이 차이점이다. 특정 노드를 기준으로 왼쪽에는 그 노드의 값보다 작은 값들만, 오른쪽에는 큰 값들만 존재한다는 BST의 특성상 큰 값을 찾을 때는 오른쪽으로만, 작은 값을 찾을 때는 왼쪽으로만 가면 된다.

 

이제 노드를 삭제하는 함수를 보자. 앞부분 1/4는 삭제할 노드를 찾아가는 부분이고, 왼쪽 사진 중간쯤에 있는 최상위 else문부터가 삭제할 노드를 찾았을 때 실행되는 부분이다.

else문부터의 코드를 보면 위에서 설명한 것과는 달리 생각보다 코드가 긴 느낌인데, self (현재 노드) = None으로 만든다고 해도 (혹은 del 같은 명령어를 써서 지운다고 해도) 부모 노드의 left/right에 들어있는 노드 객체가 안 사라져서 그것까지 지워줘야 하기 때문이다.

그 이유는 이 글에서 설명하고 있는데, 파이썬에서 인자는 C++나 Java에서처럼 참조되는 (by reference) 것이 아니라 로컬 변수에 대입 (by assignment) 되기 때문이라 한다. 그러니까 내가 구현한 delete 함수 안에서 노드 객체를 삭제해도, 다른 객체들이 '참조' 하고 있는 '그 노드 객체' 에는 영향을 미치지 못한다.

그래서 함수 파라미터로 parent를 줘서, 내려갈 때 부모 노드의 정보를 저장해뒀다가 노드를 삭제할 때 부모 노드의 left/right에 저장된 정보까지 같이 삭제해주는 식으로 구현했다.

 

1) left와 right가 둘 다 None이면, self랑 parent의 자식 객체를 None으로 만든다.

2-1) left가 None이면, right의 값을 가져와서 temp에 저장해놨다가, self와 parent의 자식 객체를 temp로 갈아끼운다. 

2-2) right가 None이면, left의 값을 가져와서 temp에 저장해놨다가, self와 parent의 자식 객체를 temp로 갈아끼운다.

3) left/right 둘 다 None이 아닌 경우 right를 시작으로 find_rightmin() 을 써서 오른쪽 서브트리에서 제일 작은 값을 가져온다. 그리고 그 값을 삭제하는 delete_bst() 를 호출한다.

 

 

그럼 마지막으로 아까 그 예시에서 9를 삭제했을 때 함수가 어떻게 동작하는지 살펴보자.

 

- delete_bst(9, -1) 을 호출 (처음 호출할 때는 root부터 시작이므로 parent에는 아무 값이나 넣어준다)

- 바로 9를 만났으므로 else로 들어가고, 자식 노드가 2개이므로 한번 더 else로 들어감

- self.right.find_rightmin() 함수가 오른쪽 서브트리에서 제일 작은 값 (12) 을 찾음

- 현재 노드 (루트) 의 값을 12로 바꿈

- self.right.delete_bst(12, self) 를 호출하여 루트 노드의 오른쪽 노드부터 시작해서 12를 찾음

- 바로 12를 만났으므로 else -> 오른쪽 자식노드 1개가 있으므로 첫번째 elif로 들어감

- 위에 있는 새로운 12 노드의 right child를 15 노드로 바꾸고 자기 자신이 15 노드가 되면서 기존 12 노드는 사라짐