이진 탐색 트리(BST)

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software engineer

정의

노드의 왼쪽 서브트리:
- 노드보다 작은 값
노드의 오른쪽 서브트리:
- 노드보다 큰 값
왼쪽·오른쪽 서브트리도 이진 탐색 트리여야 함

이진 탐색 트리의 도식적 표현.

구현

class TreeNode:  
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

class BinarySearchTree:
  def __init__(self):
    self.root = None

탐색

72 탐색

이진 탐색 트리의 도식적 표현.

탐색

72 탐색

루트 노드가 노란색으로 표시된 이진 탐색 트리의 도식적 표현.

탐색

72 탐색

루트 노드와 루트 노드의 왼쪽 서브트리가 회색으로 표시된 이진 탐색 트리. 오른쪽 서브트리의 첫 번째 노드는 노란색으로 표시됨.

탐색

72 탐색

이진 탐색 트리. 마지막 루트 노드의 왼쪽 서브트리와 마지막 루트 노드가 회색으로 표시됨. 새 루트 노드는 노란색으로 표시됨.

탐색

72 탐색

새 루트 노드는 노란색, 나머지 노드는 회색으로 표시된 이진 탐색 트리.

탐색

72 탐색

새 루트 노드는 노란색, 나머지 노드는 회색으로 표시된 이진 탐색 트리. 노란색 노드에는 숫자 72가 표시되어 강조됨.

탐색

def search(self, search_value):

    current_node = self.root

    while current_node:

      if search_value == current_node.data:

        return True

      elif search_value < current_node.data:

        current_node = current_node.left_child

      else:

        current_node = current_node.right_child

    return False

삽입

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

새 노드의 그래픽 표현.

삽입

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return

루트 노드가 된 새 노드의 그래픽 표현.

삽입

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:

새 노드와 오른쪽 자식이 있는 루트 노드의 그래픽 표현.

삽입

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root

    while True:

      if data < current_node.data:

        if current_node.left_child == None:

새 노드와 오른쪽 자식이 있는 루트 노드의 그래픽 표현. 루트 노드가 current_node임.

삽입

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return

오른쪽 자식과 왼쪽 자식이 있는 루트 노드의 그래픽 표현. 루트 노드가 current_node이고 새 노드는 왼쪽 자식임.

삽입

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:

새 노드와 일부 요소가 있는 이진 탐색 트리의 그래픽 표현. 루트 노드가 current_node임.

삽입

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child

새 노드와 일부 요소가 있는 이진 탐색 트리의 그래픽 표현. current_node는 루트의 왼쪽 자식임.

삽입

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:

        if current_node.right_child == None:

새 노드와 왼쪽 서브트리가 있는 이진 탐색 트리의 그래픽 표현.

삽입

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return

왼쪽 서브트리가 있는 이진 탐색 트리의 그래픽 표현. 새 노드는 루트의 오른쪽 자식이 됨.

삽입

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:

새 노드와 일부 요소가 있는 이진 탐색 트리의 그래픽 표현.

삽입

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

새 노드와 일부 요소가 있는 이진 탐색 트리의 그래픽 표현. current_node는 루트의 오른쪽 자식임.

삽입

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return 
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

새 노드와 일부 요소가 있는 이진 탐색 트리의 그래픽 표현. current_node는 루트의 오른쪽 자식이고 새 노드는 current_node의 왼쪽 자식임.

삭제

자식 없음

일부 요소가 있는 이진 탐색 트리의 그래픽 표현. 삭제될 노드가 빨간색으로 표시됨. 이 노드는 자식이 없음.

삭제

자식 없음
- 노드 삭제

일부 요소가 있는 이진 탐색 트리의 그래픽 표현. 삭제 대상 노드가 트리에서 제거됨.

삭제

자식 하나

일부 요소가 있는 이진 탐색 트리의 그래픽 표현. 삭제될 노드가 빨간색으로 표시됨. 이 노드는 오른쪽 자식이 있음.

삭제

자식 하나
- 노드 삭제
- 자식을 부모 노드와 연결

