TIL - 0121

문인철 교수님의 ‘데이터 구조 및 분석: Linear Structure and Dynamic Programming’ 수업

Binary Search Tree and Implementation

Binary Search Tree

200121

  • Binary Tree: degree 가 2인 트리
  • Binary Search Tree: degree 가 2인 트리이면서 저장된 데이터를 빠르게 찾을 수 있는 구조 → 어떻게 빠르게 찾을 수 있는가? → Root 를 기준으로 일정 규칙을 이용하여 데이터를 저장하기 때문

A scenario of using binary search tree

200121

  • linked list 의 경우 모든 노드를 순회하면서 해당 값을 찾아햐함
  • binary search tree 의 경우 모든 노드를 순회하지 않고 root 노드보다 큰값을 저장하는 노드들을 순회하면서 값을 찾음 → 규칙이 있기 때문에 좀더 빠르게 찾을 수 있음

Implementation of tree node

200121

  • 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