[기본개념] BST 기본 구조

| 기본구조 

트리는 기본적으로 루트와 왼쪽, 오른쪽 노드가 있다

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

class BinarySearchTree:
    def __init__(self):
        self.root = None

 

 

| Insert method

    def insert(self, value):
        new_node = Node(value)
        if self.root == None:
            self.root = new_node
            return True
        current = self.root
        while True:
            if new_node.value == current.value:
                return False
            if new_node.value < current.value:
                if current.left is None:
                    current.left = new_node
                    return True
                current = current.left
            if new_node.value > current.value:
                if current.right is None:
                    current.right = new_node
                    return True
                current = current.right

 

트리에 노드를 삽입할 때는 3가지 케이스가 있다.

1. 트리가 빈 트리일 때

2. 중복되는 값이 있을 때

3. 그 외의 정상적인 경우

 

이 상황들에 따라서 작성을 해주면 되고,

3번 상황의 경우 대소비교를 하면서 적절한 위치를 찾아줘야 하기 때문에

current 라는 화살표를 하나 설정해서, 이동해가면서 위치를 찾아주도록 한다.

 

while True 로 놓아줘서 반복하는 게 특징 ! 

 

 

| Contains

해당 value가 이 트리에 있는지 없는지만 확인하는 함수다

    def contains(self, value):
        if self.root == None:
            return False
        current = self.root
        while current is not None:
            if value < current.value:
                current = current.left
            if value > current.value:
                current = current.right
            else:
                return True
        return False

 

역시 2가지 경우로 나눌 수 있겠다

1. 빈 트리인 경우 - 당연히 없을테니까 false 반환

2. 그 외의 경우

 

2번 상황의 경우, 대소 관계를 비교해가면서 같은 값이 있는지 확인해야하고,

있을 때는 true,  끝까지 갔는데 없다면 false를 반환한다. easy! 

 

 

| Big-O

BST는 기본적으로 다 O(logn)이라고 보면 된다. insert, remove, search 모두 반쪽 잘라서 시작하기 때문에 O(logn)

그래서, 검색을 많이해야 하는 경우에는 BST가 Linked list 보다 효과적이다

하지만 데이터 추가를 많이 해야하는 경우는 LL이 더 효과적 (O(1))이다

LL 은 append로 바로 삽입이 가능하기 때문!! (하지만 그 외 remove, lookup 등은 O(n)으로 비효율적이다)