읽고 나면 진짜 쉬워지는 자료 구조 - 5. 이진 탐색 트리

이진 탐색 알고리즘의 개념을 기반으로 동적 자료 구조를 생성하는 BST

🔖 5.1 이진 탐색 트리 구조

트리에 대한 책 설명

  • 트리는 노드의 분기 사슬로 구성된 계층적 자료 구조다.

  • 트리 구조는 연결 리스트를 자연스럽게 확장한 것인데, 트리 노드는 서로소인 하부 리스트를 가리키는 2가지 next 노드를 허용한다는 점에서 연결 리스트와 차이가 있다.

쉽게 말해 트리란?

  • 트리는 데이터를 계층적으로 저장하는 자료 구조다. 즉, 여러 갈래로 뻗어나가는 가지가 있는 구조로 생각하면 된다.

연결 리스트와의 차이점

  • 연결 리스트는 노드가 다음 하나의 노드만 가리킨다면, 트리는 각 노드가 여러 개의 자식 노드를 가리킬 수 있다.

  • 가장 흔한 트리 형태인 이진 트리에서는 각 노드가 최대 2개의 자식 노드를 가리킬 수 있다.

  • 비유하자면 연결 리스트는 일렬로 이어진 기차 칸처럼 데이터가 한 방향으로만 연결돼 있다면, 트리는 뿌리에서 가지로 나뉘는 나무와 비슷하다.

노드

  • 필요에 따라 다른 정보를 포함할 수 있다. 예를 들어, 노드에 부모를 가리키는 포인터를 저장할 수 있다.

  • 포인터를 저장하면 트리 탐색 뿐만 아니라 노드 제거 시에도 유용하다.

  • 노드 값은 마치 호텔 객실을 찾아갈 때 500-519호실이 왼쪽에 있고, 520-590호실이 오른쪽에 있음을 알려주는 표지판과 같다. (좋은 비유!)

  • 즉, 단 한 번의 간단한 확인만으로 적절한 방향을 택하고 다른 방향에 있는 방을 무시할 수 있다.

🔖 5.2 이진 탐색 트리에서 탐색하기

반복적 탐색

재귀 호출 대신 while 루프를 사용하며 트리를 반복해서 내려간다.

function createNode(value) {
  return {
    value,
    left: null,
    right: null,
  };
}

function insertNode(root, value) {
  if (!root) return createNode(value);

  let current = root;
  while (true) {
    if (value < current.value) {
      if (!current.left) {
        current.left = createNode(value);
        break;
      }
      current = current.left;
    } else {
      if (!current.right) {
        current.right = createNode(value);
        break;
      }
      current = current.right;
    }
  }

  return root;
}

function iterativeSearch(root, value) {
  let current = root;
  while (current) {
    if (value === current.value) return true; // 값이 존재
    current = value < current.value ? current.left : current.right;
  }
  return false; // 값이 없음
}

재귀적 탐색

탐색 함수는 처음에 트리의 루트 노드로 호출되고 다음 노드를 사용해 자기 자신을 호출한다.

function insertNodeRecursive(root, value) {
  if (!root) return createNode(value);

  if (value < root.value) {
    root.left = insertNodeRecursive(root.left, value);
  } else {
    root.right = insertNodeRecursive(root.right, value);
  }

  return root;
}

function recursiveSearch(root, value) {
  if (!root) return false; // 값이 없음
  if (value === root.value) return true; // 값이 존재

  return value < root.value
    ? recursiveSearch(root.left, value)
    : recursiveSearch(root.right, value);
}

비교 정리

방법

반복적 탐색 (Iterative)

재귀적 탐색 (Recursive)

코드 복잡도

비교적 단순하며 명확한 흐름

함수 호출로 직관적이나 깊은 트리에선 스택 오버플로우 위험

성능

스택을 사용하지 않으므로 메모리 효율적

재귀 호출로 인해 메모리 추가 사용

사용 상황

트리 깊이가 깊은 경우 적합

코드 가독성과 간결함이 중요한 경우 적합

🔖 5.3 이진 탐색 트리 변경하기

로직 단순화

  • 이진 탐색 트리를 사용하는 로직을 단순화하기 위해 루트 노드를 포함하는 얇은 자료 구조로 트리 전체를 감쌀 수 있다.

  • 이러한 wrapper 함수가 낭비처럼 보일 수 있지만 트리의 사용을 더 쉽게 해주고, 루트 노드의 처리를 크게 단순화해준다.

노드 삽입

  • 이진 탐색 트리에 값을 삽입하는 것은 탐색과 같은 알고리즘을 사용한다.

  • 중복을 허용하는 경우에는 막다른 골목에 도달할 때까지 계속 진행한 다음에 새 값을 트리에 삽입한다.

  • 중복을 허용하지 않는 경우에는 새 값과 일치하는 노드에 저장된 데이터를 대체하거나 추가 정보를 저장할 수 있다.

  • 새 노드를 트리에 삽입하는 비용은 새 노드를 삽입하는 경로의 깊이에 비례한다.

  • 최악의 경우 삽입 비횽은 트리의 깊이에 선형적으로 비례해 증가한다.

노드 제거

  • 삽입보다 복잡한 과정이다. 자식 수가 늘어날수록 작업이 복잡해진다.

  • 리프 노드 제거 시에는 해당 노드를 제거하고 부모의 자식 포인터를 null로 갱신해 해당 노드가 더이상 존재하지 않음을 표시해야 한다.

  • 자식을 하나만 가지는 내부 노드는 자식 노드를 승격시켜 포인터를 변경하고, 해당 자식을 한 단계 승격시켜 제거한다.

  • 승격될 노드가 이미 부모의 하위 트리에 속해있었기 때문에 해당 노드의 모든 하위 항목은 이진 탐색 트리 속성을 계속 유지한다.

  • 반드시 제거할 노드를 제외한 나머지 트리의 무결성을 유지하고 계속 이진 탐색 트리 속성을 따르게 보장해야 한다.

  • 두 자식을 가진 내부 노드를 제거하려면 먼저 후속자 노드를 해당 위치로 교환한다.

🔖 5.4 균형이 맞지 않는 트리

완전 균형

  • 트리 깊이가 노드 수를 두 배로 늘릴 때마다 1씩 증가한다.

  • 최악의 경우 성능은 O(log2N)에 비례해 증가한다.

균형이 맞지 않는 경우

  • 원소 수에 비례해 트리 깊이가 선형적으로 증가할 수 있다. O(N)

  • 물론 동적 삽입과 제거 발생 시 균형을 유지하기 위해 red-black 트리 등의 방법이 있지만, 균형을 유지하는 대신 트리 연산의 복잡도를 증가시킨다는 trade-off가 있다.

🔖 5.5 이진 탐색 트리 대량 구축

균형 이진 탐색 트리 생성

  • 노드를 반복해 추가함으로써 쉽게 이진 탐색 트리를 구성할 수 있다. 다만, 균형이 맞지 않는 트리가 생길 수 있다.

  • 따라서 정렬된 배열로부터 원소를 재귀적으로 더 작은 부분 집합으로 나누어 균형 이진 탐색 트리를 생성한다.

Last updated