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

• 데이터를 정렬하고 싶을 수 있다.
• 퀵 정렬 같은 정렬 알고리즘으로 데이터를 정리할 수 있지만 O(NlogN)이라는 시간이 필요하다.
• 따라서 데이터를 자주 정렬해야 한다면 애초에 데이터를 항상 정렬된 순서로 유지하는 편이 합리적이다.
• 정렬된 배열은 읽기 O(1), 검색 O(logN), 삽입 O(N), 삭제 O(N)이다.
• 순서를 유지하면서도 빠른 검색과 삽입, 삭제가 가능한 자료 구조가 필요하면 어떻게 해야 할까? 정렬된 배열도 해시 테이블도 완벽하지 않다.
• 이진 탐색 트리를 보자.

1. 트리

• 트리(tree)는 노드 기반 자료 구조이며, 트리의 각 노드는 여러 노드로의 링크를 포함할 수 있다.
• 가장 상위에 위치한 노드를 루트라고 부른다. 루트는 트리의 꼭대기다.
• 노드는 부모와 자식 노드가 있을 수 있다.
• 패밀리 트리에는 노드에 자손과 조상이 있을 수 있다.
• 트리에는 레벨이 있다. 각 레벨은 트리에서 같은 줄이다.
• 트리의 프로퍼티는 균형 잡힌 정도를 말한다. 모든 노드에서 하위 트리의 노드 개수가 같으면 그 트리는 균형 트리다.
• 반대는 불균형 트리라고 부른다.

2. 이진 탐색 트리

• 이진 탐색 트리는 다음의 규칙이 포함된 트리다.
  • 각 노드의 자식은 최대 왼쪽에 하나, 오른쪽에 하나다.
  • 한 노드의 왼쪽 자손은 그 노드보다 작은 값만 포함할 수 있다. 마찬가지로, 오른쪽 자손은 그 노드보다 큰 값만 포함할 수 있다.

3. 검색

• 이진 탐색 트리를 검색하는 알고리즘을 살펴보자.

1. 노드를 “현재 노드”로 지정한다.
2. 현재 노드의 값을 확인한다.
3. 찾고 있는 값이면 끝난다!
4. 찾고 있는 값이 현재 노드보다 작으면 왼쪽 하위 트리를 검색한다.
5. 찾고 있는 값이 현재 노드보다 크면 오른쪽 하위 트리를 검색한다.
6. 찾고 있는 값을 찾았거나 트리 바닥에 닿을 때까지 1단계부터 5단계를 반복한다.

3.1 이진 탐색 트리의 효율성

• 위의 검색 알고리즘을 살펴보면, 각 단계마다 검색할 대상이 남은 노드의 반으로 줄어든다.
• 왼쪽 하위 트리를 따라 검색하기로 결정하는 순간, 오른쪽 하위 트리는 검색에서 아예 제외된다.
• 따라서 이진 탐색 트리 검색은 O(logN)이다.

3.2 log(N) 레벨

• 균형 이진 트리에 노드가 N개면 레벨이 약 logN개라는 이진 트리의 또 다른 일반적 특성이 존재한다.
• 노드가 N개인 트리에서 모든 자리마다 노드를 두려면 log(N)레벨이 필요하다.

4. 삽입

• 앞서 언급했듯이 이진 탐색 트리는 삽입에 가장 뛰어나다.
• 삽입은 노드의 적절한 위치를 찾기 위한 검색에 삽입 1단계가 추가로 필요하다.
• 즉, 삽입은 logN + 1단계가 걸린다.
• 이와 대조적으로 정렬된 배열에서는 검색뿐 아니라 값을 삽입할 공간을 마련하기 위해 데이터를 오른쪽으로 시프트해야 하기 때문에 삽입에 O(N)이 필요하다.
• 그렇기 때문에 이진 탐색 트리가 매우 효율적이다. 정렬된 배열은 검색에 O(logN), 삽입에 O(N)이 걸리는 반면, 이진 트리는 검색과 삽입 모두 O(logN)이다.

4.2 삽입 순서

