이진 탐색 트리 Binary Search Tree

딕셔너리나 세트라는 추상자료형을 구현하는 데에 사용할 수 있다.

이진탐색트리는 조건이 있는데,

1. 우선 이진트리여야 하고
2. 왼쪽 부분트리에 있는 모든 노드는 그 노드의 데이터보다 작아야 한다.
3. 오른쪽 부분 트리에 있는 모든 노드는 그 노드의 데이터보다 커야 한다.

이렇게 모든 노드에 대해 왼쪽 자식은 작은 수, 오른쪽 자신은 큰 수를 넣는다.

위처럼 모든 노드에 대해 동일하다.

이진 탐색 트리를 이용하면 저장한 데이터를 쉽게 찾을 수 있다. 저장한 데이터를 찾는 연산을 탐색이라고 한다.

예를 들어 4라는 수를 찾아보자.
먼저 루트노드인 8보다 작으니 왼쪽에 있는 3으로 간다.
3보다 4가 크니 오른쪽 자식노드인 6으로 간다.
6보다 작으니 왼쪽자식 노드로 이동하면 4를 찾을 수 있다.

이진탐색트리는 완전이진트리라는 보장은 없다. 따라서 배열이나 파이썬 리스트를 써서 구현하지 않고, 노드 클래스 정의한 후 여러 노드 인스턴스를 생성하고 이 인스턴스를 연결시켜 구현한다.

class Node:
  def __init__(self, data):
    self.data = data
    self.parent = None
    self.left_child = None
    self.right_child = None

이진탐색트리는 노드들을 어떻게 연결하고, 삭제하고, 찾는지가 핵심이다.
그래서 노드 클래스 자체는 바뀌는 내용이 많지 않다.

이진탐색트리의 각 노드는 부모 노드에 대한 레퍼런스도 가지고 있다!!
노드 클래스를 정의할 때 위처럼 부모 노드에 대한 레퍼런스도 정의한다.

1. 이진탐색트리 출력

이진탐색트리는 왼쪽자식이 작고, 오른쪽자식은 크다.
따라서 in-order 순회를 사용해 차례로 출력하면 정렬되어 출력할 수 있다.

• in-order 순회

  1. 왼쪽 부분 트리를 in-order 순회한다
  2. 현재 노드의 데이터를 출력한다
  3. 오른쪽 부분 트리를 in-order 순회한다

  • in-order 순회 더 자세히 알아보기

따라서 in-order 순회를 이용하면 코드는 아래와 같다.

class Node:
  """이진 탐색 트리 노드 클래스"""
  def __init__(self, data):
    self.data = data
    self.parent = None
    self.left_child = None
    self.right_child = None

def print_inorder(node):
  """주어진 노드를 in-order로 출력해주는 함수"""
  if node is not None:
    print_inorder(node.left_child)
    print(node.data)
    print_inorder(node.right_child)


