👀 이진 검색 트리

우리는 이것을 배우기 전에 왜 쓰는지 생각해보아야 한다. 왜 쓰는지 질문을 하고 거기에 대한 답을 낸 후에 배워야 한다.

왜 쓰냐고 묻는다면 값을 잘 저장하기 위해서이다. 배열 인덱스의 경우에 검색에 로그 n / 삽입 삭제에 n의 시간이 들어간다고 한다. 하지만 이진 검색 트리를 사용하게 된다면 검색 삽입 삭제 모두 평균적으로 로그 n의 시간이 소요 된다고 한다.

💡 어떤 구조인가?

이진 검색 트리를 만들 때 루트보다 큰 값은 오른쪽 작은 값은 왼쪽에 넣는다.
다음과 같은 식으로 말이다. 왼 쪽 서브트리에는 모두 30보다 작은 값이 들어가 있고 오른쪽 서브트리에는 모두 30보다 큰 값이 들어가 있다.

이러한 구조를 유지한채로 삽입과 삭제를 진행해야 한다.

먼저 말하지만 삽입의 경우는 간단하지만 삭제의 경우 조금 복잡하다.

삽입

삽입을 할 때 구조를 유지해야 한다는 점을 생각해보자. 만약 위 (a)의 상황에서 21을 넣는다면 어디로 갈까?
21은 30보다 작고 20보다 크고 25보다 작으니까 25의 왼쪽 자식이 될 것이다. 내가 지금 한 것을 코드로 옮기면 다음과 같다.

  def __insertItem(self, tnode, newItem):
    ## 맨 처음에 넣어줄 때 생각
    if tnode == None:
      tnode = TreeNode(newItem, None, None)
    elif (newItem < tnode.item):
      tnode.left = self.__insertItem(tnode.left, newItem)
    else: # newItem >= tnode.item
      tnode.right = self.__insertItem(tnode.right, newItem)
    return tnode
  
  def insert(self, newItem):
    self.__root = self.__insertItem(self.__root, newItem)

재귀적인 방식으로 구성된 코드라 조금 이해가 어려울 수도 있다. 하지만 코드를 짤 때 이것을 이해하는 것은 굉장히 중요하다.

만약 노드가 삽입해야 하는 자리까지 가면 ( 자식이 없으면 ) 재귀가 종료되는 구조이다.

루트에서 시작해서 쭉쭉 타고 내려가는 구조이다.

특이한 삽입

다음과 같이 이진 트리의 구조에 따라 비 대칭적인 트리가 생기기도 한다.

삭제

삭제는 크게 3가지 경우로 나뉜다.

Case 1: r 이 리프노드인 경우
Case 2: r의 자식이 하나인 경우
Case 3: r이 자식이 2인 경우

1,2 번은 쉽다. 그냥 없애거나 없앤 후에 부모 자식을 연결해주기만 하면 된다. 하지만 3번의 ㅇ경우를 생각하면 다음과 같이 된다.

28을 없애는데 저 자리에 무엇을 넣느냐 하는 문제이다.

저기에 표시되어 있는 30이 답이다. 왜 30이냐고 묻는다면 저 자리에는 오른 쪽 서브트리 중에서 젤 작은 값이 들어가야 한다. 때문에 30인 것이다. 30을 없앤 후에는 30의 오른 쪽 자식과 30의 부모를 연결시켜 주기만 하면 된다. 30의 경우는 서브트리에서 가장 작은 값이기 때문에 왼쪽 자식이 없는 경우이다.

쉽게 생각해서 단계를 나누면 다음과 같다.

1. 오른쪽 서브트리에서 가장 작은 값 찾기.
2. 가장 작은 값 삭제 후 원하는 값 자리에 넣기.

  def delete(self, x):
    self.__root = self.__deleteItem(self.__root, x)


  def __deleteItem(self, node, x):
    if node == None:
      return None
    elif x == node.item:
      node = self.__deleteNode(node)
    elif x < node.item:
      node.left = self.__deleteItem(node.left, x)
    elif x > node.item:
      node.right = self.__deleteItem(node.right, x)
    return node 

  def __deleteNode(self, node):
      # 3가지 케이스 존재! # 1. leaf 2. 자식 하나 3. 자식 둘
      if node.left == None and node.right == None:
        return None
      # 빈 자리 채울 노드 반환
      elif node.left == None:
        return node.right
      elif node.right == None:
        return node.left
      # 젤 복잡한 케이스 / 구조를 유지하며 삭제해야함 / 작은게 위로 가야지
      else:
        RightNodeItem, RightNode = self.__deleteMinItem(node.right)
        node.item = RightNodeItem
        node.right = RightNode
        return node
        
  def __deleteMinItem(self, node):
    if node.left == None:
      return node.item, node.right
    else:
      rtnItem, rtnNode = self.__deleteMinItem(node.left)
      node.left = rtnNode
      return rtnItem, node

코드는 다음과 같다.

조금 (많이) 어렵다.

__deleteMinItem 코드가 중요하다.

반환할 때 젤 작은 값을 아이템으로 반환하고 오른 쪽이 있던 것을 왼쪽으로 옮겨주는데 재귀적으로 되어 있어서 이해하기가 어렵다.

하나하나 곱씹으면서 이해해보도록 하자.