이진 탐색 트리

seushin·2022년 7월 20일
0

트리 모양의 연결리스트를 이분탐색으로 사용할 수 있게 만든 자료구조. 각 노드는 비교 가능한 값을 가지고, 노드의 왼쪽엔 노드보다 작은 값들, 노드 오른쪽엔 노드보다 큰 값들로 이루어져 있다.

이진 탐색 트리도 이분 탐색의 특성을 제외한다면 이진 트리와 구성요소는 동일하다. 키, 데이터와 left/right 두 자식 노드 그리고 parent 노드를 가진다.

만약 자식이나 부모가 없다면 그 자리의 노드는 NIL 노드라 하자. 트리는 하나의 루트를 가지는데 루트는 부모 노드가 NIL인 노드다. 반대로 자식이 모두 NIL 노드라면 그 노드는 leaf 노드라고 부른다.

트리의 순회

이진 탐색 트리는 중위 트리 순회를 이용해 노드들을 정렬된 순서대로 순회할 수 있다. 중위 트리 순회는 루트를 기준으로 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 순회하는데 이는 서브트리에서도 재귀적으로 반복된다.
이진 탐색 트리에서의 특징인 노드의 왼쪽엔 항상 작은 값이, 오른쪽엔 항상 큰 값이 있기 때문에 중위 순회를 한다면 항상 정렬된 순서로 순회함을 보장할 수 있다.

inorder_tree_walk(node x)
{
  if (x != NIL)
  {
    inorder_tree_walk(x.left)
    f(x)
    inorder_tree_walk(x.right)
  }
}

검색

트리의 루트와 키 k가 주어졌을 때 키 k를 가지는 노드를 반환한다. 만약 찾는 노드가 없다면 NIL을 반환한다.
루트에서부터 재귀적으로 트리의 아래로 내려가기 때문에 트리의 높이 h에 대해 O(h)의 수행시간을 가진다.

