15장 이진 탐색 트리로 속도 향상

김현수·2022년 2월 25일

누구나 자료 구조와 알고리즘 알고리즘

누구나 자료 구조와 알고리즘

목록 보기

15/20

정렬 알고리즘은 아무리 빨라도 O(N logN)이다. 데이터를 자주 정렬해야 하면 데이터를 항상 정렬된 순서로 유지하는 편이 합리적이다.

정렬된 배열은 읽기에 O(1), (이진) 검색에 O(logN)이 걸린다. 하지만 삽입과 삭제가 상대적으로 느리다. 평균 시나리오에서 N/2 단계, 즉 O(N)이 걸린다.

해시 테이블은 연산이 빠르지만 순서를 유지하지 못하므로 알파벳순으로 목록을 정렬하는 애플리케이션에는 적절치 않다.

15.1 트리

트리는 노드 기반 자료 구조이다. 하지만 연결 리스트와는 달리 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다.

가장 상위 노드를 "루트 root"라 부른다. 트리의 꼭대기에 해당한다.
트리에는 부모와 자식이 존재하며, 자손과 조상이 있을 수 있다.
- 한 노드의 자손은 그 노드에서 생겨난 모든 노드이며, 한 노드의 조상은 그 노드를 생겨나게 한 모든 노드다.
트리에는 레벨이 있다. 각 레벨은 트리에서 같은 줄이다.
트리의 프로퍼티 property는 균형잡힌 정도를 말한다.
- 모든 노드에서 하위 트리의 노드 개수가 같으면 그 트리는 균형(balanced) 트리다. 그렇지 않다면 불균형(imbalanced) 트리라고 한다.

15.2 이진 탐색 트리

이진 트리는 각 노드에 자식이 0개, 1개 혹은 2개 이다.
이진 탐색 트리는 다음의 규칙이 추가된 트리다.

각 노드의 자식은 최대 왼쪽에 하나, 오른쪽에 하나다.
한 노드의 왼쪽 자손은 그 노드보다 작은 값만 포함할 수 있다. 오른쪽 자손은 그 노드보다 큰 값만 포함할 수 있다.

class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.leftChild = left;
    this.rightChild = right;
  }
}

const node1 = new TreeNode(25);
const node2 = new TreeNode(75);
const root = new TreeNode(50, node1, node2);

15.3 검색

이진 탐색 트리를 검색하는 알고리즘은 다음과 같다:

노드를 "현재 노드"로 지정한다. (처음에는 루트 노드가 첫 번째 "현재 노드"다.)
현재 노드의 값을 확인한다.
찾고 있는 값이면 검색을 종료한다.
찾고 있는 값이 현재 노드보다 작으면 왼쪽 하위 트리를 검색한다.
찾고 있는 값이 현재 노드보다 크면 오른쪽 하위 트리를 검색한다.
찾고 있는 값을 찾았거나, 트리 바닥에 닿을 때(즉, 트리 내에 찾고 있는 값이 없을 때)까지 1-5단계를 반복한다.

15.3.1 이진 탐색 트리 검색의 효율성

이진 탐색 트리 검색은 각 단계마다 검색할 대상이 남은 노드의 반으로 줄어든다. 처음 시작할 땐 루트의 자손 중 하나일 것이나, 오른쪽 자식을 선택하는 순간 왼쪽 자식과 왼쪽 자식의 자손은 모두 검색에서 제외된다. 따라서 O(logN)이다. 물론 최선의 시나리오인 포화 균형 이진 탐색 트리에서만 그렇다.

15.3.2 log(N) 레벨

균형 이진 트리에 노드가 N개면 레벨(줄)이 약 logN개다. 노드가 N개인 트리에서 모든 자리마다 노드를 두려면 log(N) 레벨이 필요하다. 즉, 레벨을 새로 추가할 때마다 트리 크기가 두 배가 된다.

이진 탐색 트리 검색은 O(logN)인데 이는 정렬된 배열의 이진 검색과 효율성이 같다.

15.3.3 코드 구현: 이진 탐색 트리 검색

