이진탐색트리 탐색과 삽입(BST Search & Insert )

1. 탐색함수(Search)

이진탐색트리 T의 노드 v와 v의 자손 노드들 중에서 key값을 갖는 노드를 찾아 리턴
없다면 None을 리턴

①

def get(self,k): #탐색 연산
    return self.get_item(self.root,k)
def get_item(self,n,k):
    if n==None: #탐색 실패
        return none 
    if n.key<k:   #k가 노드의 key보다 크면 오른쪽 서브트리 탐색
        return self.get_item(n.right,k)
    elif n.key>k:  #k가 노드의 key보다 작으면 왼쪽 서브트리 탐색
        return self.get_item(n.left,k)
    else:
        return n.value   #탐색 성공

②

def find_loc(self, key):
    if self.size == 0: 
        return None  #탐색 실패
    p = None        # P는 v의 부모
    v = self.root
    while v:          # while v!=None
	if v.key == key: return v
	else:
       	   if v.key < key:
	     p = v
	     v = v.right
	   else:
             p = v
	     v = v.left
    return p 

2. 삽입(Insert)

이진탐색트리에서 삽입은 탐색 연산과 비슷하다.

① 탐색 연산의 마지막에서 None이 반환 되어야 할 상황에서 None을 반환하는 대신,
② 삽입하고자 하는 [key,value]를 갖는 새로운 노드를 생성하고,
③ 새 노드를 부모노드와 연결하면 삽입 연산이 완료된다.
단, 이미 트리에 존재하는 key를 삽입할 경우, value만을 갱신한다.

①

def put(self,key,value): # 삽입 연산	
    self.root=self.put_item(self.root,key,value)  # 루트와  put_item()이 리턴하는 노드를 재연결

def put_item(self,n,key,value):
    if n==None:
        return Node(key,value) # 새 노드 생성
    if n.key < key:
        n.right= self.put_item(n.right,key,value) # n의 오른쪽 자식과 put_item()이 리턴하는 노드를 재연결
    elif n.key > key: 
       n.left=self.put_item(n.left,key,value)  # n의 왼쪽 자식과  put_item()이 리턴하는 노드를 재연결
    else:
        n.value=value # key가 이미 있으므로 value만 갱신
    return n  #부모노드와 연결하기 위해 노드 n을 리턴

① 이진탐색트리이기 때문에,key가 들어갈 위치가 정해진다.
② 그림의 왼쪽 트리에 key=16을 삽입하고 싶다면, 먼저 삽입될 위치를 find_loc함수를 이용해 찾는다.
③ 값의 크기에 의해 17의 왼쪽에 삽입되어야 한다.
④ find_loc함수는 16의 부모노드가 될 17노드를 리턴한다.

②

def insert(self, key):
    v = Node(key)
    if self.size == 0:
        self.root = v
    else:
        p = self.find_loc(key)
        if p and p.key != key:  #p는 v의 부모
            if p.key < key:  #check if left/right
                p.right = v
            else:
                p.left = v
                v.parent = p
    self.size += 1
    return v