저번 게시물에서 이진 트리에 대해 짤막하게 알아보았다. ( [자료구조] 이진 트리 (Binary Tree) 에 대하여 (tistory.com) )
다만 저번에 알아본 이진 트리는 이진 트리라는 단독으로는 잘 사용되지는 않는것 같다. 이진 트리를 여러가지 개선이나 변화한 방식의 자료구조로 사용이 되는데 그 중 하나인 이진 탐색 트리에 대해서 알아보고자 한다.
이진 탐색 트리란?
이진 탐색 트리는 다음과 같은 조건이 만족해야한다.
임의의 꼭짓점 v 에 대해, 왼쪽 부분 트리에 포함된 모든 꼭짓점 v' 에 대해 key[v] >= key[v'] 가 성립하고, v 오른쪽 부분 트리에 포함된 모든 꼭짓점 v' 에 대해 key[v] <= key[v'] 가 성립한다.
즉 왼쪽 자신 노드의 값은 부모노드 보다 작거나 같고, 오른쪽의 자식 노드의 값은 부모 노드보다 큰 상태로 트리가 존재하게 되는 것이다.
예시 그림을 보면 이런 식으로 트리가 존재한다는 것을 알 수가 있다.
해당 이미지를 보면 한 꼭짓점 v 를 기준으로 v 의 값보다 작은 값은 왼쪽으로 가고, 큰 값은 오른쪽에 위치한다는 것을 알 수 있다.
그런데 왜 이런 방식을 사용할까?
이러한 구조는 삽입, 삭제등의 연산과 검색을 효율적으로 할 수 있다는 강점이 있다.
검색을 할 때, 루트에서부터 시작해 각 노드를 비교할때 만약 찾고자 하는 값이 해당 노드의 값보다 작으면 왼쪽, 크면 오른쪽으로 가면 되기 때문에 이진 탐색처럼 빠르게 찾아 나갈 수 있다. 이러한 검색의 방식처럼 삽입, 삭제 연산도 연산이 많을 때도 비교적 빠르게 수행 할 수 있다는 강점을 가진다.
그리고 이러한 방식으로 인해, 늘 정렬된 데이터를 제공할 수 있다는 것도 장점이다. 트리 순회 방법 중 중위 순회를 하게 되면 내림차순이든 오름차순이든 별도의 정렬 과정 없이 정렬된 데이터를 얻을 수 있다.
하지만 이러면 이진 탐색 트리는 저번 게시물에서 설명했던 것 처럼 균형을 유지 하지 않고 치우치게 되면 성능이 크게 저하 될 수도 있다. 편향된 이진 트리가 되어버린다면 O(n) 의 아주 느린 시간 복잡도를 가지게 된다.
그러면 이런 이진 탐색 트리를 파이썬을 통해 구현해보고, 예제를 통해 활용하여 보자
구현 및 예제 문제
일단 기본적인 이진 탐색 트리를 만들어보자. 저번에 작성한 이진 트리의 틀에다가 더욱 기능을 추가하여 만들어보자
def insert_node(self, current_value):
if self.root is None:
self.root = Node(current_value)
else:
self.insert(self.root, current_value)
def insert(self, node, value) -> Node:
if node.value < value:
if node.right is None:
node.right = Node(value)
else:
self.insert(node.right, value)
elif node.value >= value:
if node.left is None:
node.left = Node(value)
else:
self.insert(node.left, value)
예전에 만들어둔 Node 클래스와 BinaryTree 의 insert_node 메서드를 수정해보았다. 일단 예전에는 find_node 를 문제 상황에 맞게 만들어 놨었지만 그 메서드 이름 안에서 삽입 연산을 하자니 이름과 기능이 맞지 않아 이름을 insert 로 바꾸고 그 안에서 재귀적으로 삽입할 장소를 찾게 하였다.
이진 탐색 트리가 구성될 수 있게 루트부터 삽입하려는 값을 해당 꼭짓점과 비교하여 작다면 왼쪽으로 크면 오른쪽으로, 그리고 해당 위치에 노드가 없다면 삽입 있다면 다시 재귀적 호출로 삽입할 자리를 찾는다.
def search_node(self, target_value):
target_node = self.search(self.root, target_value)
return target_node
def search(self, node, value):
if node is None:
return None
if node.value == value:
return node
elif node.value < value:
return self.search(node.right, value)
else:
return self.search(node.left, value)
검색연산도 삽입과 비슷한 방법으로 찾을 수 있다. 우리가 마치 이진 탐색을 할때 처럼 트리를 기준에 맞게 내려가기만 하면 된다.
하지만 삭제 연산을 처리할 때는 조금 고려해야 할 점이 있다. 만약 한 노드를 삭제할때, 자식이 없는 노드라면 그냥 삭제해버리면 된다. 대체하지 않아도 되기 때문이다. 또한 자식이 하나만 있다면 그냥 올려버리면 되기 때문에 크게 어렵지 않다.
그런데 만약 자식이 두쪽 모두에 있다면, 만약 그 노드를 삭제 하였을 때, 어떤 다른 노드가 그 자리를 차지해야 할까? 마구잡이로 삭제된 곳에 다른 자식 노드가 놓여진다면 이진 탐색 트리가 깨지고 말 것이다.
우리는 이 노드를 대체하기 위해서 매우 적절한 후계자 값을 찾기 위해서는 해당 꼭짓점의 서브트리에서 찾아야한다. 왼쪽 서브트리에서 가장 큰 값이나 오른쪽 서브 트리에서 가장 작은 값이 삭제하려는 해당 노드의 값과 매우 유사할 것이 때문에 후계자로 적당하다.
def delete_node(self, value):
self.root = self.delete(self.root, value)
def delete(self, node, value):
if node is None:
return node
if value == node.value:
if node.left is None and node.right is None:
return None
if node.left is None:
return node.right
elif node.right is None:
return node.left
min_larger_node = self.find_min(node.right)
node.value = min_larger_node.value
node.right = self.delete(node.right, min_larger_node.value)
elif value < node.value:
node.left = self.delete(node.left, value)
else:
node.right = self.delete(node.right, value)
return node
def find_min(self, node):
current = node
while current.left is not None:
current = current.left
return current
구현한 해당 로직은 오른쪽 서브 트리에서 가장 작은 값을 찾은 후에 그 값을 대체자로 정하는 방식으로 하였다. 일단 루트 노드부터 해당하는 값을 찾기 시작하여 해당하는 노드를 찾는 다면, 일단 그 노드의 자식이 있는지 여부를 확인하고 만약 왼쪽, 오른쪽 자식이 다 있다면, find_min 메서드를 통해 오른쪽 서브 트리에서 가장 작은 값을 찾고 그 값으로 대체한다.
이제 이렇게 이진 트리에서 이진 탐색 트리로 바꿔보았으니 예제 문제를 풀고 적용해보자
어떤 트리를 전위 순회한 결과를 이진 탐색 트리에 넣고 그 결과를 그대로 후위 순회하여 출력하면 될 것 같다.
우리가 작성했던 코드에서 검색이나 삭제 연산등의 불필요한 코드들은 빼고 이 형식대로 기능을 수행시키면 될 것 같지만 그렇게 되지 않았다. 값이 많아질 수록 재귀 깊이가 깊어질 뿐더러 타임 아웃이 나왔기 때문이다.
그렇기 때문에 순회하는 과정은 재귀를 통해 한다고 치더라도 삽입하는 연산은 반복문으로 바꿔서 처리를 하였다.
import sys
sys.setrecursionlimit(10**6)
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert_node(self, current_value):
if self.root is None:
self.root = Node(current_value)
else:
node = self.root
while True:
if current_value < node.value:
if node.left is None:
node.left = Node(current_value)
break
else:
node = node.left
else:
if node.right is None:
node.right = Node(current_value)
break
else:
node = node.right
def post_order(self, node):
if node:
self.post_order(node.left)
self.post_order(node.right)
print(node.value)
tree = BinarySearchTree()
input = sys.stdin.read()
values = list(map(int, input.split()))
for value in values:
tree.insert_node(value)
tree.post_order(tree.root)
이런식으로 불필요한 기능들은 삭제하고 문제 풀이에 필요한 기능들만 남겨서 다시 작성했다. 그리고 삽입 연산에서의 재귀과정을 반복문으로 바꿔서 시간복잡도에 조금 더 유리하게 변경하였다.
그럼에도 재귀 깊이를 늘려준 이유는 순회하는 과정에서 재귀 깊이를 넘어서는 경우가 있어서 설정 후에 다시 제출하니 문제 없이 정답 처리 되었다.
정리
이진 탐색 트리는 검색, 삽입, 삭제 등의 연산을 효율적으로 사용하여 시간을 단축시킬 수도 있는 유용한 자료구조이다.
하지만 파이썬에서는 따로 패키지를 설치하지 않는 한 내장함수단에서 구현된 트리 모델이 없었기에 구현과 문제 풀이를 함으로서 나중에 이진 탐색 트리를 구현할 일이 있을때 익숙해지면 좋겠다는 취지로 이러한 글을 작성하였다.
참조 :
문제 해결력을 높이는 알고리즘과 자료 구조
문제 해결력을 높이는 알고리즘과 자료 구조 - 예스24 (yes24.com)
C언어로 쉽게 풀어쓴 자료구조
'자료구조' 카테고리의 다른 글
| [자료구조] 이진 트리(Binary Tree) 에 대하여 (0) | 2024.09.06 |
|---|