search(searchValue, node) {
  // 기저 조건: 노드가 없거나, 찾고 있던 값이면
  if (node === null || node.value === searchValue) return node;

  if (searchValue < node.value) {
    return this.search(searchValue,node.leftChild);
  } else {
    return this.search(searchValue, node.rightChild);
  }
}

이진 탐색 트리 연산을 구현할 때 재귀를 많이 활용된다. 10장에서 배웠듯이, 재귀는 임의의 깊이만큼 들어가야 하는 자료 구조를 다룰 때 꼭 필요하다. 레벨이 무한한 트리가 그러하다.

search 함수는 찾는 값인 searchValue와 검색 기반으로 사용할 node를 입력으로 받는다. 처음 호출할 땐 node가 루트 노드이다. 재귀 호출에선 node가 트리 내 다른 노드일 수 있다.

함수에서 다루는 네 가지 조건 중 두 가지는 기저 조건이다. 노드에 찾고 있는 값이 들어있는 경우 해당 노드를 반환하고 더 이상 재귀를 호출하지 않는다.

자식 노드에 search를 호출했는데 null을 반환할 경우(실제로 기본값이 null이기 때문에 null을 반환한다.)는 searchValue가 트리에 존재하지 않을 때 발생한다. 이때의 node는 null이므로, node를 반환하는 것은 결국 null을 반환하는 것인데, 이는 searchValue가 트리 안에 없다는 뜻이므로 적절하다.

searchValue가 현재 노드 값보다 작으면 searchValue는 현재 노드보다 왼쪽에 있을 것이므로 왼쪽 자식에 대해 재귀적으로 호출하고, 크면 오른쪽에 있을 것이므로 오른쪽 자식에 대해 재귀적으로 호출한다.

15.4 삽입

이진 탐색 트리는 삽입에 가장 뛰어나다.
올바른 노드를 루트로부터 검색해 삽입한다.

삽입은 항상 검색에 한 단계 더 추가 된다. 즉, (logN) + 1단계가 걸리므로 O(logN)이다.

정렬된 배열은 검색에 O(logN), 삽입에 O(N)이다. 반면 이진 탐색 트리는 검색과 삽입 모두 O(logN)이 걸리므로 효율적이다. 데이터를 많이 변경할 애플리케이션이라면 특히 중요하다.

15.4.1 코드 구현: 이진 탐색 트리 삽입

insert(value, node) {
  if (value < node.value) {
    if (node.leftChild === null) {
      // 왼쪽 자식이 없으면 왼쪽 자식으로 값을 삽입한다.
      node.leftChild = new TreeNode(value);
    } else {
      this.insert(value, node.leftChild);
    }
  } else if (value > node.value) {
    if (node.rightChild === null) {
      node.rightChild = new TreeNode(value);
    } else {
      this.insert(value, node.rightChild);
    }
  }
}

value가 node의 값보다 작은지 확인한다.

작다면 node의 왼쪽 자손 어딘가에 삽입해야 한다는 뜻이다.
node의 왼쪽 자식이 없다면 value가 들어가야 할 자리가 그곳이므로 value를 왼쪽 자식으로 삽입한다. 재귀 호출이 없으니 이 조건이 기저 조건이다.
자식이 있다면 그 자리에 값을 넣을 수 없으므로 왼쪽 자식에 대해 insert를 재귀적으로 호출하면서 넣을 자리를 계속 검색한다. 언젠가는 자식이 없는 자손 노드에 도달하게 되고 그곳이 value가 들어가야 할 자리다.

15.4.2 삽입 순서

무작위로 정렬된 데이터로 트리를 생성해야 대개 균형 잡힌 트리가 생선된다. 완벽한 선형 트리는 최악의 경우 검색에 O(N)이 걸린다.

정렬된 데이터를 트리에 삽입하면 불균형이 심하고 덜 효율적일 수 있다. 오직 균형 트리일 때만 O(logN)이 걸린다.

따라서 정렬된 배열을 이진 탐색 트리로 변환하고 싶다면 먼저 데이터 순서를 무작위로 만드는 게 좋다.

15.5 삭제

삭제는 이진 탐색 트리에서 가장 어려운 연산이며 주의 깊게 실행해야 한다.

