Python에서 이항 트리(binomial tree)를 구현해야 하는 경우, 객체 지향 프로그래밍 방식을 활용하는 것이 가장 효과적입니다. 클래스를 정의하고 그 안에 속성(attribute)과 메서드(method)를 선언한 뒤, 클래스의 인스턴스를 생성하여 실제 연산을 수행하는 방식입니다.
이 글에서는 이항 트리를 생성하고, 차수(order)가 같은 두 트리를 결합하는 기능을 갖춘 메뉴 기반 프로그램을 소개합니다.
이항 트리란?
이항 트리는 이진 힙(binary heap)과 함께 사용되는 자료구조로, 다음과 같은 특징을 가집니다.
- 차수가 k인 이항 트리는 정확히 2^k개의 노드를 가집니다.
- 차수가 k인 트리는 루트 노드와 차수가 각각 0부터 k-1까지인 자식 트리들로 구성됩니다.
- 차수가 같은 두 개의 이항 트리는 쉽게 하나로 결합할 수 있어, 우선순위 큐(priority queue) 구현에 널리 활용됩니다.
예제 코드
class binomial_tree:
def __init__(self, key):
self.key = key
self.children = []
self.order = 0
def add_at_end(self, t):
self.children.append(t)
self.order = self.order + 1
my_tree = []
print('Menu')
print('create <key>')
print('combine <index1> <index2>')
print('exit')
while True:
option = input('What do you wish like to do? ').split()
operation = option[0].strip().lower()
if operation == 'create':
key = int(option[1])
b_tree = binomial_tree(key)
my_tree.append(b_tree)
print('Binomial tree has been created.')
elif operation == 'combine':
index_1 = int(option[1])
index_2 = int(option[2])
if my_tree[index_1].order == my_tree[index_2].order:
my_tree[index_1].add_at_end(my_tree[index_2])
del my_tree[index_2]
print('Binomial trees have been combined.')
else:
print('Order of trees need to be the same to combine them.')
elif operation == 'exit':
print("Exit")
break
print('{:>8}{:>12}{:>8}'.format('Index', 'Root key', 'Order'))
for index, t in enumerate(my_tree):
print('{:8d}{:12d}{:8d}'.format(index, t.key, t.order))실행 결과
Menu create <key> combine <index1> <index2> exit What do you wish like to do? create 7 Binomial tree has been created. Index Root key Order 0 7 0 What do you wish like to do? create 11 Binomial tree has been created. Index Root key Order 0 7 0 1 11 0 What do you wish like to do? create 4 Binomial tree has been created. Index Root key Order 0 7 0 1 11 0 2 4 0 What do you wish like to do? combine 0 1 Binomial trees have been combined. Index Root key Order 0 7 1 1 4 0 What do you wish like to do? exit Exit
코드 설명
- 클래스 정의: 'binomial_tree'라는 이름의 클래스를 정의합니다.
- 생성자(__init__): 노드의 키 값(key), 자식 노드 리스트(children), 그리고 트리의 차수(order)를 초기화합니다. 새로 생성된 트리의 초기 차수는 0입니다.
- add_at_end 메서드: 트리 끝에 새로운 트리를 추가하는 메서드로, 자식을 추가할 때마다 차수가 1씩 증가합니다.
- 빈 리스트 생성: 여러 개의 이항 트리를 저장하기 위한 빈 리스트 'my_tree'를 만듭니다.
- 메뉴 선택: 사용자가 원하는 작업(생성, 결합, 종료)을 입력받아 처리합니다.
- 'create' 옵션: 키 값을 입력하면 클래스의 인스턴스가 생성되고, 해당 키를 루트로 하는 이항 트리가 만들어집니다. 이후 인덱스, 루트 키 값, 차수가 함께 출력됩니다.
- 'combine' 옵션: 결합할 두 트리의 인덱스를 지정하면, 두 트리의 차수가 동일한 경우 하나로 합쳐지고 결과가 화면에 표시됩니다. 차수가 다르면 결합이 거부되며 안내 메시지가 출력됩니다.
- 'exit' 옵션: 프로그램을 종료합니다.
이처럼 객체 지향 방식을 활용하면 이항 트리의 생성과 결합 로직을 깔끔하게 분리할 수 있으며, 코드의 재사용성과 유지보수성도 크게 향상됩니다.