TIL_39 : 이진 탐색 트리

🙄 이진 탐색 트리

---

➡ 이진 탐색 트리란?

• 추상 자료형 딕셔너리, 세트를 구현할 때 사용 됨
• 이진 탐색 트리 속성을 갖는 이진 트리
• 특정 노드를 봤을 때, 왼쪽 부분 트리에 있는 모든 노드는 그 노드의 데이터보다 작아야 함
• 반대로 오른쪽 부분 트리에 있는 모든 노드는 그 노드의 데이터보다 커야 함

➡ 이진 탐색 트리 노드 구현

• 힙은 항상 완전 이진 트리기 때문에 배열로 구현
• 이진 탐색 트리는 이진 트리지만 완전 이진 트리라는 보장은 없음
• 노드 클래스를 정의한 후 여러 노드 인스턴스들을 생성하고 인스턴스들을 연결시켜 구현
• 노드들을 어떻게 연결하고, 어떻게 삭제하고, 어떻게 찾는지가 핵심
• 이진 탐색 트리에서 in-order 순회 함수를 쓰면 정렬된 순서대로 데이터 출력 가능

def print_inorder(node):
    """주어진 노드를 in-order로 출력해주는 함수"""
    if node is not None:
        print_inorder(node.left_child)
        print(node.data)
        print_inorder(node.right_child)
        
        
class Node:
    """이진 탐색 트리 노드 클래스"""
    def __init__(self, data):
        self.data = data
        self.parent = None
        self.left_child = None
        self.right_child = None


class BinarySearchTree:
    """이진 탐색 트리 클래스"""
    def __init__(self):
        self.root = None

    def print_sorted_tree(self):
        """이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
        print_inorder(self.root)


# 비어 있는 이진 탐색 트리 생성
bst = BinarySearchTree()

🙄 이진 탐색 트리 연산

---

➡ 이진 탐색 트리 삽입

• 삽입 이후에도 이진 탐색 트리 속성이 유지되어야 함

1. 새로운 노드 생성
2. root 노드부터 비교하면서 저장할 위치 찾음
3. 찾은 위치에 새롭게 만든 노드 연결

시간 복잡도

• 트리의 높이 : $h$

1. : $O(1)$
2. : $O(h)$
3. : $O(1)$

• 시간 복잡도 : $O(1+h+1)$ = $O(h)$

class BinarySearchTree:
    """이진 탐색 트리 클래스"""
    def __init__(self):
        self.root = None


    def insert(self, data):
        new_node = Node(data)  # 삽입할 데이터를 갖는 새 노드 생성

        # 트리가 비었으면 새로운 노드를 root 노드로 만든다
        if self.root is None:
            self.root = new_node
            return
        
        temp = self.root
        while temp is not None:
            if data > temp.data:
                if temp.right_child is None:
                    temp.right_child = new_node
                    new_node.parent = temp
                    return
                else:
                    temp = temp.right_child
            else:
                if temp.left_child is None:
                    temp.left_child = new_node
                    new_node.parent = temp
                    return
                else:
                    temp = temp.left_child


    def print_sorted_tree(self):
        """이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
        print_inorder(self.root)  # root 노드를 in-order로 출력한다


# 빈 이진 탐색 트리 생성
bst = BinarySearchTree()

# 데이터 삽입
bst.insert(7)
bst.insert(11)
bst.insert(9)
bst.insert(17)
bst.insert(8)
bst.insert(5)
bst.insert(19)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(14)

# 이진 탐색 트리 출력
bst.print_sorted_tree()

# 2
# 3
# 4
# 5
# 7
# 8
# 9
# 11
# 14
# 17
# 19

➡ 이진 탐색 트리 탐색

• 특정 데이터를 갖는 노드를 리턴하는 연산

1. 주어진 노드의 데이터와 탐색하려는 데이터 비교
2. 탐색하려는 데이터가 더 크면 노드의 오른쪽 자식으로 간다
3. 탐색하려는 데이터가 더 작으면 노드의 왼쪽 자식으로 간다
4. 탐색하려는 노드를 찾으면 리턴한다

시간 복잡도

• 트리의 높이 : $h$
• 최악의 경우 : $h+1$번 탐색
• 시간 복잡도 : $O(h+1)$ = $O(h)$