삭제할 노드에 자식이 없으면 그냥 삭제한다.
삭제할 노드에 자식이 하나면 노드를 삭제하고 그 자식을 삭제된 노드가 있던 위치에 넣는다.

15.5.1 자식이 둘인 노드 삭제

자식이 둘인 노드를 삭제할 때는 삭제된 노드를 후속자 노드로 대체한다.
- 후속자 노드는 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드다.

삭제된 노드와 그 노드의 모든 자손을 오름차순으로 정렬했을 때 삭제한 노드 다음으로 큰 수가 후속자 노드다.

15.5.2 후속자 노드 찾기

삭제된 값의 오른쪽 자식을 방문해서, 그 자식의 왼쪽 자식을 따라 계속해서 방문하며, 더 이상 왼쪽 자식이 없을 때까지 내려간다. 바닥(bottom) 값이 후속자 노드다.

15.5.3 오른쪽 자식이 있는 후속자 노드

후속자 노드에 왼쪽 자식은 없고 오른쪽 자식만 있을 수도 있다.

만약 후속자 노드에 오른쪽 자식이 있으면, 후속자 노드를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.

15.5.4 완전한 삭제 알고리즘

모든 단계를 종합하면 다음과 같다:

삭제할 노드에 자식이 없으면 그냥 삭제한다.
삭제할 노드에 자식이 하나면 노드를 삭제하고 그 자식을 삭제된 노드가 있던 위치에 넣는다.
자식이 둘인 노드를 삭제할 때는 삭제된 노드를 후속자 노드로 대체한다.
- 후속자 노드는 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드다.
- 삭제된 값의 오른쪽 자식을 방문해서, 그 자식의 왼쪽 자식을 따라 계속해서 방문하며, 더 이상 왼쪽 자식이 없을 때까지 내려간다. 바닥(bottom) 값이 후속자 노드다.
만약 후속자 노드에 오른쪽 자식이 있으면, 후속자 노드를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.

15.5.5 코드 구현: 이진 탐색 트리 삭제

delete(valueToDelete, node) {
  // 트리 바닥에 도달 해 부모 노드에 자식이 없으면 기저 조건
  if (node === null) {
    return null;
  } else if (valueToDelete < node.value) {
    // 삭제하려는 값이 현재 노드보다 작거나 크면
    // 왼쪽 혹은 오른쪽 하위 트리에 대한 재귀 호출 반환값을
    // 각각 왼쪽 혹은 오른쪽 자식에 할당
    node.leftChild = this.delete(valueToDelete, node.leftChild);
    return node;
  } else if (valueToDelete > node.value) {
    node.rightChild = this.delete(valueToDelete, node.rightChild);
    return node;
  } else if (valueToDelete === node.value) {
    // 삭제하려는 값이 현재 노드인 경우

    // 현재 노드에 왼쪽 자식이 없으면
    // 오른쪽 자식(과 하위트리)을 부모의 새로운 하위트리로 반환
    if (node.leftChild === null) {
      return node.rightChild;
    } else if (node.rightChild === null) {
      return node.leftChild;
    } else {
      // 현재 노드에 자식이 둘이면
      // 현재 노드의 값을 후속자 노드의 값으로 바꾸는 lift 함수를 호출
      node.rightChild = this.lift(node.rightChild, node);
      return node;
    }
  }
}

lift(node, nodeToDelete) {
  // 이 함수의 현재 노드의 왼쪽 자식이 있으면 왼쪽 하위트리로 계속해서 내려가도록 재귀 호출
  if (node.leftChild) {
    node.leftChild = this.lift(node.leftChild, nodeToDelete);
    return node;
  } else {
    // 왼쪽 자식이 없으면 현재 노드가 후속자 노드라는 뜻이다.
    nodeToDelete.value = node.value;
    return node.rightChild;
  }
}

기저 조건은 노드가 실제로 존재하지 않을 때, 재귀 호출에서 존재하지 않는 자식 노드에 접근할 때이다.

valueToDelete가 node의 값보다 작다면 삭제할 값은 현재 노드의 왼쪽 하위 트리에 있는 것이다. delete 함수 자체는 결국 노드를 반환하므로, 왼쪽 하위 트리에 재귀적으로 호출하여 얻은 반환값을 왼쪽 하위 트리에 덮어 쓴다. 반대의 경우 역시 마찬가지다.

