이진 탐색 트리(BST) - Insert와 Delete 메서드

# 트리 노드 구현
class TreeNode:
  def __init__ (self, val, left=None, right=None):
    self.value = val
    self.leftChild = left
    self.rightChild = right

# BST의 이니셜라이저
class BST:
  def __init__ (self, root_value):
    self.root = None
    if root_value is None:
      raise ValueError("Root value is required")
    else:
      self.root = TreeNode(root_value)

    self.size = 1

class BST:

  [...]

  # loop로 구현
  def insert(self, key):
    # 중복 노드가 있는지 확인
    if self.search(key):
      raise ValueError("This key is duplicated with the existing node.")

    temp = self.root
    while temp:
      if temp.value > key:
        if temp.leftChild is None:
          temp.leftChild = TreeNode(key)
          self.size += 1
          break
        else:
          temp = temp.leftChild

      if temp.value < key:
        if temp.rightChild is None:
          temp.rightChild = TreeNode(key)
          self.size += 1
          break
        else:
          temp = temp.rightChild

class BST:

  [...]

  # 재귀로 구현
  def insert(self, key):
    if self.search(key):
      raise ValueError("This key is duplicated with the existing node.")
    return _insert(self.root, key)

  def _insert(self, node, key):
    temp = node
    if temp.value > key:
      if temp.leftChild is None:
        temp.leftChild = TreeNode(key)
        self.size += 1
      else:
        self._insert(temp.leftChild, key)

    if temp.value < key:
      if temp.rightChild is None:
        temp.rightChild = TreeNode(key)
        self.size += 1
      else:
        self._insert(temp.rightChild, key)

import bst # 이진탐색트리 모듈 가칭
a = bst.BST(1) # 1은 루트 노드의 값
a.insert(3)
a.insert(4)

class BST:

  [...]

  # BST가 중위순회하는 순서를 print하는 메서드
  def inorder(self):
    return self._inorder(self.root)

  def _inorder(self, node):
    if node is not None:
      self._inorder(node.leftChild)
      print(node.value, end= " ")
      self._inorder(node.rightChild)

  """중위순회 후계자를 리턴하는 메서드
  해당 노드의 오른쪽 서브트리에서 가장 작은 값이므로
  오른쪽 자식의 가장 왼쪽 자식을 리턴
  """
  def inorder_successor(self, node):
    return self.min_value_node(node.rightChild)

  def min_value_node(self, node):
    if node.lefChild:
      return self.min_value_node(node.leftChild)
    return node

class BST:

  [...]

  # key값을 가진 노드를 삭제
  def delete(self, key):
    self.root = self._delete(self.root, key)

  # _delete 메서드는 새로운 루트 노드를 리턴
  def _delete(self, node, key):
    # 노드 밸류가 찾는 값과 일치할 때
    if node.value is key:
      """노드의 자식이 2개인 경우
      inorder_successor 메서드를 호출해 후계 노드를 찾는다.
      찾은 후계 노드의 value를 복사한다.
      원래 후계 노드는 삭제해버린다.
      후계 노드 값을 복사한 노드를 리턴한다.
      """
      if node.rightChild and node.leftChild:
        successor = inorder_successor(node)
        node.value = successor.value
        successor = None
        return node
      """노드의 자식이 1개인 경우
      후계 노드는 유일한 자식이 되므로
      노드는 삭제해버리고 자식(후계 노드)를 리턴한다.
      """
      elif node.leftChild or node.rightChild:
        node = None
        return node.leftChild or node.rightChild
      """노드의 자식이 0개인 경우
      후계 노드가 존재하지 않으므로 노드를 삭제한 후 리턴한다.
      """
      else:
        node = None
        return node

    """노드 밸류가 key와 일치하지 않을 때
    key와 대소비교를 통해 다시 _delete 메서드를 재귀적으로 호출한다.
    다만 여기서 재귀적으로 호출한 결과를 어디에 대입하고 있느냐가 중요하다.
    """
    else:
      if node.value > key:
        node.leftChild = self._delete(node.leftChild,key)
      if node.value < key:
        node.rightChild = self._delete(node.rightChild,key)
     	return node