class BinarySearchTree:
  """이진 탐색 트리 클래스"""
  def __init__(self):
    self.root = None

  def print_sorted_tree(self):
    """이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
    print_inorder(self.root)

2. 이진탐색트리 삽입

이진탐색트리에 새로운 데이터를 삽입 이후에도 이진탐색트리 속성이 유지되어야 한다.

위처럼 생긴 이진탐색트리에 13 이라는 수를 추가하고 싶은 상황이다.

우선 root노드에서부터 시작한다.
루트노드의 수인 12보다 크니 오른쪽으로 이동한다.
그다음 18 보다 작으니 왼쪽으로 이동한다.
15 보다 작으니 왼쪽으로 이동하는데, 왼쪽자식이 없으니 여기에 13을 삽입하면 된다.

일반화 해서 설명하면 아래와 같다.

이진탐색트리 삽입 연산 방식

1. 새로운 노드를 생성한다.
2. root 노드부터 데이터를 비교하면서 새로운 노드를 저장할 위치를 찾는다.
   • 새로운 노드의 데이터가 더 크면, root 노드의 오른쪽 부분 트리에 저장
   • 더 작으면, root 노드의 왼쪽 부분 트리에 저장
3. 찾은 위치에 새롭게 만든 노드를 연결한다.

이진탐색트리 삽입 연산의 시간복잡도

• 이진탐색트리의 높이가 h일때, 최악의 경우 맨 아래에 연결되는 상황이라면 $O(h+1)$의 시간복잡도가 걸린다.
• 아래 이진탐색트리에서 16이라는 수를 삽입하는 경우,
  높이는 h=3 이고, 12, 18, 15, 17, 과 한 번씩 비교하니 총 4번을 비교하는 연산을 하게 된다.
  
• 새로운 노드를 생성 : $O(1)$
• 찾은 위치에 새롭게 만든 노드를 연결 : $O(1)$
• 삽입 시간 복잡도 : $O(1+h+1) = O(h)$

이진탐색트리 삽입 구현

아래는 삽입 메서드를 구현한 거다.

    def insert(self, data):
        new_node = Node(data)  # 삽입할 데이터를 갖는 새 노드 생성

        # 트리가 비었으면 새로운 노드를 root 노드로 만든다
        if self.root is None:
           self.root = new_node
           return

        compare_node = self.root
        while True:
          if new_node.data < compare_node.data:
            if compare_node.left_child == None:
              compare_node.left_child = new_node
              new_node.parent = compare_node
              return
            compare_node = compare_node.left_child

          if new_node.data > compare_node.data:
            if compare_node.right_child == None:
              compare_node.right_child = new_node
              new_node.parent = compare_node
              return
            compare_node = compare_node.right_child

위 메서드를 클래스에 추가하고, 테스트해보자.

class Node:
    """이진 탐색 트리 노드 클래스"""
    def __init__(self, data):
        self.data = data
        self.parent = None
        self.right_child = None
        self.left_child = None


def print_inorder(node):
    """주어진 노드를 in-order로 출력해주는 함수"""
    if node is not None:
        print_inorder(node.left_child)
        print(node.data)
        print_inorder(node.right_child)


class BinarySearchTree:
    """이진 탐색 트리 클래스"""
    def __init__(self):
        self.root = None


    def insert(self, data):
        new_node = Node(data)  # 삽입할 데이터를 갖는 새 노드 생성

        # 트리가 비었으면 새로운 노드를 root 노드로 만든다
        if self.root is None:
           self.root = new_node
           return

        compare_node = self.root
        while True:
          if new_node.data < compare_node.data:
            if compare_node.left_child == None:
              compare_node.left_child = new_node
              new_node.parent = compare_node
              return
            compare_node = compare_node.left_child

          if new_node.data > compare_node.data:
            if compare_node.right_child == None:
              compare_node.right_child = new_node
              new_node.parent = compare_node
              return
            compare_node = compare_node.right_child


    def print_sorted_tree(self):
        """이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
        print_inorder(self.root)  # root 노드를 in-order로 출력한다


# 빈 이진 탐색 트리 생성
bst = BinarySearchTree()

# 데이터 삽입
bst.insert(7)
bst.insert(11)
bst.insert(9)
bst.insert(17)
bst.insert(8)
bst.insert(5)
bst.insert(19)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(14)

# 이진 탐색 트리 출력
bst.print_sorted_tree()

# 2
# 3
# 4
# 5
# 7
# 8
# 9
# 11
# 14
# 17
# 19

3. 이진탐색트리 탐색

• 탐색 은 특정 데이터를 갖는 노드를 리턴하는 연산이다.

탐색 연산 순서

1. 주어진 노드의 데이터와 탐색하려는 데이터 비교 (root 노드에서 시작)
2. 탐색하려는 데이터가 더 크면 노드의 오른쪽 자식으로 간다
3. 탐색하려는 데이터가 더 작으면 노드의 왼쪽 자식으로 간다
4. 데이터를 갖는 노드를 찾을 때까지 1-3번을 반복한다. 탐색하려는 노드를 찾으면 리턴한다.

탐색연산의 시간복잡도

• 트리의 높이 : h라 할 때, 최악의 경우 $O(h+1)$번 비교해야 한다.

이진탐색트리 탐색 구현

이진탐색트리의 탐색연산은 아래처럼 구현할 수 있다.
위에서 만든 class에 search 매서드를 추가해주자.

