[OOP] Binary Search Tree 자료구조 만들기

Binary Search Tree란?

 

• 이진 탐색 트리
• Binary Tree : 오직 두 개의 자식을 가지는 tree구조
• Binary Search Tree : 부모의 왼쪽 자식은 부모의 데이터값보다 작은 값을 가짐, 오른쪽 자식은 크거나 같은 값을 가짐

Binary Search Tree의 장점

1. 이진 탐색의 장점 -> 탐색 시간복잡도 O(logN), 삽입 삭제 불가능

2. 연결리스트의 장점 -> 데이터의 삽입 삭제 가능

 

Binary Search Tree의 시간복잡도

데이터 삽입, 삭제, 탐색 -> O(logN)

 

 

Binary Search Tree의 기본 구성 요소

 

- Attribution ( 속성 )

 

• Node

1. 데이터 값

2. left child, right child

class Node:
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None

 

• BST ( Binary Search Tree )

1. Root ( Head )

class BinarySearchtree:
    def __init__(self):
        self.root = Node(None)

 

Binary Search Tree의 주 기능 ( Method )

 

class BinarySearchtree:
    def __init__(self):
        self.root = Node(None)
    def insert(self, value):
        new_node = Node(value)
        if self.root.data is None:
            self.root = new_node
            return
        else:
            current_node = self.root
            while True:
                if value >= current_node.data:
                    if current_node.right is None:
                        current_node.right = new_node
                        return
                    else :
                        current_node = current_node.right
                else :
                    if current_node.left is None:
                        current_node.left = new_node
                        return
                    else :
                        current_node = current_node.left
    def print_tree(self):
        # bfs method
        need_visited = deque()
        need_visited.append(self.root)
        while need_visited:
            current_node = need_visited.popleft()
            if current_node.data is not None:
                print(current_node.data, end=" ")
            if current_node.left is not None:
                need_visited.append(current_node.left)
            if current_node.right is not None:
                need_visited.append(current_node.right)
        print()
    def find(self, value):
        current_node = self.root
        if current_node.data is None:
            return False
        while True:
            if value > current_node.data:
                if current_node.right is None:
                    return False
                else:
                    current_node = current_node.right
            elif value < current_node.data:
                if current_node.left is None:
                    return False
                else:
                    current_node = current_node.left
            else:
                return True

BST = BinarySearchtree()
BST.insert(10)
BST.insert(5)
BST.insert(15)
BST.insert(3)
BST.insert(12)
BST.insert(7)
BST.print_tree()

# 출력
# 10 5 15 3 7 12

print(BST.find(7))

# 출력
# True

print(BST.find(8))

# 출력
# False