[프로그래머스 알고리즘] 20강: 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리 (Binary Search Tree)

모든 노드에 대해서,

왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값도가 큰 성질을 만족하는 이진트리

(중복데이터는 없는 것으로 가정)

 

 

정렬된 배열을 이용한 이진 탐색과의 비교

• 장점 : 데이터 원소의 추가, 삭제가 용이
• 단점 : 공간 소요가 큼

항상 O(logn)의 탐색 복잡도를 가지는가? --> NO

각 노드는 (key, value)의 쌍으로 키를 이용하여 검색 가능. 보다 복잡한 데이터 레코드로 확장 가능

 

연산의 정의

• insert(key, data) - 트리에 주어진 데이터 원소를 추가
• remove(key) - 특정 원소를 트리에서 삭제
• lookup(key) -  특정 원소를 검색
• inorder() - 키의 순서대로 데이터 원소를 나열
• min(), max() -최소 키, 최대 키를 가지는 원소를 각각 탐색

 

이진 탐색 트리에 원소 삽입

key값과 3을 비교해 작으면 left node로, 크면 right node로 이동

 코드 구현 - initialization

class Node:
	def __init__(self, key, data):
    	self.key = key
        self.data = data
        self.left = None
        self.right = None
        
class BinSearchTree:
	def __init__(self):
		self.root = None

---

20강 실습: 이진 탐색 트리의 원소 삽입 연산 구현

class Node:

    def __init__(self, key, data):
        self.key = key
        self.data = data
        self.left = None
        self.right = None


    def insert(self, key, data):
        if self.key > key:
            if self.left:
                return self.left.insert(key, data)
            else:
                self.left = Node(key, data)
            
        elif self.key < key:
            if self.right:
                return self.right.insert(key, data)
            else:
                self.right = Node(key, data)

        else:
            raise KeyError()


    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
            traversal += self.right.inorder()
        return traversal


class BinSearchTree:

    def __init__(self):
        self.root = None


    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)


    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []