이진 탐색 트리

이진 탐색을 위해 만들어지는 트리여서 이진 탐색 트리라고 부른다.

반드시 부모 노드의 오른쪽에는 부모 노드의 값보다 큰 값이 위치하고, 왼쪽에는 부모 노드보다 작은 값이 위치하게 된다.

이진 탐색 트리의 특징

이진탐색 트리는 자료의 삽입 순서에 따라 트리의 모양이 달라진다.

• 밸런스가 잘 맞는 경우 아래 시간복잡도를 가진다.
  • 자료의 탐색: O(logN)
  • 자료의 삽입: O(logN)
  • 자료의 삭제: O(logN)
• 자료의 중복을 허용안함.

한계

이진탐색 트리는 한쪽으로 트리가 쏠릴 경우, (자료가 순서대로 정렬되어 들어오거나 하면) 링크드리스트와 같은 시간복잡도를 갖는다.

그래서 데이터 삽입 시 랜덤하게 인풋을 넣어주거나, 균형잡힌 트리가 만들어지도록 노력해야 한다.

탐색

이진탐색 트리의 존재 이유다. 이진 탐색 트리는 삽입이나 삭제가 추가적으로 일어나지 않는 편이고, 주로 이미 주어진 정보를 정렬하여 탐색하는 데 쓰인다. 루트 노드보다 큰 값은 오른쪽으로 이동하고, 작은 값은 왼쪽으로 이동해, 한번의 탐색에 절반의 후보군을 줄여버릴 수 있어서 O(logN) 의 시간복잡도를 갖는다.

삽입

시간복잡도 O(logN) 이다. 먼저 해당 value 와 중복되는 노드가 있는지 확인하고 없다면 마지막 search node에서 알맞은 위치에 삽입한다. 중복 노드를 확인하는데 탐색하는 부분에서 O(logN)의 시간복잡도가 발생한다.

삭제

시간복잡도 O(logN) 이다. 해당 value를 찾아가서 노드를 삭제하고, 일련의 작업이 필요하다.
1) 노드가 한 개도 없을 경우
2) 노드가 한 개 있을 경우
3) 노드가 두 개 모두 있을 경우

세 가지 경우로 나눠서 처리해주어야 한다.

1) 의 경우 그냥 삭제해버리면 된다. 순회할 때 마다 parent 노드와 내가 어떤 방향으로 내려왔는지 변수에 저장해놓아야 한다. 그리고 삭제할 노드를 찾으면 그 부모노드의 내가 온 방향으로 연결을 끊어주면 된다.

2) 의 경우 삭제 후 연결 되어 있는 노드를 그대로 parent에 붙여주어야 한다.

3) 의 경우 삭제 후 연결 되어 있는 모든 간선을 끊어주어야 한다. 특정 노드를 삭제한다는 의미는 해당 노드의 왼쪽엔 모두 그 값보다 작은 값이 존재하고, 해당 노드의 오른쪽에는 그 값보다 큰 값만이 존재한다. 때문에 오른쪽에 있는 노드를 올려서 parent에 연결된다면, 끊어진 왼쪽 노드들은 삭제되기 전 노드의 오른쪽 노드의 가장 왼쪽으로 타고 내려가서 그 노드에 붙어야 한다.

코드

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

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            curr = self.root
            while curr is not None:
                if value == curr.value:
                    print("already there is node")
                    return False

                elif value > curr.value:
                    if curr.right is None:
                        curr.right = Node(value)
                        return
                    curr = curr.right
                elif value < curr.value:
                    if curr.left is None:
                        curr.left = Node(value)
                        return
                    curr = curr.left

    def search(self, value):
        curr = self.root
        while curr is not None:
            if value == curr.value:
                return curr
            if value > curr.value:
                curr = curr.right
            else:
                curr = curr.left
        return False

    def remove(self, value):
        parent = None
        direction = "l"
        isHere = False
        curr = self.root
        while curr is not None:

            if value == curr.value:
                isHere = True
                break
            parent = curr
            if value > curr.value:
                direction = "r"
                curr = curr.right
            else:
                direction = "l"
                curr = curr.left

        if not isHere:
            return False

        # 하위 노드가 없는 경우
        if curr.left is None and curr.right is None:
            if direction == "l":
                parent.left = None
            else:
                parent.right = None
        # 하위 노드가 한개 있는 경우
        #   오른쪽

        elif curr.left is None and curr.right is not None:
            if direction == "l":
                parent.left = curr.right
            else:
                parent.right = curr.right
        #   왼쪽

        elif curr.right is None and curr.left is not None:
            if direction == "l":
                parent.left = curr.left
            else:
                parent.right = curr.left

        # 하위 노드가 두 개 모두 있는 경우
        elif curr.right is not None and curr.left is not None:
            if direction == "l":
                parent.left = curr.right
                parent.right = curr.right
                temp = curr.left
                curr = curr.right
                while curr.left is not None:
                    curr = curr.left
                curr.left = temp
            else:
                parent.right = curr.right
                temp = curr.left
                curr = curr.right
                while curr.left is not None:
                    curr = curr.left
                curr.left = temp
        # parent 노드와, 방향을 저장해두어야 함.
        # 오른쪽 하위 노드들을 전부 부모에 갖다붙이고, 삭제하는 왼쪽 노드들을 오른쪽 노드의 최 왼쪽 노드에 갖다 붙임