• 한 가지 알아둘 점은 무작위로 정렬된 데이터로 트리를 생성해야 대개 균형 잡힌 트리가 생성된다는 점이다.
• 반대로 정렬된 데이터를 트리에 삽입하면 불균형이 심하고 덜 효율적일 수 있다.
• 예를 들어 1, 2, 3, 4, 5를 트리에 순서대로 삽입한다면 선형 트리가 생성될 것이다.
• 그러나 같은 데이터를 3, 2, 1, 4, 5 순서대로 삽입한다면 균형 잡힌 트리가 된다.
• 오로지 균형 트리일 때만 검색에 O(logN)이 걸린다.
• 이러한 이유로 정렬된 배열을 이진 탐색 트리로 변환하고 싶을 때는 먼저 데이터 순서를 무작위로 만드는 게 좋다.

5. 삭제

• 삭제는 이진 탐색 트리에서 가장 어려운 연산이며 주의 깊게 실행해야 한다.
• 삭제할 노드에 자식이 없으면 그냥 삭제한다.
• 삭제할 노드에 자식이 하나면 노드를 삭제하고 그 자식을 삭제된 노드가 있던 자리에 넣는다.

5.1 자식이 둘인 노드 삭제

• 가장 복잡한 시나리오이다.
• 자식이 둘인 노드를 삭제할 때는 삭제된 노드를 후속자 노드로 대체한다. 후속자 노드란 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드다.
• ?
• 다시 말하자면, 삭제된 노드와 그 노드의 모든 자손을 정렬했을 때 방금 삭제한 노드 다음으로 큰 수가 후속자 노드다.

5.2 후속자 노드 찾기

• 후속자 노드를 어떻게 찾을까?
• 삭제된 값의 오른쪽 자식을 방문해서 그 자식의 왼쪽 자식을 따라 계속해서 방문하며 더 이상 왼쪽 자식이 없을 때까지 내려간다. 바닥값이 후속자 노드다.
• ok

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

• 하지만 아직 고려하지 않은 경우가 있다.
• 후속자 노드에 오른쪽 자식이 있을 때다.
• 만약 후속자 노드에 오른쪽 자식이 있으면 후속자 노드를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.
• …?

5.4 완전한 삭제 알고리즘

• 모든 단계를 종합하면 이진 트리의 삭제 알고리즘은 다음과 같다.
• 삭제할 노드에 자식이 없으면 그냥 삭제한다.
• 삭제할 노드에 자식이 하나면 노드를 삭제하고 그 자식을 삭제된 노드가 있던 자리에 넣는다.
• 자식이 둘인 노드를 삭제할 때는 삭제된 노드를 후속자 노드로 대체한다.
  • 후속자 노드란 삭제된 노드보다 큰 값 중 최솟값을 갖는 자식 노드다.
  • 삭제된 값의 오른쪽 자식을 방문해서 그 자식의 왼쪽 자식을 따라 계속해서 방문하며 더 이상 왼쪽 자식이 없을 때까지 내려간다.
  • 바닥값이 후속자 노드다.
  • 만약 후속자 노드에 오른쪽 자식이 있으면 후속자 노드를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.

5.6 이진 탐색 트리의 효율성

• 검색과 삽입처럼 트리 삭제도 일반적으로 O(logN)이다.

7. 이진 탐색 트리 순회

• 자료구조에서 모든 노드를 방문하는 과정을 자료구조 순회traversal라고 부른다.
• 중위 순회: 트리를 오름차순으로 순회하는 방법
• 재귀는 중위 순회를 수행하는 훌륭한 도구다.
• 방문 순서는 다음과 같다.

1. 노드의 왼쪽 자식을 재귀적으로 방문한다. 왼쪽 자식이 없는 노드에 닿을 때까지 함수를 계속 호출한다.
2. 노드의 값을 출력한다.
3. 노드의 오른쪽 자식을 재귀적으로 방문한다. 오른쪽 자식이 없는 노드에 닿을 때까지 함수를 계속 호출한다.

8. 마무리

• 이진 탐색 트리는 정렬 순서를 유지하는 강력한 노드 기반 자료구조이자 빠른 검색과 삽입, 삭제도 제공한다. 사촌격인 연결 리스트보다 복잡하지만 가치가 엄청나다.
• 그러나 이진 탐색 트리는 트리 종류 중 하나일 뿐이다. 다른 종류의 트리가 많고, 각각 특수한 상황에서 특유의 이점이 있다.
• 16장에서는 구체적이면서도 일반적인 시나리오에서 속도상의 이점이 있는 또다른 트리를 알아본다.