이진 탐색 트리를 이용하면 추상 자료형 딕셔너리를 구현할 수 있다고 했다.

딕셔너리 (또는 맵)는 key - value 데이터 쌍을 찾고, 저장하고, 지울 수 있게 해주는 추상 자료형이다.

이진 탐색 트리를 사용해서 어떻게 딕셔너리를 구현할 수 있는지 알아보자.

이진 탐색 트리 Node

딕셔너리용 이진 탐색 트리 Node

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

이렇게 이진 탐색 트리 Node 를 새롭게 정의해 주면된다.

전에는 Node의 데이터, 변수 data를 이용해서 원하는 Node 를 삽입, 삭제, 탐색을 했다.

이렇게 Node를 새롭게 정의하면 Node를 data가 아닌 변수 key를 사용해서 찾고 저장하고 지운다.

그러니까 특정 key가 주어졌을 때, 이 key에 해당하는 Node를 찾고, 저장하고 지울 수 있는 것이다.

시간 복잡도

연산들 자체는 data 변수 대신 key를 사용하는 것으로 바뀌었을 뿐이다.

시간 복잡도가 바뀌는 건 없다.