문인철 교수님의 ‘데이터 구조 및 분석: Linear Structure and Dynamic Programming’ 수업
Binary Search Tree and Implementation
Binary Search Tree
- Binary Tree: degree 가 2인 트리
- Binary Search Tree: degree 가 2인 트리이면서 저장된 데이터를 빠르게 찾을 수 있는 구조 → 어떻게 빠르게 찾을 수 있는가? → Root 를 기준으로 일정 규칙을 이용하여 데이터를 저장하기 때문
A scenario of using binary search tree
- linked list 의 경우 모든 노드를 순회하면서 해당 값을 찾아햐함
- binary search tree 의 경우 모든 노드를 순회하지 않고 root 노드보다 큰값을 저장하는 노드들을 순회하면서 값을 찾음 → 규칙이 있기 때문에 좀더 빠르게 찾을 수 있음
Implementation of tree node
- BST 는 root 노드를 이용하여 데이터를 저장
- root 노드만을 이용하여 인스턴스에 접근 할 수 있음
코드
class TreeNode:
lhs_node = None
rhs_node = None
parent_node = None
value = None
def __init__(self, value, parent_node):
self.value = value
self.parent_node = parent_node
def get_lhs(self):
return self.lhs_node
def get_rhs(self):
return self.rhs_node
def get_value(self):
return self.value
def get_parent(self):
return self.parent_node
def set_lhs(self, lhs_node):
self.lhs_node = lhs_node
def set_rhs(self, rhs_node):
self.rhs_node = rhs_node
def set_value(self, value):
self.value = value
def set_parent(self, parent_node):
self.parent_node = parent_node