부산대학교자료구조
Scientific Inference Lab

Keeping the Order

BST Insertion and Deletion

탐색 경로로 새 키를 붙이고 자식 수에 따라 노드를 지우는 과정을 추적한다.

문제 1

삽입이 붙는 자리

문제 1~4는 빈 BST에 키 45, 25, 60, 15, 35, 50, 70, 30, 55를 차례로 넣은 트리를 쓴다. 괄호 표기는 (왼쪽 부분 트리, 오른쪽 부분 트리), -는 빈 자식이다. 문제 2와 3의 삭제는 각각 이 트리에서 따로 시작한다.

  1. 키 30과 55를 넣을 때 지나온 노드와 붙은 자리, 비교 횟수를 적는다.
  2. 아홉 키를 모두 넣은 트리를 괄호 표기로 적는다.
  3. 이미 있는 키 35를 다시 넣을 때 Map 방식의 동작을 적는다.
  4. 탐색이 멈춘 자리에 붙여도 ordering invariant(순서 불변식)가 깨지지 않는 이유를 적는다.
해설 펼치기
  1. 30: 45 → 25 → 35를 지나 35의 왼쪽에 붙는다. 55: 45 → 60 → 50을 지나 50의 오른쪽에 붙는다. 둘 다 지나온 노드는 3개다. _put처럼 <를 먼저, 거짓이면 >를 비교하면 키 비교는 30이 4번(45에서 1, 25에서 2, 35에서 1), 55가 5번(45에서 2, 60에서 1, 50에서 2)이다.
  2. 45(25(15, 35(30, -)), 60(50(-, 55), 70))다.
  3. 노드를 새로 만들지 않고 키 35의 값을 새 값으로 갱신한다. 노드 수는 그대로다.
  4. 지나온 노드와 이미 대소를 비교했고 매번 조건에 맞는 쪽으로 내려왔으므로 멈춘 자리에서도 조건이 유지된다.
문제 2

단말 노드와 자식이 하나인 노드 지우기

문제 1의 원래 BST에서 새로 시작한다.

  1. 키 15를 지울 때의 경우와 바꾸는 참조, 결과 트리를 적는다.
  2. 키 35를 지울 때의 경우와 결과 트리를 적는다.
  3. 35를 지운 뒤 30을 25의 오른쪽에 올려도 ordering invariant가 유지되는 이유를 적는다.
  4. 두 삭제 뒤에도 ordering invariant가 유지되는지 확인할 수 있는 순회를 적고, 각 결과 트리에서 그 순회 결과를 적는다.
해설 펼치기
  1. 단말 노드다. 부모 25의 왼쪽 참조만 비워 45(25(-, 35(30, -)), 60(50(-, 55), 70))가 된다.
  2. 자식이 30 하나인 경우다. 30을 35 자리로 splice해 45(25(15, 30), 60(50(-, 55), 70))가 된다.
  3. 30은 35의 부분 트리에 있었으므로 25보다 크고 45보다 작은 범위 안에 있다. 그 범위가 부모와의 대소 관계를 그대로 보장한다.
  4. 중위 순회다. 15를 지운 트리는 25, 30, 35, 45, 50, 55, 60, 70, 35를 지운 트리는 15, 25, 30, 45, 50, 55, 60, 70으로 지운 값만 빠지고 오름차순이 유지된다.
문제 3

자식이 둘인 노드 지우기

문제 1의 원래 BST에서 새로 시작한다.

  1. 루트 45를 후계 노드로 지울 때 후계 노드를 찾는 경로, 옮기는 값, splice하는 곳, 결과 트리를 적는다.
  2. 결과 트리의 중위 순회를 적어 순서가 지켜졌는지 확인한다.
  3. 같은 45를 선행 노드로 지우면 결과 트리가 어떻게 되는지 적는다.
  4. 후계 노드에 왼쪽 자식 노드가 없는 이유와, 그래서 세 번째 경우가 어떻게 앞의 경우로 돌아오는지 적는다.
해설 펼치기
  1. 오른쪽 자식 60으로 간 뒤 왼쪽 끝 50에 닿는다. 50을 루트에 옮겨 적고, 50의 자리에는 오른쪽 자식 55를 splice한다. 결과는 50(25(15, 35(30, -)), 60(55, 70))다.
  2. 15, 25, 30, 35, 50, 55, 60, 70이다. 지운 45만 빠지고 오름차순이다.
  3. 선행 노드는 왼쪽 부분 트리의 최댓값 35다. 35를 루트에 옮기고 35의 자리에 30을 splice해 35(25(15, 30), 60(50(-, 55), 70))가 된다.
  4. 왼쪽 자식이 있다면 그 노드가 더 작아 오른쪽 부분 트리의 최솟값이 아니게 된다. 후계 노드는 자식이 없거나 오른쪽 하나뿐이라 경우 1이나 2로 지운다.
문제 4

높이가 비용을 정한다

문제 1의 원래 BST에서 새로 시작한다.

  1. 문제 1의 트리 높이를 적는다.
  2. 같은 아홉 키를 정렬된 순서 15, 25, 30, …, 70으로 넣으면 트리 모양과 높이가 어떻게 되는지 적는다.
  3. 탐색·삽입·삭제의 비용이 모두 높이에 비례하는 이유를 적고, 삭제에서 후계 노드를 찾는 일까지 포함해도 그런 이유를 적는다.
  4. 무작위 순서 삽입의 평균 비용이 좋아도 최악의 경우를 보장하지 못하는 이유를 적는다.
해설 펼치기
  1. 45 → 25 → 35 → 30과 45 → 60 → 50 → 55가 가장 길어 높이는 3이다.
  2. 한쪽으로만 자라는 편향 트리가 되고 높이는 8이다. 연산 비용이 O(n)이 된다.
  3. 세 연산 모두 루트에서 한 갈래를 따라 내려간 뒤 O(1) 작업을 한다. 삭제는 지울 노드와 후계 노드를 찾으려 두 번 내려가도 여전히 높이에 비례한다.
  4. 입력 순서는 사용하는 쪽이 정하지 못하고 정렬된 입력은 실제로 드물지 않다. 평균이 좋다는 것은 최악의 경우 보장이 아니다.
문제 5

Python BST Map 구현

  1. put이 빈 트리와 일반 경우를 나누는 이유와 _put이 맡는 일을 적는다.
  2. _put에서 키가 같을 때 하는 일과, 노드를 새로 만들지 않는 이유를 적는다.
  3. __iter__가 중위 순회를 쓰면 보장되는 순서와, 해시테이블 대신 BST를 쓰는 연산 두 가지를 적는다.
  4. 구현 뒤 확인할 조건 네 가지를 적는다.
해설 펼치기
  1. 루트가 없으면 새 노드를 루트로 만들고, 있으면 _put이 현재 부분 트리를 인자로 받아 비교 방향으로 내려가 빈 자리에 새 노드를 붙인다.
  2. node.value = value로 값만 갱신한다. Map은 같은 키의 노드를 하나만 둔다.
  3. 키가 오름차순으로 나온다. 순서대로 출력하기와 범위로 찾기에서 해시테이블은 별도 정렬이나 모든 키 확인이 필요하다.
  4. 삽입 뒤 중위 순회가 오름차순인지, 삭제 세 경우 뒤에도 오름차순인지, 없는 키의 탐색·삭제가 정한 실패 규칙을 따르는지, 같은 키 재삽입에서 노드 수가 같고 값만 바뀌는지 확인한다.