자료구조 & 알고리즘 11. 트리와 그래프

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

class BinarySearchTree :
  def __init__(self, data) :
    self.root = Node(data) # 루트노드에 값을 하나 넣는다.

  def insert(self, data) :
    self.current_node = self.root
    while True :
      # 현재 넣으려는 값이 루트값보다 작을경우 왼쪽으로
      if data < self.current_node.data :
        # 왼쪽노드가 있다면 계속 탐색
        if self.current_node.left != None :
          self.current_node = self.current_node.left
        else : # 없다면 그자리에 값 넣기
          self.current_node.left = Node(data)
          break
      else : # 현재 넣으려는 값이 루트값보다 클경우 오른쪽으로
        if self.current_node.right != None :
          self.current_node = self.current_node.right
        else :
          self.current_node.right = Node(data)
          break

  def search(self, data) :
    self.current_node = self.root
    while self.current_node :
      if self.current_node.data == data :
        return True
      elif data < self.current_node.data :
        self.current_node = self.current_node.left
      else :
        self.current_node = self.current_node.right
    return False

  def delete(self, data) :
    # 삭제할 노드가 있는지 확인하기
    searched = False # 삭제할 값을 찾았는지 여부를 알려주는 searched
    self.current_node = self.root # 현재노드
    self.parent_node = self.root # 부모노드
    while self.current_node : # 현재 노드가 있는 동안 반복
      # 만약 현재 노드가 삭제하려는 값과 같다면 탐색 중지
      if self.current_node.data == data :
        searched = True
        break
      # 만약 현재 노드가 삭제하려는 값보다 크다면 왼쪽 탐색
      elif data < self.current_node.data :
        self.parent_node = self.current_node
        self.current_node = self.current_node.left
      else : # 현재 노드가 삭제하려는 값보다 작다면 오른쪽으로
        self.parent_node = self.current_node
        self.current_node = self.current_node.right
    if searched == False :
      return False

    # 삭제하려는 값을 찾은 경우 이곳으로들어온다.
    # 1. 만약 삭제하려는 노드가 자식이 없는 리프노드라면..
    if self.current_node.left == None and self.current_node.right == None :
      if data < self.parent_node.data : # 현재 값이 부모의 왼쪽노드라면 
        self.parent_node.left = None # 부모의 왼쪽인 나와 연결 끊기
      else : # 부모의 오른쪽 노드라면
        self.parent_node.right = None # 부모의 오른쪽인 나와 연결 끊기

    # 2. 만약 삭제하려는 노드가 자식노드가 있다면...
    # 2-1. 자식노드가 왼쪽만 있다면
    elif self.current_node.left != None and self.current_node.right == None :
      # 나의 부모와 나의 자식을 이어주자.
      if data < self.parent_node.data : # 2-1-1. 내 자식이 왼쪽
        self.parent_node.left = self.current_node.left
      else : # 2-1-2. 내 자식이 오른쪽
        self.parent_node.right = self.current_node.left
    # 2-2. 자식노드가 오른쪽이라면 
    elif self.current_node.left == None and self.current_node.right != None :
      # 나의 부모와 나의 자식을 이어주자.
      if data < self.parent_node.data : # 2-2-1. 내 자식이 왼쪽
        self.parent_node.left = self.current_node.right
      else : # 2-2-2. 내 자식이 오른쪽
        self.parent_node.right = self.current_node.right

    # 3. 삭제하려는 노드가 자식노드가 두개 있다면...
    elif self.current_node.left != None and self.current_node.right != None :
      if data < self.parent_node.data : # 삭제할 노드가 부모의 왼쪽 자식이었다면
        # 3-1. 삭제하려는 노드의 오른쪽 중 가장 작은 값이 현재 자리에 와야함(혹은 왼쪽 중 가장 큰값)
        self.change_node = self.current_node.right # 빈자리를 채워줄 노드
        self.change_node_parent = self.current_node.right # 빈자리를 채우는 노드의 부모 노드
        while self.change_node.left != None : # 삭제노드의 오른쪽 자식을 탐색하여 가장 작은 값을 찾는다.
          self.change_node_parent = self.change_node
          self.change_node = self.change_node.left
        if self.change_node.right != None : # 옮기려는 자식에 오른쪽 자식이 있다면
          self.change_node_parent.left = self.change_node.right # 옮길자식의 부모와 자식을 이어준다.
        else : # 옮기려는 자식에 오른쪽 자식이 없다면(=리프노드)
          self.change_node_parent.left = None
        self.parent_node.left = self.change_node # 빈자리에 바꿀 노드를 넣는다.
        self.change_node.right = self.current_node.right # 바꾼노드의 오른쪽에 기존에 있던 노드들을 이어준다.
        self.change_node.left = self.change_node.left # 바꾼 노드의 왼쪽에 기존에 있던 노드들을 이어준다.
      else : # 삭제할 노드가 부모의 오른쪽 자식이었다면
        self.change_node = self.current_node.right
        self.change_node_parent = self.current_node.right
        while self.change_node.left != None : # 빈자리를 대신할 노드를 찾기
          self.change_node_parent = self.change_node
          self.change_node = self.change_node.left
        if self.change_node.right != None : # 대신할 노드의 오른쪽에 자식이 있다면
          self.change_node_parent.left = self.change_node.right # 빈자리의 부모-빈자리의 오른쪽 연결
        else : # 옮기려는 자식에 오른쪽 자식이 없다면(=리프노드)
          self.change_node_parent.left = None
        self.parent_node.right = self.change_node # 빈자리에 바꿀 노드를 넣는다.
        self.change_node.right = self.current_node.right # 바꾼 노드의 오른쪽에 기존 노드들을 이어준다. 
        self.change_node.left = self.current_node.left# 바꾼 노드의 왼쪽에 기존에 있던 노드들을 이어준다.
    return True