class BinarySearchTree:
    """이진 탐색 트리 클래스"""

    def __init__(self):
        self.root = None

    def search(self, data):
        """이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""

        temp = self.root
        if data == temp.data:
            return temp
        while temp is not None:
            if temp.data == data:
                return temp
            elif data > temp.data:
                temp = temp.right_child
            else:
                temp = temp.left_child
        return None


# 빈 이진 탐색 트리 생성
bst = BinarySearchTree()

# 데이터 삽입
bst.insert(7)
bst.insert(11)
bst.insert(9)
bst.insert(17)
bst.insert(8)
bst.insert(5)
bst.insert(19)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(14)

# 노드 탐색과 출력
print(bst.search(7).data)
print(bst.search(19).data)
print(bst.search(2).data)
print(bst.search(20))

# 7
# 19
# 2
# None

➡ 이진 탐색 트리 삭제

• 삭제하려는 데이터를 갖는 노드를 먼저 찾아야 됨

삭제하려는 데이터가 leaf 노드의 데이터일 때

• 부모 노드의 자식 레퍼런스를 None으로 지정해 줌

class BinarySearchTree:
    """이진 탐색 트리 클래스"""
    def __init__(self):
        self.root = None


    def delete(self, data):
        """이진 탐색 트리 삭제 메소드"""
        node_to_delete = self.search(data)  # 삭제할 노드를 가지고 온다
        parent_node = node_to_delete.parent  # 삭제할 노드의 부모 노드

        # 경우 1: 지우려는 노드가 leaf 노드일 때 
        if node_to_delete.left_child is None and node_to_delete.right_child is None:
            if node_to_delete == self.root:
                self.root = None
            else:
                if node_to_delete is parent_node.left_child:
                    parent_node.left_child = None
                else:
                    parent_node.right_child = None

삭제하려는 데이터 노드가 하나의 자식 노드만 있을 때

• 자식 노드가 부모 노드의 자리를 차지하면 됨

class BinarySearchTree:
    """이진 탐색 트리 클래스"""
    def __init__(self):
        self.root = None


    def delete(self, data):
        """이진 탐색 트리 삭제 메소드"""
        node_to_delete = self.search(data)  # 삭제할 노드를 가지고 온다
        parent_node = node_to_delete.parent  # 삭제할 노드의 부모 노드

        # 경우 1: 지우려는 노드가 leaf 노드일 때
        if node_to_delete.left_child is None and node_to_delete.right_child is None:
            if self.root is node_to_delete:
                self.root = None
            else:  # 일반적인 경우
                if node_to_delete is parent_node.left_child: 
                    parent_node.left_child = None
                else:
                    parent_node.right_child = None

        # 경우 2: 지우려는 노드가 자식이 하나인 노드일 때:
        elif node_to_delete.left_child or node_to_delete.right_child is None: 
            if node_to_delete.left_child is None: 	# 오른쪽 자식이 하나라면
                if node_to_delete is self.root: 	# 지우려는게 root일 때
                    node_to_delete.right_child = self.root
                else:					# 지우려는게 부모의 왼쪽 자식이라면
                    if node_to_delete is parent_node.left_child: 	
                        parent_node.left_child = node_to_delete.right_child
                        node_to_delete.right_child.parent = parent_node
                    else: 				# 지우려는게 부모의 오른쪽 자식이라면
                        parent_node.right_child = node_to_delete.right_child
                        node_to_delete.right_child.parent = parent_node
                        
            else: 					# 왼쪽 자식이 하나라면
                if node_to_delete is self.root: 	# 지우려는게 root일 때
                    node_to_delete.left_child = self.root
                else: 					# 지우려는게 부모의 왼쪽 자식이라면
                    if node_to_delete is parent_node.left_child:
                        parent_node.left_child = node_to_delete.left_child
                        node_to_delete.left_child.parent = parent_node
                    else: 				# 지우려는게 부모의 오른쪽 자식이라면
                        parent_node.right_child = node_to_delete.left_child
                        node_to_delete.left_child.parent = parent_node

삭제하려는 데이터 노드가 두 개의 자식이 있을 때

• 지우려는 노드의 오른쪽 자식 노드를 root로 갖는 부분 트리에서 가장 작은 데이터 노드로 대체한다

class BinarySearchTree:
    """이진 탐색 트리 클래스"""
    def __init__(self):
        self.root = None


    def delete(self, data):
        """이진 탐색 트리 삭제 메소드"""
        node_to_delete = self.search(data)  # 삭제할 노드를 가지고 온다
        parent_node = node_to_delete.parent  # 삭제할 노드의 부모 노드

        # 경우 1: 지우려는 노드가 leaf 노드일 때
        if node_to_delete.left_child is None and node_to_delete.right_child is None:
            if self.root is node_to_delete:
                self.root = None
            else:  # 일반적인 경우
                if node_to_delete is parent_node.left_child: 
                    parent_node.left_child = None
                else:
                    parent_node.right_child = None

        # 경우 2: 지우려는 노드가 자식이 하나인 노드일 때:
        elif node_to_delete.left_child is None:  # 지우려는 노드가 오른쪽 자식만 있을 때:
            # 지우려는 노드가 root 노드일 때
            if node_to_delete is self.root:
                self.root = node_to_delete.right_child
                self.root.parent = None
            # 지우려는 노드가 부모의 왼쪽 자식일 때
            elif node_to_delete is parent_node.left_child:
                parent_node.left_child = node_to_delete.right_child
                node_to_delete.right_child.parent = parent_node
            # 지우려는 노드가 부모의 오른쪽 자식일 때
            else:
                parent_node.right_child = node_to_delete.right_child
                node_to_delete.right_child.parent = parent_node

        elif node_to_delete.right_child is None:  # 지우려는 노드가 왼쪽 자식만 있을 때:
            # 지우려는 노드가 root 노드일 때
            if node_to_delete is self.root:
                self.root = node_to_delete.left_child
                self.root.parent = None
            # 지우려는 노드가 부모의 왼쪽 자식일 때
            elif node_to_delete is parent_node.left_child:
                parent_node.left_child = node_to_delete.left_child
                node_to_delete.left_child.parent = parent_node
            # 지우려는 노드가 부모의 오른쪽 자식일 때
            else:
                parent_node.right_child = node_to_delete.left_child
                node_to_delete.left_child.parent = parent_node

        # 경우 3: 지우려는 노드가 2개의 자식이 있을 때
        else:
            successor = self.find_min(node_to_delete.right_child)
            successor_of_parent = successor.parent
            node_to_delete.data = successor.data
            
            # successor 노드 트리에서 삭제
            if successor.right_child is not None: # successor노드가 오른쪽 자식이 있을 때
                successor.right_child.right_child = node_to_delete.right_child    
            
            if successor is successor_of_parent.left_child: # successor 노드가 왼쪽 자식일 때
                successor_of_parent.left_child = None
            else: # successor 노드가 오른쪽 자식일 때
                successor_of_parent.right_child = None


    @staticmethod
    def find_min(node):
        """(부분)이진 탐색 트리의 가장 작은 노드 리턴"""
        # 코드를 쓰세요
        temp = node  # 탐색 변수. 파라미터 node로 초기화

        # temp가 node를 뿌리로 갖는 부분 트리에서 가장 작은 노드일 때까지 왼쪽 자식 노드로 간다
        while temp.left_child is not None:
            temp = temp.left_child      

        return temp  

시간 복잡도

1. 지우려는 데이터 노드가 leaf 노드일 때
2. 지우려는 데이터 노드가 하나의 자식이 있을 때
3. 지우려는 데이터 노드가 두 개의 자식이 있을 때

	탐색	탐색 후 단계들
경우 1	$O(h)$	$O(1)$
경우 2	$O(h)$	$O(1)$
경우 3	$O(h)$	$O(h)$

	탐색 + 탐색 후 단계들
경우 1	$O(h)$
경우 2	$O(h)$
경우 3	$O(h)$

➡ 이진 탐색 트리 높이

• 트리의 높이가 $h$라고 할 때, 기본적인 연산들 (탐색, 삽입, 삭제)의 시간 복잡도는 $O(h)$
• 이진 탐색 트리 연산들의 시간은 모두 $h$에 비례
• 노드들이 직선적인 모양으로 저장될수록 비효율적
  최악의 경우 : 모든 노드들이 직선 형태 : $O(n)$
• 균형 잡힌 완전 이진 트리에 가까울수록 효율적
  최선의 경우 : 완전 이진 트리 : $O(lg(n))$

이진 탐색 트리 연산	시간 복잡도
삽입	$O(h)$ (평균적 $O(lg(n))$, 최악 $O(n)$)
탐색	$O(h)$ (평균적 $O(lg(n))$, 최악 $O(n)$)
삭제	$O(h)$ (평균적 $O(lg(n))$, 최악 $O(n)$)

🙄 이진 탐색 트리로 딕셔너리 구현

---

➡ 딕셔너리용 이진 탐색 트리 노드

class Node:
	"""이진 탐색 트리 노드 클래스"""
    def __init__(self, key, value):
    	self.key = key
        self.value = value
        self.parent = None
        self.left_child = None
        self.right_child = None

시간 복잡도

이진 탐색 트리 연산	시간 복잡도
key를 이용한 key-value 데이터 쌍 삭제	$O(h)$ (평균적 $O(lg(n))$)
key를 이용한 노드 또는 value 탐색	$O(h)$ (평균적 $O(lg(n))$)
key-value 데이터 쌍 삽입	$O(h)$ (평균적 $O(lg(n))$)

🙄 이진 탐색 트리 평가

---

➡ 이진 탐색 트리 vs 해시 테이블

	이진 탐색 트리	해시 테이블
삽입	$O(h)$ (평균적 $O(lg(n))$, 최악 $O(n)$)	평균적 $O(1)$, 최악 $O(n)$
탐색	$O(h)$ (평균적 $O(lg(n))$, 최악 $O(n)$)	평균적 $O(1)$, 최악 $O(n)$
삭제	$O(h)$ (평균적 $O(lg(n))$, 최악 $O(n)$)	평균적 $O(1)$, 최악 $O(n)$

• 추상 자료형, 세트, 딕셔너리를 코드로 구현할 때, 일반적인 경우 해시 테이블이 더 효율적
• 하지만 세트의 데이터나 딕셔너리의 key를 정렬된 상태로 사용하고 싶을 때는 연산의 효율성은 조금 포기하고 이진 탐색 트리 사용