이진탐색트리.md

이진탐색트리(binary search tree)

• 다음 속성을 가진 이진 트리 자료 구조
  • 각 노드는 유일한 값을 가지고, 값은 순서를 가짐
  • 왼쪽 서브트리는 그 노드의 값보다 작은 값들을 지닌 노드
  • 오른쪽 서브트리는 그 노드의 값보다 큰 값들을 지닌 노드

이진 트리 설계

class Node:
    def __init__(self, key,value, left,right):
        self.key = key     # 키
        self.value = value # 값
        self.left = left   # 왼쪽 자식 참조
        self.right = right # 오른쪽 자식 참조

class BinarySearchTree():	
	# 생성자
	def __init__(self)->None:
	
	# 검색하는 메소드
	def search(self, key)->int:
	
	# 노드 추가하는 메소드
	def add(self,key,value)->bool:
	
	# 노드 삭제하는 메소드
	def remove(self, key)-> bool:

• Node 클래스로 각 노드를, BinarySearchTree 클래스를 활용하여 전체 트리를 구성

def __init__(self)->None:
        self.root = None # 루트 설정

• 생성 후 트리가 비어 있으므로 None을 설정

탐색

• 전체 노드 탐색은 이진 트리에서 중위순회(In-order)로 탐색할 수 있음
  • 왼쪽 서브트리 >> 루트 >> 오른쪽 서브트리
• 특정 노드를 탐색한다면
  • 더 작은 값을 탐색할 때 왼쪽 서브트리 탐색
  • 더 큰 값을 탐색할 때 오른쪽 서브트리 탐색

def search(self, key)->int:
        node = self.root          # 루트에서 시작
        while True:
            if node is None: 
                return -1         # 탐색 실패
            if key == node.key:
                return node.value # 탐색 성공
            elif key < node.key:
                node = node.left  # 왼쪽 서브 트리에서 탐색
            else:
                node = node.right # 오른쪽 서브 트리에서 탐색

삽입

• 각 노드가 삽입될 때, 이진 탐색 트리 조건이 유지되어야 함
• 다음과 같은 과정을 거쳐 삽입
  • root가 없으면 root로, 있다면 root부터 탐색
  • 현재 노드에서 탐색 시작
  • 만약 현재 노드가 추가하려는 노드이면 실패
  • 현재 노드보다 더 작은 값을 추가할 때,
    • 왼쪽 노드가 없으면, 삽입하고 종료
    • 왼쪽 노드가 있으면, 현재 노드를 왼쪽 노드로 옮겨서 다시 탐색
  • 현재 노드보다 더 큰 값을 추가할 때,
    • 오른쪽 노드가 없으면, 삽입하고 종료
    • 오른쪽 노드가 있으면, 현재 노드를 오른쪽 노드로 옮겨서 다시 탐색
  • 삽입을 성공할 때까지 이 과정을 반복

def add(self,key,value)->bool:
    def add_node(node, key,value)->None:
        if key == node.key: 
            return False
        elif key < node.key:
            if node.left is None:
                node.left = Node(key,value,None,None)
            else:
                add_node(node.left,key,value)
        else:
            if node.right is None:
                node.right = Node(key,value,None,None)
            else:
                add_node(node.right,key,value)
        return True
    if self.root is None:
        self.root = Node(key,value,None,None)
        return True
    else: 
        return add_node(self.root,key,value)

삭제

• 삭제 과정은 경우에 따라 분류하여 시행
• 해당 노드를 찾은 후,
  • 자식 노드가 없는 경우와 자식 노드와 1개, 2개인 경우에 따라 분류
• 자식 노드가 없는 경우
  • 부모 노드에서 자식 노드 삭제
• 자식 노드가 1개인 경우 자식노드를 자신의 위치에
• 자식 노드가 2개인 경우 대체노드를 찾아서 대체

def remove(self, key)-> bool:
    node = self.root 
    parent = None 
    is_left_child = True 

    # 삭제할 노드 탐색
    while True:
      if node is None:
          return False
      if key == node.key:
          break
      else:
          parent = node
          if key < node.key:
              node = node.left
              is_left_child = True 
          else:
              node = node.right
              is_left_child = False 
    
    if node.left is None: 
        if node is self.root: 
            self.root = node.right
	elif is_left_child: 
            parent.left = node.right 
        else: 
            parent.right = node.right
    
    elif node.right is None: 
        if node is self.root: 
            self.root = node.left 
        elif is_left_child:
            parent.left = node.left 
        else:
            parent.right = node.left 

# 자식이 2개 있는 노드이면
else: 
    parent = node
    node_max_left = node.left 
    is_left_child = True 
    
    while node_max_left.right is not None:
        parent = node_max_left
        node_max_left = node_max_left.right
        is_left_child = False

    node.key = node_max_left.key
    node.value = node_max_left.value

    if is_left_child:
        parent.left = node_max_left.left
    else:
        parent.right = node_max_left.left
return True

참조

• wikipedia
• BST 탐색/삽입/삭제