일부 요소가 있는 이진 탐색 트리의 그래픽 표현. 삭제 대상 노드가 제거되고 루트 노드가 삭제된 노드의 오른쪽 자식을 가리킴.

삭제

자식 하나
- 노드 삭제
- 자식을 부모 노드와 연결

이진 탐색 트리의 그래픽 표현.

삭제

자식 둘

루트 노드가 삭제 대상으로 빨간색으로 표시된 이진 탐색 트리의 그래픽 표현.

삭제

자식 둘
- 후계자 노드로 대체
  - 해당 노드보다 큰 값 중 가장 작은 노드
- 후계자 찾기:

루트 노드가 삭제 대상으로 빨간색으로 표시된 이진 탐색 트리의 그래픽 표현.

삭제

자식 둘
- 후계자 노드로 대체
  - 해당 노드보다 큰 값 중 가장 작은 노드
- 후계자 찾기:
  - 오른쪽 자식 방문

루트 노드가 삭제 대상으로 빨간색, 루트의 오른쪽 자식이 노란색으로 표시된 이진 탐색 트리의 그래픽 표현.

삭제

자식 둘
- 후계자 노드로 대체
  - 해당 노드보다 큰 값 중 가장 작은 노드
- 후계자 찾기:
  - 오른쪽 자식 방문
  - 끝까지 왼쪽 노드를 계속 방문

루트 노드가 삭제 대상으로 빨간색, 후계자를 찾기 위해 다른 노드가 노란색으로 표시된 이진 탐색 트리의 그래픽 표현.

삭제

자식 둘
- 후계자 노드로 대체
  - 해당 노드보다 큰 값 중 가장 작은 노드
- 후계자 찾기:
  - 오른쪽 자식 방문
  - 끝까지 왼쪽 노드를 계속 방문

루트 노드가 삭제 대상으로 빨간색, 후계자를 찾기 위해 다른 노드가 노란색으로 표시된 이진 탐색 트리의 그래픽 표현.

삭제

자식 둘
- 후계자 노드로 대체
  - 해당 노드보다 큰 값 중 가장 작은 노드
- 후계자 찾기:
  - 오른쪽 자식 방문
  - 끝까지 왼쪽 노드를 계속 방문

루트 노드가 삭제 대상으로 빨간색, 후계자를 찾기 위해 다른 노드가 노란색으로 표시된 이진 탐색 트리의 그래픽 표현. 후계자는 숫자 13으로 확인됨.

삭제

자식 둘
- 후계자 노드로 대체
  - 해당 노드보다 큰 값 중 가장 작은 노드
- 후계자 찾기:
  - 오른쪽 자식 방문
  - 끝까지 왼쪽 노드를 계속 방문

루트 노드가 후계자로 대체된 이진 탐색 트리의 그래픽 표현.

삭제

자식 둘
- 후계자 노드로 대체
  - 해당 노드보다 큰 값 중 가장 작은 노드
- 후계자 찾기:
  - 오른쪽 자식 방문
  - 끝까지 왼쪽 노드를 계속 방문
  - 후계자에게 오른쪽 자식이 있는 경우:

후계자 노드에 오른쪽 자식이 있는 이진 탐색 트리의 그래픽 표현.

삭제

자식 둘
- 후계자 노드로 대체
  - 해당 노드보다 큰 값 중 가장 작은 노드
- 후계자 찾기:
  - 오른쪽 자식 방문
  - 끝까지 왼쪽 노드를 계속 방문
  - 후계자에게 오른쪽 자식이 있는 경우:
    - 해당 자식이 후계자 부모의 왼쪽 자식이 됨.

후계자 노드에 오른쪽 자식이 있었던 이진 탐색 트리의 그래픽 표현. 후계자의 자식이 후계자 부모의 왼쪽 자식이 되고 루트 노드가 후계자로 대체됨.

활용

목록을 효율적으로 정렬
배열·연결 리스트보다 훨씬 빠른 탐색
배열보다 훨씬 빠른 삽입·삭제
고급 자료구조 구현에 활용:
- 동적 집합
- 조회 테이블
- 우선순위 큐

연습해 봅시다!

Python으로 배우는 자료구조와 알고리즘