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

Choose One Subtree

Binary Search Trees

ordering invariant(순서 불변식)로 BST를 판정하고 탐색 경로를 추적한다.

문제 1

Map 구현 고르기

  1. 정렬 배열에서 탐색과 가운데 삽입의 비용을 각각 적는다.
  2. 해시테이블로 키를 작은 순서대로 읽으려면 무엇이 더 필요한지 적는다.
  3. 키 갱신과 정렬 순회를 함께 자주 해야 할 때 BST가 알맞은 이유를 적는다.
  4. 정렬 연결리스트가 순서를 유지해도 탐색이 빠르지 않은 이유를 적는다.
해설 펼치기
  1. 탐색은 이진 탐색으로 O(log n), 가운데 삽입은 뒤 항목을 옮겨 O(n)이다.
  2. 해시테이블은 키의 대소 순서를 보존하지 않으므로 별도로 정렬해야 한다.
  3. BST는 키의 순서를 구조에 담아 비교 결과로 한쪽 부분 트리를 고르고, 중위 순회로 정렬 순서를 바로 읽을 수 있다.
  4. 가운데 원소로 바로 갈 수 없어 앞에서부터 따라가야 하므로 O(n)이다.
문제 2

BST인지 판정하기

트리 X는 20(9(-, 22), 31)이다.

  1. 각 부모와 자식 노드 사이의 대소 관계만 보면 조건이 맞는지 적는다.
  2. X가 BST인지 판정하고 어기는 노드와 이유를 적는다.
  3. is_bst(root, float("-inf"), float("inf"))로 검사할 때 노드 22에 전달되는 허용 범위와 결과를 적는다.
  4. 같은 키를 다시 넣었을 때의 정책을 미리 정해야 하는 이유와, 이번 강의의 정책을 적는다.
해설 펼치기
  1. 맞다. 9 < 20, 31 > 20, 22 > 9다.
  2. BST가 아니다. 22는 루트 20의 왼쪽 부분 트리에 있으므로 20보다 작아야 하는데 크다. 조건은 자식 하나가 아니라 부분 트리 전체에 걸린다.
  3. 루트에서 왼쪽으로 가며 상한이 20, 9에서 오른쪽으로 가며 하한이 9가 되어 범위는 (9, 20)이다. 22는 범위 밖이라 False다.
  4. 규칙이 없으면 같은 입력으로도 서로 다른 구조가 만들어질 수 있다. 이번 강의는 Map 방식으로 기존 키의 값을 갱신한다.
문제 3

정렬 순서와 양 끝

문제 3~5는 빈 BST에 키 20, 9, 31, 4, 15, 25, 40, 12, 47을 차례로 넣어 만든 다음 트리를 쓴다. 괄호는 (왼쪽 부분 트리, 오른쪽 부분 트리)이고 -는 빈 자식이다.

20(9(4, 15(12, -)), 31(25, 40(-, 47)))
  1. 트리를 중위 순회한 출력을 적는다.
  2. 최솟값과 최댓값을 찾는 경로를 각각 적는다.
  3. 중위 순회 결과가 정렬되는 이유를 부분 트리로 설명한다.
해설 펼치기
  1. 4, 9, 12, 15, 20, 25, 31, 40, 47이다.
  2. 최솟값은 20 → 9 → 4, 최댓값은 20 → 31 → 40 → 47이다. 각각 왼쪽·오른쪽 자식 노드가 없을 때까지 한쪽으로만 간다.
  3. 왼쪽 부분 트리의 키는 모두 현재 키보다 작고 오른쪽은 모두 크다. 각 부분 트리의 중위 순회도 정렬되어 있으므로 왼쪽, 현재, 오른쪽을 이으면 전체가 정렬된다.
문제 4

탐색 경로

문제 3의 BST를 쓴다.

  1. find(12)의 탐색 경로와 판정을 단계별로 적는다.
  2. find(33)과 find(26)의 탐색 경로와 멈추는 곳을 적는다.
  3. 실패한 find(33)이 알려 주는, 33을 새로 넣을 자리를 적는다.
  4. find(12)에서 20과 비교한 뒤 보지 않아도 되는 부분을 적는다.
해설 펼치기
  1. 20: 12가 작아 왼쪽, 9: 크므로 오른쪽, 15: 작으므로 왼쪽, 12: 같아 성공. 경로는 20 → 9 → 15 → 12다.
  2. find(33): 20 → 31 → 40에서 33 < 40이라 왼쪽인데 비어 있어 실패. find(26): 20 → 31 → 25에서 26 > 25라 오른쪽인데 비어 있어 실패.
  3. 40의 왼쪽 자식 자리다.
  4. 루트 20과 오른쪽 부분 트리 31, 25, 40, 47 전체다.
문제 5

Python 탐색과 비용

문제 3의 BST를 쓴다.

  1. _get이 노드를 반환하고 get이 값을 꺼내는 이유를, 값으로 None을 저장할 수 있는 경우와 함께 적는다.
  2. 6 in tree가 호출하는 메서드와 판정 기준을 적는다.
  3. 재귀 _get과 반복문 search가 방문하는 노드가 같은 이유를 적는다.
  4. 이 트리의 높이와 탐색의 최대 비교 노드 수를 적고, 탐색 비용을 높이로 설명하는 이유를 적는다.
해설 펼치기
  1. 값이 None이면 get의 None만으로 키 부재와 구별할 수 없다. 보조 탐색이 노드를 반환하면 노드 존재로 키 유무를 먼저 판단할 수 있다.
  2. __contains__가 _get(key, self.root)를 부르고 결과가 None이 아니면 True다.
  3. 둘 다 같은 비교 규칙으로 한 단계에 한 자식만 따라가므로 같은 탐색 경로를 방문한다.
  4. 높이는 3(예: 20 → 9 → 15 → 12)이고 최대 4개 노드와 비교한다. 탐색은 루트에서 멈춘 곳까지의 경로만 방문하므로 O(높이)이고, 트리 모양에 따라 경로 길이가 달라진다.