이진 탐색 트리

모든 노드에 대해서,

• 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
• 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진트리
  (중복 되는 데이터 원소는 없는 것으로 가정)

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

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

이진 탐색 트리의 추상적 자료구조

데이터 표현

각 노드는 (key, value)의 쌍으로

• 키를 이용해서 검색 가능
• 보다 복잡한 데이터 레코드로 확장 가능

연산 정의

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

코드구현

class Node:
	def __init__(self, key, data):
    	self.key = key
        self.data = data
        self.left = None
        self.right = None
        
    def inorder(self):
    	traversal = []
        if self.left:
        	traversal += self.left.inorder()
        traversal.append(self)
        if self.right:
        	traversal += self.right.inorder()
        return traversal
        
    def min(self):
    	if self.left: # 왼쪽이 작은 값이므로 
        	return self.left.min()
        else:
        	return self
            
    def max(self):
    	# min()과 완전히 대칭
    
    def lookup(self, key, parent = None):
    	if key < self.key:
        # 왼쪽 서브트리에 있을 경우
        	if self.left:
            	return self.left.lookup(key, self)
            else:
            	return None, None
        elif key > self.key:
        # 오른쪽 서브트리에 있을 경우
        	if self.right:
            	return self.right.lookup(key, self)
            else:
            	return None, None
        else:
        	return self, parent
            
        

class BinSerchTree:
	def __init__(self):
    	self.root = None
    
    def inorder(self):
    	if self.root:
        	return self.root.inorder()
        else:
        	return []
    
    def min(self):
    	if self.root:
        	return self.root.min()
        else:
        	return None
            
    def lookup(self, key):
    	if self.root:
        	return self.root.lookup(key)
        else: return None, None
    
    def insert(self, key, data):
    	if self.root:
        	self.root.insert(key, data)
        else:
        	self.root = Node(key, data)
    

lookup()

입력 인자: 찾으려는 대상 키
리턴: 찾은 노드와, 그것의 부모 노드 (각각, 없으면 None으로)

insert()

입력 인자: 키, 데이터 원소
리턴: 없음