이진 탐색 트리(Binary Search Tree)에서 가장 작은 요소와 가장 큰 요소를 찾아야 하는 경우, 먼저 이진 트리 클래스를 정의하고 트리에 요소를 추가하는 메서드와 특정 노드를 검색하는 메서드를 함께 구현합니다. 이후 클래스의 인스턴스를 생성하여 이 메서드들을 활용하면 됩니다.
핵심 원리는 간단합니다. 이진 탐색 트리에서는 루트에서 왼쪽 자식 노드를 계속 따라 내려가면 최솟값에 도달하고, 오른쪽 자식 노드를 계속 따라 내려가면 최댓값에 도달합니다.
아래는 전체 동작 과정을 보여주는 예제입니다.
예제 코드
class BST_Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.parent = None
def insert_elem(self, node):
if self.key > node.key:
if self.left is None:
self.left = node
node.parent = self
else:
self.left.insert_elem(node)
elif self.key < node.key:
if self.right is None:
self.right = node
node.parent = self
else:
self.right.insert_elem(node)
def search_node(self, key):
if self.key > key:
if self.left is not None:
return self.left.search_node(key)
else:
return None
elif self.key < key:
if self.right is not None:
return self.right.search_node(key)
else:
return None
return self
class BSTree:
def __init__(self):
self.root = None
def add_elem(self, key):
new_node = BST_Node(key)
if self.root is None:
self.root = new_node
else:
self.root.insert_elem(new_node)
def search_node(self, key):
if self.root is not None:
return self.root.search_node(key)
def get_smallest_elem(self):
if self.root is not None:
current = self.root
while current.left is not None:
current = current.left
return current.key
def get_largest_elem(self):
if self.root is not None:
current = self.root
while current.right is not None:
current = current.right
return current.key
my_instance = BSTree()
print('메뉴 (중복된 키는 없다고 가정)')
print('add <key>')
print('smallest')
print('largest')
print('quit')
while True:
my_input = input('어떤 작업을 수행하시겠습니까? ').split()
operation = my_input[0].strip().lower()
if operation == 'add':
key = int(my_input[1])
my_instance.add_elem(key)
if operation == 'smallest':
smallest = my_instance.get_smallest_elem()
print('가장 작은 요소 : {}'.format(smallest))
if operation == 'largest':
largest = my_instance.get_largest_elem()
print('가장 큰 요소 : {}'.format(largest))
elif operation == 'quit':
break
실행 결과
메뉴 (중복된 키는 없다고 가정)
add <key>
smallest
largest
quit
어떤 작업을 수행하시겠습니까? add 5
어떤 작업을 수행하시겠습니까? add 8
어떤 작업을 수행하시겠습니까? add 11
어떤 작업을 수행하시겠습니까? add 0
어떤 작업을 수행하시겠습니까? add 3
어떤 작업을 수행하시겠습니까? smallest
가장 작은 요소 : 0
어떤 작업을 수행하시겠습니까? largest
가장 큰 요소 : 11
어떤 작업을 수행하시겠습니까? quit
코드 설명
필요한 속성들을 갖춘
BST_Node클래스를 정의합니다.__init__(생성자) 함수는 새 노드를 만들 때 왼쪽(left), 오른쪽(right), 부모(parent) 노드를 모두None으로 초기화합니다.insert_elem메서드는 키 값을 비교하며 적절한 위치를 재귀적으로 탐색해 새 요소를 트리에 삽입합니다.search_node메서드는 트리에서 특정 키를 가진 노드를 검색하고, 존재하지 않으면None을 반환합니다.별도의
BSTree클래스를 정의하며, 초기 상태에서 루트(root)는None으로 설정됩니다.add_elem메서드는 새 노드를 생성해 트리에 추가합니다. 첫 번째 요소라면 루트 노드가 됩니다.search_node메서드는 루트부터 시작해 특정 노드를 검색하는 역할을 담당합니다.get_smallest_elem메서드는 루트에서 왼쪽 자식을 따라 끝까지 이동하여 트리에서 가장 작은 값을 반환합니다.get_largest_elem메서드는 루트에서 오른쪽 자식을 따라 끝까지 이동하여 트리에서 가장 큰 값을 반환합니다.BSTree클래스의 인스턴스를 하나 생성합니다.사용자가 입력한 명령(add, smallest, largest, quit)에 따라 해당 연산이 수행되며, 'quit'을 입력하면 프로그램이 종료됩니다.
동작 원리와 시간 복잡도
이진 탐색 트리는 왼쪽 서브트리에는 항상 더 작은 값, 오른쪽 서브트리에는 항상 더 큰 값이 위치하는 규칙을 유지합니다. 따라서 최솟값은 루트에서 왼쪽으로만 이동하면, 최댓값은 오른쪽으로만 이동하면 찾을 수 있습니다.
두 연산 모두 트리의 높이(h)에 비례하는 시간이 소요되므로 시간 복잡도는 O(h)입니다. 트리가 균형 잡혀 있다면 O(log n), 한쪽으로 치우쳐 있다면 최악의 경우 O(n)까지 늘어날 수 있습니다.