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

From Links to Hierarchies

Tree Terminology

트리의 관계와 깊이·높이를 읽고 두 Python 표현으로 추적한다.

문제 1

트리인지 판정하기

다음 구조가 트리인지 판정하고 근거를 적는다.

  1. 노드 X의 바로 위에 P와 Q 두 노드가 연결되어 있다.
  2. 부모 노드가 없는 노드가 두 개 있다.
  3. 디렉터리 / 아래에 home과 usr가 있고 home 아래에 a.txt가 있다.
  4. 노드마다 다음 노드가 최대 하나인 단일 연결리스트.

마지막으로, 파일 시스템을 훑는 walk(folder)가 하위 디렉터리에 같은 함수를 다시 적용할 수 있는 이유를 한 문장으로 적는다.

해설 펼치기
  1. 트리가 아니다. 루트 이외 노드의 위쪽 연결은 하나여야 하고, 갈라진 뒤 다시 합쳐질 수 없다.
  2. 트리가 아니다. 시작 노드(루트)는 하나여야 한다.
  3. 트리다. 시작점이 하나이고 각 항목의 위쪽 연결이 하나다.
  4. 트리다. 트리의 조건을 만족하며 한 줄로 이어진 모양이다. 연결리스트는 다음 연결이 최대 1개, 트리는 여러 개를 둘 수 있다.

하위 디렉터리도 다시 트리이므로 같은 절차를 적용할 수 있다. 이런 방식을 재귀(recursion)라 한다.

문제 2

관계 용어 읽기

문제 2~5는 중첩 리스트 [루트, 왼쪽 부분 트리, 오른쪽 부분 트리]로 적은 다음 이진트리를 쓴다.

T = ["A", ["B", ["D", [], []], ["E", ["G", [], []], []]], ["C", [], ["F", [], []]]]
  1. 루트, 단말 노드를 모두 적는다.
  2. G의 부모 노드, B의 자식 노드, D의 형제 노드를 적는다.
  3. B를 루트로 하는 부분 트리에 속한 노드를 모두 적는다.
  4. C의 왼쪽 자식 노드는 무엇인지 적는다.
해설 펼치기
  1. 루트는 A, 단말 노드는 D, G, F다.
  2. G의 부모 노드는 E, B의 자식 노드는 D와 E, D의 형제 노드는 E다.
  3. B, D, E, G다. 부분 트리는 한 노드와 그 아래의 모든 자손이다.
  4. 없다. C는 오른쪽 자식 노드 F만 가진다.
문제 3

깊이와 높이

문제 2의 원래 이진트리 T를 쓴다.

  1. A, E, G의 깊이를 적는다.
  2. G, E, B, C의 높이와 트리의 높이를 적는다.
  3. 빈 트리의 높이를 −1로 둔 재귀식으로 E의 높이를 계산한다.
  4. 깊이와 높이가 각각 어느 방향으로 세는 거리인지 적는다.
해설 펼치기
  1. A는 0, E는 2, G는 3이다.
  2. G는 단말 노드라 0, E는 1 + max{0, −1} = 1, B는 1 + max{0, 1} = 2, C는 1 + max{−1, 0} = 1, 트리의 높이는 루트 A의 높이 1 + max{2, 1} = 3이다.
  3. E의 왼쪽 부분 트리 G의 높이는 0, 오른쪽은 빈 트리라 −1이므로 1 + max{0, −1} = 1이다.
  4. 깊이는 루트에서 그 노드까지 아래로, 높이는 그 노드에서 가장 먼 단말 노드까지 센 연결 수다.
문제 4

중첩 리스트로 읽고 바꾸기

문제 2의 원래 이진트리 T를 쓴다.

  1. T[1][2][0]과 T[2][1]의 값을 적는다.
  2. 단말 노드 G가 리스트에서 어떤 모양인지 적고, 단말 노드에 새 형식을 만들지 않는 이유를 적는다.
  3. insert_left(T, "X")를 실행하면 루트의 왼쪽 부분 트리가 어떻게 바뀌는지 적고, 바뀐 트리의 높이를 구한다.
  4. B와 C를 서로 바꾼 트리가 T와 같은 이진트리인지 판단한다.
해설 펼치기
  1. T[1]은 B의 부분 트리, T[1][2]는 E의 부분 트리라 T[1][2][0]은 "E"다. T[2][1]은 C의 왼쪽 부분 트리라 []다.
  2. ["G", [], []]이다. 빈 부분 트리 두 개로 표현하면 같은 세 인덱스 규칙과 재귀 정의를 그대로 쓸 수 있다.
  3. 기존 T[1](B 부분 트리)을 꺼내 ["X", B 부분 트리, []]를 만들어 T[1]에 넣는다. A → X → B → E → G 경로가 가장 길어 높이는 4다.
  4. 다르다. 이진트리는 왼쪽과 오른쪽 자리를 구분하므로 노드 수가 같아도 서로 다른 이진트리다.
문제 5

노드와 참조로 읽기

문제 2의 원래 이진트리 T를 BinaryTree 노드(key, left_child, right_child)로 만들어 루트를 tree에 저장했다.

  1. tree.left_child.right_child.key와 tree.right_child.left_child의 값을 적는다.
  2. 노드 3개로 만들 수 있는 이진트리 가운데 높이가 가장 작은 것과 가장 큰 것의 높이를 적는다.
  3. ‘이진트리이면 왼쪽 값이 작고 오른쪽 값이 크다’는 말이 맞는지 판단한다.
해설 펼치기
  1. "E"와 None이다. 빈 자식 노드는 None으로 나타낸다.
  2. 루트에 두 자식 노드를 둔 모양이 높이 1, 한 줄로 이은 모양이 높이 2다. 노드 수만으로 높이를 정할 수 없다.
  3. 틀렸다. 이진트리는 자식 노드가 최대 둘이라는 구조만 정하고 키의 크기 순서는 정하지 않는다. 그 조건은 이진 탐색 트리에서 추가된다.