search(node x, key k)
{
  if (x == NIL || k == x.key)
  	return x
  if (k < x.key
  	return search(x.left, k)
  else
  	return search(x.right, k)
}

직후 원소

노드 x가 주어졌을 때 중위 트리 순회로 정렬되는 순서 안에서 그 노드의 직후 노드를 찾는다.
모든 키가 서로 다르다면 노드 x의 직후 노드는 x의 값보다 큰 값 중 가장 작은 값을 가지는 노드가 된다. 이진 탐색 트리의 특성을 이용하면 값의 비교 없이 직후 노드를 찾을 수 있다.
아래에 나와있듯 두 가지 상황으로 나눌 수 있다.

  1. 노드가 오른쪽 서브트리를 가지고 있을 경우
  2. 노드의 오른쪽 서브트리가 없을 경우

오른쪽 서브트리를 가진다면 노드 x보다 큰 값 중 가장 작은 값을 찾는다면 오른쪽 서브트리에서 최소값을 찾으면 된다.
만약 오른쪽 자식이 없다면 트리의 부모 방향으로 올라가면서 노드 x보다 큰 값을 찾아야 한다. 다르게 말하면 현재 노드가 부모 노드의 왼쪽 노드가 될 때까지 트리를 따라 올라간다.

successor(node x)
{
  if (x.right != NIL)
    return minimum(x.right)
  parent_node = x.parent
  current_node = x
  while (parent != NIL && current_node == parent.right)
  {
    current_node = parent_node // 위로 올라간다.
    parent_node = parent_node.parent
  }
  return parent_node
}

최소 원소는 아래와 같이 트리의 가장 왼쪽 노드를 찾으면 된다.

minimum(node x)
{
  if (x == NIL)
    return NIL
  while (x.left != NIL)
    x = x.left
  return x
}

원소 삽입

트리의 루트와 새로운 노드를 받아, 루트에서 시작해 새로운 노드와 기존 노드를 비교하며 NIL 노드를 만날 때까지 아래로 내려간다.
아래 코드에서 current_node가 NIL일 때 current_node의 위치가 새로운 노드가 놓일 자리가 된다. 다만 트리에 새로운 노드를 연결하기 위해서는 부모 노드를 수정해야 하는데 NIL 노드를 찾았을 때에는 이미 부모 노드를 지나왔기 때문에 부모 노드 포인터를 따로 저장해둬야 한다.
삽입도 다른 연산들과 마찬가지로 높이 h만큼 아래로 내려가므로 O(h)의 수행시간을 가진다.

insert(tree T, node new_node)
{
  parent_node = NIL
  current_node = T.root
  
  while (current_node != NIL)
  {
    parent_node = current_node
    if (new_node.key < current_node.key)
      current_node = current_node.left
    else
      current_node = current_node.right
  }
  new_node.parent = parent_node;
  
  if (parent_node == NIL) // 빈 트리일 때, 새로운 노드가 루트가 된다.
    T.root = new_node
  else if (new_node.key < parent_node.key)
    parent_node.left = new_node
  else
    parent_node.right = new_node
}

원소 삭제

이진 탐색 트리 T에서 노드 x를 삭제할 때 세 가지 시나리오를 떠올려 볼 수 있다.

  1. 노드 x가 자식 노드를 가지고 있지 않으면 x의 부모 노드에서 자식 x를 NIL 노드로 대체하여 삭제한다.
  2. 노드 x가 자식 노드를 하나만 가지고 있다면 그 자식노드를 x의 자리로 상승시키고 삭제한다.
  3. 자식 노드를 두 개 가지고 있다면 x의 직후 원소 y를 찾고 y를 x의 자리를 대체하도록 한다.

세 번째 시나리오 안에서 중요한 포인트는 직후 원소 y는 항상 왼쪽 자식이 NIL 노드라는 것. 세 번째 시나리오에서는 x의 오른쪽 자식이 존재한다고 가정하기 때문에(양쪽 자식 모두 가지고 있으니), 직후 원소 y는 항상 x의 오른쪽 서브트리에서 가장 작은 값(가장 왼쪽 값)이 되기 때문이다.

이제 다시 세 번째 시나리오를 두 가지 상황으로 나눠 볼 수 있는데

  1. 직후 원소 y가 x의 오른쪽 자식이라면, y는 x의 왼쪽 자식을 이어받으며 x의 자리를 그대로 대체한다.
  2. 그렇지 않다면 y는 x의 오른쪽 서브 트리에 있지만 x의 오른쪽 자식은 아니다. 이 경우 y의 자리를 y의 오른쪽 자식으로 먼저 대체하고, 그 다음 x의 자리에 y를 대체한다.
delete(tree T, node x)
{
  if (x.left == NIL) // 1, 2번 시나리오
    transplant(T, x, x.right)
  else if (x.right == NIL) // 2번 시나리오
    transplant(T, x, x.left)
  else // 3번 시나리오
  {
    y = minimum(x.right)
    if (y.parent != x) // 3-2
    {
      transplant(T, y, y.right)
      y.right = x.right
      y.right.parent = y
    }
    transplant(T, x, y)
    y.left = x.left
    y.left.parent = y
  }
}

노드 u가 루트인 서브 트리를 노드 v가 루트인 서브 트리로 교체하는 transplant는 아래와 같다.

transplant(tree T, node u, node v)
{
  // u의 부모 노드에서 연결된 u를 v로 바꾸기
  if (u.parent == NIL)
    T.root = v
  else if (u == u.parent.left)
    u.parent.left = v
  else
    u.parent.right = v
  // v의 입장에서도 부모를 연결해준다
  if (v != NIL)
    v.parent = u.parent
}

transplant는 상수 시간 안에 수행되므로, 삭제 연산은 minimum 연산의 수행시간인 O(h) 시간이 소요된다.

여기까지 이진 탐색 트리의 삽입, 검색, 삭제 연산들이 O(h) 안에 수행될 수 있다는 것을 확인하였다.
최악의 경우에는 트리의 높이가 노드의 갯수와 같아져(O(n)) 연산의 속도는 연결 리스트와 비슷해져 버린다. 어느 정도의 높이를 보장하기 위해서는 트리에서 노드들을 균형을 이루도록 만들 필요가 있다. 이러한 균형 잡힌 이진 트리는 대표적으로 AVL 트리, 레드-블랙 트리가 있다.

Ref

  • Introduction to Algorithms(한빛아카데미)
profile
seushin

0개의 댓글