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

정렬 알고리즘은 아무리 빨라도 O(NlogN)시간이 걸린다. 따라서 데이터를 자주 정렬해야 하면 다시 정렬하는 일이 없게 애초에 데이터를 항상 정렬된 순서로 유지하는 편이 합리적이다.

 

정렬된 배열은 순서대로 데이터를 유지하는 간단하면서도 효과적인 도구다. 또한 특정 연산에 매우 빨라서 읽기에는 O(1), 이진 검색을 사용할 때는 O(logN)이 걸린다. 하지만 삽입과 삭제가 상대적으로 느리다. 최악의 시나리오일 경우 N단계가 걸리고, 평균적으로 N / 2 단계가 걸린다. 즉 O(N)이므로 단순한 삽입이나 삭제치고는 느리다.

 

전반벅으로 빠른 속도를 내는 자료 구조를 원한다면 해시 테이블이 좋은 선택지다. 해시 테이블은 검색, 삽입, 삭제가 O(1)이다. 연산이 빠르지만 순서를 유지하지 못하므로 알파벳순으로 목록을 정렬하는 애플리케이션에는 적절치 않다.

15.1 트리

전형적인 연결 리스트는 각 노드마다 그 노드와 다른 한 노드를 연결하는 링크를 포함한다.

트리 역시 노드 기반 자료 구조이지만 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다.

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

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. 노드를 "현재 노드"로 지정한다. (처음에는 루트 노드가 첫 번째 "현재 노드"다.)
2. 현재 노드의 값을 확인한다.
3. 찾고 있는 값이면 검색을 종료한다.
4. 찾고 있는 값이 현재 노드보다 작으면 왼쪽 하위 트리를 검색한다.
5. 찾고 있는 값이 현재 노드보다 크면 오른쪽 하위 트리를 검색한다.
6. 찾고 있는 값을 찾았거나, 트리 바닥에 닿을 때(즉, 트리 내에 찾고 있는 값이 없을 때)까지 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(N)이 걸린다.

 

정렬된 배열은 검색에 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.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함수의 역할은 다음과 같다.

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

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

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

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

15.6 이진 탐색 트리 다뤄보기

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

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

15.7 이진 탐색 트리 순회

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

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

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

1. 왼쪽 자식이 없는 노드에 닿을 때까지 왼쪽 자식에 traverse 함수를 재귀적으로 호출한다.
2. 노드를 방문한다. 이 예제에서는 노드의 값을 출력한다.
3. 오른쪽 자식이 없는 노드에 닿을 때 까지 오른쪽 자식에 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 마무리

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