def search(self, data):
    """이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""
    compare_node = self.root
    while True:
      if data < compare_node.data:
        if compare_node.left_child == None:
          return None
        compare_node = compare_node.left_child 

      if data > compare_node.data:
        if compare_node.right_child == None:
          return None
        compare_node = compare_node.right_child

      if data == compare_node.data:
        return compare_node

테스트 코드

# 노드 탐색과 출력
print(bst.search(7).data)
print(bst.search(19).data)
print(bst.search(2).data)
print(bst.search(20))
"""
7
19
2
None
"""

4. 이진탐색트리 find_min 메서드

이번에는 설정한 노드를 루트노드로 삼고, 그 중 가장 작은 데이터를 추출하는 메서드를 만들어보자.

find_min()메소드에 14를 파라미터로 넘기면 빨간 부분트리 안에서 가장 작은 노드 12가 리턴된다.

아래는 find_min메서드를 구현한 코드이다.
위에서 만든 class에 추가해주자.

@staticmethod
def find_min(node):
    """(부분)이진 탐색 트리의 가장 작은 노드 리턴"""
    while node.left_child != None:
      node = node.left_child

    return node

테스트 코드

print(bst.find_min(bst.root).data)  # 전체 이진 탐색 트리에서 가장 작은 노드
print(bst.find_min(bst.root.right_child).data)  # root 노드의 오른쪽 부분 트리에서 가장 작은 노드
"""
2
8
"""

근데 클래스 안에 넣는 함수인데 파라미터에 self가 없고, 메서드 위에 @staticmethod가 붙어있다.
이것을 인스턴스를 통하지 않고 클래스에서 바로 호출할 수 있는 정적 메서드라고 한다.
정적 메서드는 self를 받지 않으므로 인스턴스 속성에 접근할 수 없고, 인스턴스 속성, 인스턴스 메서드가 필요 없을 때 사용한다.

여기에서는 node의 left_child가 None이 될 때까지 계속 left_child의 left_child를 내려가다가 만약 어떤 Node의 left_child가 None이라면 그 때의 Node를 반환한다.

이 과정에서 인스턴스 데이터에 대해 처리하는 부분이 없으니, 위 과정만 진항하는 거라 정적 메소드로 만든다.

사실 이 부분이 잘 이해가 안 돼서 객체지향 부분을 좀 더 공부해 봐야겠다..

• 코드잇 객체지향 프로그래밍

5. 이진탐색트리 삭제

삭제 연산의 경우, 몇 가지 경우의 수를 생각해봐야 한다.

• 경우1 : 삭제하려는 데이터가 leaf 노드의 데이터일 때
  • 7을 지우고 싶은 경우, 부모노드인 6의 오른쪽 자식 레퍼런스를 None으로 지정한다.
  • 지우려는 노드가 부모노드의 왼쪽자식인지, 오른쪽자식인지 확인하고 각 경우에 맞게 처리해주면 된다.
    
• 경우 1을 코드로 구현하면 아래와 같다.

def delete(self, data):
    """이진 탐색 트리 삭제 메소드"""
    node_to_delete = self.search(data)  # 삭제할 노드를 가지고 온다
    parent_node = node_to_delete.parent  # 삭제할 노드의 부모 노드

    # 경우 1: 지우려는 노드가 leaf 노드일 때
    if node_to_delete.right_child == None and node_to_delete.left_child == None:
      if node_to_delete.data < parent_node.data:
        parent_node.left_child = None
      elif node_to_delete.data > parent_node.data:
        parent_node.right_child = None

• 해설은 아래처럼 짰다.

# 경우 1: 지우려는 노드가 leaf 노드일 때
if node_to_delete.left_child is None and node_to_delete.right_child is None:
    if self.root is node_to_delete:
        self.root = None
    else:  # 일반적인 경우
        if node_to_delete is parent_node.left_child: 
            parent_node.left_child = None
        else:
            parent_node.right_child = None

• 경우2 : 삭제하려는 데이터 노드가 하나의 자식노드만 있을 때
  • 아래처럼 10을 지우고 싶은 경우, 자식노드인 14가 부모 노드의 자리를 차지하면 된다.
  • 그리고 14의 부모노드를 8로 잘 지정한다.
    
• 경우 2를 코드로 구현하면 아래와 같다.

# 경우 2: 지우려는 노드가 자식이 하나인 노드일 때:
if parent_node.data > node_to_delete.data:
    if node_to_delete.left_child is None and node_to_delete.right_child is not None:
        parent_node.left_child = node_to_delete.right_child
        node_to_delete.right_child.parent = parent_node
    else:
        parent_node.left_child = node_to_delete.left_child
        node_to_delete.left_child.parent = parent_node
        
else:
    if node_to_delete.left_child is None and node_to_delete.right_child is not None:
        parent_node.left_child = node_to_delete.right_child
        node_to_delete.right_child.parent = parent_node
    else:
        parent_node.left_child = node_to_delete.left_child
        node_to_delete.left_child.parent = parent_node

• 해설도 비슷한데, 지우려는 노드가 root노드일때까지 고려해서 짰다.

# 경우 2: 지우려는 노드가 자식이 하나인 노드일 때:
elif node_to_delete.left_child is None:  # 지우려는 노드가 오른쪽 자식만 있을 때:
    # 지우려는 노드가 root 노드일 때
    if node_to_delete is self.root:
        self.root = node_to_delete.right_child
        self.root.parent = None
    # 지우려는 노드가 부모의 왼쪽 자식일 때
    elif node_to_delete is parent_node.left_child:
        parent_node.left_child = node_to_delete.right_child
        node_to_delete.right_child.parent = parent_node
    # 지우려는 노드가 부모의 오른쪽 자식일 때
    else:
        parent_node.right_child = node_to_delete.right_child
        node_to_delete.right_child.parent = parent_node

elif node_to_delete.right_child is None:  # 지우려는 노드가 왼쪽 자식만 있을 때:
    # 지우려는 노드가 root 노드일 때
    if node_to_delete is self.root:
        self.root = node_to_delete.left_child
        self.root.parent = None
    # 지우려는 노드가 부모의 왼쪽 자식일 때
    elif node_to_delete is parent_node.left_child:
        parent_node.left_child = node_to_delete.left_child
        node_to_delete.left_child.parent = parent_node
    # 지우려는 노드가 부모의 오른쪽 자식일 때
    else:
        parent_node.right_child = node_to_delete.left_child
        node_to_delete.left_child.parent = parent_node

• 경우3 : 삭제하려는 데이터의 노드가 두 개의 자식이 있을 때

이렇게 생긴 이진탐색트리에서 12를 삭제하려면 어떻게 해야 할까?
정답은 14를 12의 위치로 옮기면 된다.
그 이유를 생각해보자.
우선 12의 왼쪽자식인 10과 11은 오른쪽 노드에서 가장 작은 데이터보다 더 작을 수 밖에 없다.
따라서 14을 12의 위치로 옮겨도 이진탐색트리의 속성이 유지되는 것이다.
이렇게 어떤 노드보다 큰 노드 중 가장 작은 노드를 successor라고 부른다. 이 상황에서는 12보다 큰 데이터 중 가장 작은 데이터가 14이기 때문에, 14는 12의 successor이라고 할 수 있다.

그럼 아래처럼 옮기는 방법을 생각해보자.

14는 successor이기 때문에 리프노드일 것이다. 또는 14보다 큰 수인 오른쪽 자식을 가질 수도 있다. successor의 왼쪽자식은 당연히 없다.

이걸 코드로 구현해보는 실습을 해보자.

• 두 개의 자식이 모두 있는 노드를 삭제하는 경우
  1. 지우려는 successor를 받아온다. (find_min()메소드 활용)
  2. 삭제하려는 노드 데이터에 successor의 데이터를 저장한 다.
  3. successor 노드를 삭제한다.
  • 이때 successor노드가 부모노드의 오른쪽 자식인지, 왼쪽 자식인지,
  • successor 노드가 오른쪽 자식을 가지는지 아닌지를 고려해야 한다.
  • delete() 메소드는 지우려는 데이터 data를 파라미터로 받는다. 그리고 data를 갖는 노드를 트리에서 삭제한다.

아래 코드를 delete 메서드에 추가해주자.

# 경우 3: 지우려는 노드가 2개의 자식이 있을 때

else:
  successor = self.find_min(node_to_delete.right_child)

  node_to_delete.data = successor.data

  # successor 노드가 어떤 부모 노드의 왼쪽 자식일 때
  if successor == successor.parent.left_child:
    successor.parent.left_child = successor.right_child
  else: # sucessor 노드가 삭제하려는 노드의 바로 오른쪽 자식일 때
    successor.parent.right_child = successor.right_child

  if successor.right_child is not None: # successor 노드가 오른쪽 자식이 있을 떄
    successor.right_child.parent = successor.parent

삭제연산의 시간복잡도

삭제하는 경우 3가지 경우를 봐야 한다. 공통적으로 삭제하기 위해 먼저 지우려는 노드를 탐색해야 하는데, 위에서 언급했듯이 탐색 연산은 $O(h)$ 의 시간 복잡도가 걸린다.

• 경우1 : 지우려는 데이터가 leaf 노드일때
  • 지우려는 데이터의 부모에서 자식 레퍼런스를 None으로만 지정해주면 된다. 따라서 O(1)이 걸리고, 탐색하는 것까지 고려해서 $O(h)$가 걸린다.
• 경우2 : 지우려는 데이터가 노드 하나의 자식이 있을 때
  • 삭제하려는 노드의 부모의 자식을 삭제하려는 노드의 자식으로 만들어주면 된다. 이것도 레퍼런스 연결만 해주면 되니, $O(1)$가 걸리고, 즉, $O(h)$가 걸린다.
• 경우3 : 지우려는 데이터 노드가 두 개의 자식이 있을 때
  • 이 경우, 여러 단계를 거치므로 하나하나 살펴보자.
  1. 먼저 지우려는 데이터 노드의 successor 노드를 찾는다
     -> find_min 메소드는 $O(h)$이 걸린다.
  2. 지우려는 노드에 successor 노드의 데이터를 저장한 후
     -> $O(h)$가 걸린다.
  3. successor 노드를 지운다.
     -> $O(1)$가 걸린다.
  • 합쳐서보면 $O(h+h+1)$이 걸리고, 탐색하는 것까지 고려하여 $O(h+h+h+1) = O(h)$가 걸린다.
• 이진 탐색 트리의 기본 연산들은 트리가 편향돼 있을수록 비효율적이고, 균형이 잡혀 있을수록 효율적이다.