valueToDelete가 node의 값이라면, 즉 삭제할 값을 찾았다면 node에 자식이 있는지 여부부터 판단한다.

node에 왼쪽 자식이 없으면 node의 오른쪽 자식을, node에 오른쪽 자식이 없으면 node의 왼쪽 자식을 함수의 결과로 반환한다.
그러면 반환한 트리는 이전 호출 스택의 왼쪽 혹은 오른쪽 자식 노드로 들어가게 되고, node는 결국 삭제되는 셈이다.

삭제하려는 노드에 자식이 둘인 경우, lift 함수를 호출해 그 결과를 node의 오른쪽 자식으로 넣는다.

lift함수의 역할은 다음과 같다.

후속자 노드를 찾는다.
nodeToDelte의 값을 후속자 노드의 값으로 덮어쓴다. 즉 후속자 노드를 올바른 위치에 넣는다. 후속자 노드 객체를 옮기는 게 아니라 삭제 중인 노드에 값을 복사할 뿐이다.
후속자 노드 객체를 삭제하기 위해 원래 후속자 노드의 오른쪽 자식을 후속자 노드 부모의 왼쪽 자식으로 넣는다.
재귀가 모두 끝나면 맨 처음에 전달받은 rightChild를 반환하거나, rightChild에 왼쪽 자식이 없어 원래 rightChild가 후속자 노드가 됐다면 null을 반환한다.

lift의 반환값을 받아 node의 오른쪽 자식으로 넣는다. 오른쪽 자식이 바뀌지 않거나, 오른쪽 자식이 후속자 노드라면 null로 바뀐다.

15.5.6 이진 탐색 트리 삭제의 효율성

트리 삭제도 일반적으로 O(logN)이다. 검색과 연결이 끊긴 자식을 처리하는 과정을 더해야 하기 때문이다.

15.6 이진 탐색 트리 다뤄보기

이진 탐색 트리는 데이터 삽입과 삭제가 정렬된 배열보다 빠르므로 데이터를 수정할 경우 특히 효율 적이다.

책 제목 리스트를 관리하는 애플리케이션을 생성할 경우, 알파벳 순으로 출력할 수 있으면서 리스트를 계속 수정해야 한다면 이진 탐색 트리가 효율적이다.

15.7 이진 탐색 트리 순회

이진 탐색 트리를 순서대로 출력하려면 어떻게 해야할까?

트리의 노드를 모두 빠짐없이 접근해야 한다. 이 과정을 자료 구조 순회traversal라 부른다.
트리를 순서대로 순회할 수 있어야 한다. 15.6의 예시에선 알파벳 순으로 순회해야 하므로 중위 순회inorder traversal라 알려진 방법을 수행한다.

중위 순회를 하기 위해 traverse이라는 재귀 함수를 생성한다. 함수는 다음과 같은 역할을 한다.

왼쪽 자식이 없는 노드에 닿을 때까지 왼쪽 자식에 traverse 함수를 재귀적으로 호출한다.
노드를 방문한다. 이 예제에서는 노드의 값을 출력한다.
오른쪽 자식이 없는 노드에 닿을 때 까지 오른쪽 자식에 traverse 함수를 재귀적으로 호출한다.

자식이 없는 노드에 traverse를 호출하는 것이 기저 조건이며, 이때 함수는 return만 실행한다.

traverseAndPrint(node) {
  if (node === null) return;
  this.traverseAndPrint(node.leftChild);
  console.log(node.value);
  this.traverseAndPrint(node.rightChild);
}

이렇게 되면 재귀 함수가 호출 스택에 쌓이며 순서대로 출력하게 된다.

트리 순회는 트리의 노드 N개를 모두 방문하므로 O(N)이다.

15.8 마무리

이진 탐색 트리는 정렬 순서를 유지하는 강력한 노드 기반 자료 구조이자 빠른 검색과 삽입, 삭제를 제공한다.

김현수

이전 포스트

14장 노드 기반 자료 구조

다음 포스트