[자료구조💾] 12장 탐색 트리

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스)

 

12.1 이진 탐색 트리 (binary search tree)

1) 이진 탐색 트리

- 이진 탐색 알고리즘을 적용하여 원소들을 저장한 이진 트리

- 다음의 조건을 만족해야 한다.

• 트리 내의 모든 원소는 유일해야 한다.
• 루트는 자신의왼쪽 서브트리에존재하는 모든 노드보다 크고, 오른쪽 서브 트리의 모든 노드보다 작다.
• 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.

- 평균 탐색 시간(h = 트리의 높이) : O(h)

 

2) 이진 탐색 트리의 노드 탐색

- 탐색 키와 중간 값을 비교한 후 결과에 따라 탐색 성공, 왼쪽 서브 트리 탐색, 오른쪽 서브트리 탐색 중 하나이다.

- 재귀적 이진 탐색 트리

def rbst(root, item):
  if not root:
    return None
  if item == root.data:
    return root
  if item < root.data:
    return rbst(root.left, item)
  return rbst(root.right, item)

- 반복문 이진 탐색 트리

def ibst(root, item):
  node = root
  while node:
    if item == node.data:
      return node
    if item < node.data:
      node = node.left
    else:
      node = node.right
  return None

 

3) 이진 탐색 트리에 노드 추가

- 알고리즘

1. 이진 탐색 트리에서 추가할 노드(node)를 탐색한다.
2. 동일한 노드가 이미존재하면 중복 오류를 보고하고 알고리즘을 종료한다.
3. 중복이 아니면 가장 마지막에 탐색한 노드(temp)와 크기를 비교한다.
4. node가 temp보다 크면 오른쪽 자식으로 추가하고, 그렇지 않으면 왼쪽 자식 노드로 추가한다.

- 코드

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

class BST:
  def __init__(self):
    self.tree = []
    self.temp = None
    self.prev = None
    self.direction = None
  
  def insert(self, item):
    node = Node(item)
    if not self.tree:
      self.tree = node
    else:
      temp = self.tree
      prev = None
      while True:
        prev = temp
        if item < prev.data:
          temp = temp.left
          if not temp:
            prev.left = node
            return
        elif item > prev.data:
          temp = temp.right
          if not temp:
            prev.righ = node
            return
        else:
          return

 

4) 이진 탐색 트리에 노드 삭제

- 삭제할 노드가 단말 노드 : 삭제 노드의 부모 노드의 링크를 None으로 변경한다.

- 삭제할 노드가 자식이 한 개인 노드 : 삭제 노드의 부모 노드의 링크에 삭제 노드의 자식 노드를 연결한다.

- 삭제할 노드가 자식이 두 개인 노드

• 삭제 노드의 왼쪽 서브 트리에서 최댓값 또는 오른쪽 서브 트리의 최솟값 노드로 삭제 노드를 대신한다.
• 대체 노드의 이동은 또 다른 삭제연산으로, 재귀적인 삭제 과정을 수행한다.

- 코드

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

class BST:
  def __init__(self):
    self.tree = []
    self.temp = None
    self.prev = None
    self.direction = None
        
  def find_delete(self, item):
    self.tree = self.delete(self.tree, item)

  def find_max(self, root):
    if not root:
      return None
    node = root
    while node.right:
      node = node.right
    return node
        
  def delete(self, node, item):
    if node is None:
      return None
    if node.data > item:
      node.left = self.delete(node.left, item)
      return node
    elif node.data < item:
      node.right = self.delete(node.right, item)
      return node
    else:
      if node.left is None:
        return node.right
      elif node.right is None:
        return node.left
      elif node.left is None and node.right is None:
        return None
      else:
        left_max = self.find_max(node.left)
        node.data = left_max.data
        node.left = self.delete(node.left, left_max.data)
        return node

 

 

12.2 균형 이진 탐색 트리 (balanced binary search tree)

1) 균형 이진 탐색 트리

- 이진 탐색 트리의 성능

• 트리의 형태에 따라 달라짐.
• 최악의 경우(편중 트리) 시간 복잡도 : O(n)
• 이진 탐색 트리에서 탐색 성능을 유지하기 위해 트리의높이를 최대한 낮게 유지하는 것이 좋다.

-  균형 이진 탐색 트리

• 노드가 추가되거나 삭제되어도 높이를 O(log₂n)로 유지해야 하는 트리
• 예시 : AVL 트리, 2-3-4 트리, Red-Black 트리

 

2) AVL 트리

-  Adelson-Velskii와 Landis가 1962년에 발표한 균형 이진 탐색 트리

- 탐색 시간 : O(log₂n) 

- 모든 노드에서 좌우 서브 트리의 높이 차가 1이어야 한다.

- 균형 인수(balance factor : BF)

• 노드와 좌우 트리의높이 차이
• AVL 트리의 모든 노드의 균형 인수는 -1,0, 1 중 하나이다.
• BF[i] = height(LS[i]) - height(RS[i])

- AVL 트리의 최소 노드 수 : N_h = N_h-1 + N_h-2 + 1

 

3) AVL 트리에 노드 추가

(1) 단일 회전 재구성

(2) 이중 회전 재구성

 

 

12.3 B-트리

1) B-트리

- 주 메모리의 크기보다 큰 대용량의 데이터를 하드디스크에 저장할 때는 효율적인 저장방법이 필요하다.

- 탐색 속도를 높이기 위해 이진 트리를 포기하고 자식 노드를 더 많이 할당하여 트리의 높이를 줄인다.

- m-원 B-트리(m-way B-tree) : 차수가 2보다 큰 트리

 

2) m-원 B-트리

- 공백 트리이거나 아래 조건을 만족하는 m-원 탐색 트리이다.

• 루트는 최소 2개 이상의 자식 노드를 갖거나, 단말 노드이다.
• 루트가 아닌 모든 내부 노드는 ceil(m/2) ~ m개의 자식을 갖는다.
• 단말 노드는 같은 레벨에 존재한다.
• 내부 노드에 저장되는 키의 수는 자식의 수보다 1개 적다.
• 단말 노드에 저장되는 키의 수는 ceil(m/2)-1 ~ m-1 개이다.
• m = 3인 트리를 2-3 트리, m = 4인 트리는 2-3-4트리라고 한다.
• 높이가 h인 m-원 B-트리에 저장할 수 있는 총 키의 개수 : m^h+1-1

- 노드 추가

- 노드 삭제