오늘은 BST를 직접 구현해 봤다.
- 원래 계획은 웹크롤링이었다.(국내 6개 항공사에서 비행기 정보 가져오기).
BST를 빨리 구현해보고 싶은 욕심이 생겨서 계획과는 다르게 진행했다ㅎㅎㅎㅎ
(BST : Binary Search Tree으로 이진 탐색 트리 구조의 자료구조)
① 노드 클래스의 설계는 단순하다.
1) left와 right를 가지고 있어야 한다.
2) value를 가지고 있어야 한다.
class Ticket_node: # Structure(BST)의 최소 구성 단위
def __init__(self, data):
# 1. 초기화 : 노드의 좌,우 노드는 비어있다.(default : None)
self.right = self.left = None
# 2. 노드값 : 노드가 가지고 있는 고유 value
self.data = data② 다음은 BST클래스의 설계 구조다.
class Binary_search: # Structure 개념이며, root가 핵심
# 1. 처음엔 BST(Binary-Search-Tree가 비어있다.)
# root가 여러 노드들을 통해 움직이면서, 노드의 insert, find, delete등의 메소드가 구현이 되도록 도와준다.
def __init__(self):
self.root = None
def insert(self, data):
if self.root == None:
self.root = Ticket_node(data)
else:
self._insert(data, self.root)
def _insert(self, data, cur_node):
# data[1] == air_price다. cf) data[0] == 항공사 이름, data[3] == 이륙시간
if data[1] < cur_node.data[1]:
if cur_node.left == None:
cur_node.left = Ticket_node(data)
else:
self._insert(data, cur_node.left)
elif data[1] > cur_node.data[1]:
if cur_node.right == None:
cur_node.right = Ticket_node(data)
else:
self._insert(data, cur_node.right)
else: # 가격이 동일할 때는 → 이륙시간이 빠른 순서로 정렬. data[2] = 이륙시간
if data[2] < cur_node.data[2]:
if cur_node.left == None:
cur_node.left = Ticket_node(data)
else:
self._insert(data, cur_node.right)
else:
if cur_node.right == None:
cur_node.right = Ticket_node(data)
else:
self._insert(data, cur_node.right)새로운 데이터가 들어오면, 트리 클래스의 root는 root 노드의 값과 비교를 한다. root의 값보다 크면 root.right쪽으로 데이터의 새로운 자리를 알아보려고 하고, root의 값보다 작으면 root.left쪽으로 데이터의 새로운 자리를 알아보려고 한다.
이제 여기서 핵심은, 재귀함수의 등장이다. 자료를 찾아보지 않고 혼자서 BST를 구현하다가 막힌 부분이 바로 이것 때문이었다. root를 계속 이동시키다가 새로운 자리를 찾았더니, root의 위치를 다시 맨 위로 올릴 수가 없었다.
-> 왜냐하면, 예를 들어, root가 자식노드(left, right)가 없는 lear node에 머물러 있다고 하자. 맨 밑에 있는 노드는 자기의 부모노드를 알 방법이 없기 때문이다. 그래서 멘붕이 왔었다.
def insert(self, data):
if self.root == None:
self.root = Ticket_node(data)
else:
self._insert(data, self.root)우선, root가 None이라는 말은, 맨 초기의 상태를 의미한다.
데이터가 아무것도 입력되지 않고, 단지 BST 클래스를 선언한 상태다.
이때는 맨 처음 들어오는 값을 그대로 넣어주면 된다.
문제는 else: 아래 구문이다. insert()함수가 아닌, _insert()함수를 호출하고 있다. 이제 _insert()함수를 정의한 코드의 일부를 보자.
def _insert(self, data, cur_node):
# data[1] == air_price다. cf) data[0] == 항공사 이름, data[3] == 이륙시간
if data[1] < cur_node.data[1]:
if cur_node.left == None:
cur_node.left = Ticket_node(data)
else:
self._insert(data, cur_node.left)
elif data[1] > cur_node.data[1]:
if cur_node.right == None:
cur_node.right = Ticket_node(data)
else:
self._insert(data, cur_node.right)_insert()함수 안에서 또 다시 _insert()함수를 호출하고 있다.
이 방식이 소름이 돋는 것은,
재귀 함수를 모두 마치고 맨처음 호출한 상태로 돌아오면, (컴퓨터는) 맨 처음의 root값을 알고 있다는 것이다.
_insert(data, cur_node): 함수의 매개변수를 보자. cur_node가 원래는 root 였다가,
root 노드 의 값과의 대소 비교(재귀)를 통해 cur_node가 root.right, root.right.left, root.right.left.right -> .... 쭉쭉쭉 변해간다.
언제까지???? 계속 탐색해나간 cur_node 의 left 혹은 right가 None이 나올때까지!!
None 이 나오면 바로 그 자리에 노드를 생성해주면서 data를 그 노드에 넣으니까.
BST의 핵심은 재귀함수를 이해할 수 있느냐에 달린 것 같다.
예시로 데이터 10개의 대한 BST를 출력해 보았다.
그 결과,
가격이 낮은 순서대로 출력되고 있음을 확인했다. 120 -> 200 -> 390 -> 460 -> 쭉쭉
======================================================
어제는 1) 사용자 정보 입력받기 (출발지, 도착지, 출발일자) 코드를 완료했다.
오늘은 세번째 프로세스인 3) 데이터 정렬(by BST) 및 출력을 완료했다.
내일, 모레는 2) 각 항공사에서 티켓 가격과 출발시간을 크롤링해서 저장해서
data 변수에 저장하는 것 까지 할 예정이다.
- One step at a time - 