[Python 자료구조 #탐색트리2] 이진탐색트리를 이용한 맵

* 이진탐색트리를 이용한 맵

↓BSTNode(), inorder(), count_node(),search_bst()함수 코드참고.(이전 블로그 글 참고)

class BSTNode:

    def __init__(self, key, value):

        self.key = key

        self.value = value

        self.left = None

        self.right = None

def inorder(n):  # 중위 순회 함수

    if n is not None:

        inorder(n.left)  # 왼쪽 서브트리 처리

        print(n.key, end=" ")  # 루트노드 처리(화면 출력)

        inorder(n.right)

def count_node(n):

    if n is None:

        return 0

    else:

        return 1 + count_node(n.left) + count_node(n.right)

def search_bst(n, key):

    if n == None:

        return None

    elif key == n.key:

        return n

    elif key < n.key:

        return search_bst(n.left, key)

    else:

        return search_bst(n.right, key)

이진탐색트리(Binary Search tree)을 이용한 Map 구현

# BSTMap의 ADT 구현
class BSTMap:
    def __init__(self):
        self.root = None

    def isEmpty(self):
        return self.root == None

    def clear(self):
        self.root = None

    def size(self):
        return count_node(self.root)

    def search(self, key):
        return search_bst(self.root, key)

    def searchValue(self, key):
        return search_value_bst(self.root, key)

    def findMax(self):
        return search_max_bst(self.root)

    def findMin(self):
        return search_min_bst(self.root)

    def insert(self, key, value=None):	# 삽입연산
        n = BSTNode(key, value)
        if self.isEmpty():
            self.root = n
        else:
            insert_bst(self.root, n)

    def delete(self, key):	# 삭제 연산
        delete_bst(self.root, key)

    def display(self, msg="BSTMap :"):
        print(msg, end="")
        inorder(self.root)
        print()

아래 BST구조 그림

map = BSTMap()
data = [35, 18, 7, 26, 12, 3, 68, 22, 30, 99]

print("[삽입 연산] : ", data)
for key in data:
    map.insert(key)
map.display("[중위 순회] : ")

if map.search(26) != None:		# 탐색연산 테스트
    print("[탐색  26 ] : 성공")
else:
    print("[탐색  26 ] : 실패")
if map.search(25) != None:		# 탐색연산 테스트
    print("[탐색  25 ] : 성공")
else:
    print("[탐색  25 ] : 실패")

map.delete(3)				# 삭제연산 테스트
map.display("[   3 삭제] : ")
map.delete(68)				# 삭제연산 테스트
map.display("[  68 삭제] : ")
map.delete(18)				# 삭제연산 테스트
map.display("[  18 삭제] : ")
map.delete(35)				# 삭제연산 테스트
map.display("[  35 삭제] : ")
----------------------------------------------------------
[삽입 연산] :  [35, 18, 7, 26, 12, 3, 68, 22, 30, 99]
[중위 순회] : 3 7 12 18 22 26 30 35 68 99
[탐색  26 ] : 성공					# 26은 트리에 있고
[탐색  25 ] : 실패					# 25는 트리에 없음
[   3 삭제] : 7 12 18 22 26 30 35 68 99
[  68 삭제] : 7 12 18 22 26 30 35 99
[  18 삭제] : 7 12 22 26 30 35 99
[  35 삭제] : 7 12 22 26 30 99