"이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편 9장의 써머리입니다."

09. 트리

1) 트리 개념

트리(Tree) : 데이터를 저장하고 탐색하기에 유용한 구조를 가짐

트리의 특성을 활용하는 분야

계층 구조를 표현하는 용도로 많이 사용(eg. 파일 시스템, 디렉터리 구조)

• 인공지능 : 판단 기준을 만들 때 의사 결정 트리 사용
  → 외부에서 입력된 데이터 분류, 상황 예측하는 모델
• 자동 완성 기능 : 트리는 문자열 처리에도 많이 사용
  → 검색 엔진에서 자동 검색어 추천 기능(트라이(trie) 트리 구조 활용)
• 데이터베이스 : 데이터를 쉽게 검색, 삽입, 삭제 할 수 있도록 트리 활용하여 데이터를 구조화하고 인덱싱 함(B-트리 or B+트리)
  
  

나무를 거꾸로 뒤집어 놓은 모양의 트리

트리를 구성하는 노드

루트 노드(Root Node) : 노드 중 가장 위에 있는 노드

노드를 연결하는 에지

간선 or 에지(Edge) : 노드와 노드 사이에 이어주는 선

• 트리는 노드와 노드가 단방향 간선으로 연결
• 루트 노드에서 각 노드까지 경로는 유일

레벨 : 루트 노드로부터 특정 노드까지 거쳐가는 최소한의 간선 수

부모-자식, 형제 관계를 가지는 노드

부모-자식 관계 : 간선으로 연결된 노드들

• 부모 노드(Parent Node) : 간선으로 직접 연결된 노드 중 상대적으로 위에 있는 노드
• 자식 노드(Child Node) : 그 아래에 있는 노드

형제 노드(Sibling Node) : 같은 부모를 갖는 노드

자식이 없는 말단 노드

리프 노드(Leaf Node) : 자식이 없는 노드

아래로 향하는 간선의 개수, 차수

차수(Degree) : 특정 노드에서 아래로 향하는 간선의 개수

2) 이진 트리 표현하기

이진 트리(Binary Tree) : 모든 노드의 최대 차수가 2를 넘지 않는 트리

• 이진 트리는 배열이나 포인터로 구현 가능
  
  

배열로 표현하기

• 이진 트리의 노드가 N개 일 때, 배열로 이진 트리 생성 시 O(N)이 걸림

배열 - 선형 자료구조 / 트리 - 계층 자료구조

3가지 규칙 필요

1) 루트 노드는 배열 인덱스 1번에 저장

2) 왼쪽 자식 노드의 배열 인덱스 : 부모 노드의 배열 인덱스 x 2

3) 오른쪽 자식 노드의 배열 인덱스 : 부모 노드의 배열 인덱스 x 2 + 1

* 메모리만 넉넉하다면 구현 시간을 단축하는 용도로 Good

이진 트리 순회하기

순회 : 어떤 데이터가 있을 때 그 데이터를 빠짐 없이 방문하는 것을 의미
→ 트리에서 데이터를 검색하려면 트리를 순회할 수 있어야 함

트리 순회 방법

• 전위 순회(Preorder)
  현재 노드를 부모 노드로 생각했을 때
  부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순서로 방문
• 중위 순회(Inorder)
  현재 노드를 부모 노드로 생각했을 때
  왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순서로 방문
• 후위 순회(Postorder)
  현재 노드를 부모 노드로 생각했을 때
  왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드 순서로 방문

* 방문 : 탐색에서 방문은 탐색을 마친 상태를 의미, 탐색 과정에서 지나치는 것과 그렇지 않은 것을 구분하기 위해 방문이라는 용어를 사용

전위 순회 과정 살펴보기

01단계) 루트 노드에서 시작

02단계) 현재 노드를 부모로 생각, 다음 왼쪽 자식 노드로 이동

03 단계) 오른쪽 자식 노드 방문

04 단계) 오른쪽 자식 노드가 없을 경우, 현재 노드의 부모 노드로 이동

* 전위 순회는 주로 트리를 복사할 때 많이 사용

중위 순회 과정 살펴보기

01단계) 루트 노드에서 시작 → 왼쪽 자식 노드 이동

02단계) 01단계의 노드를 부모로, 이 노드의 왼쪽 자식 노드 방문/이동

03단계) 부모 노드 방문

04단계) 오른쪽 자식 노드 방문 후 거슬러 올라감

* 중위 순회는 이진 탐색 트리에서 정렬된 순서대로 값을 가져올 때 사용

후위 순회 과정 살펴보기

01단계) 루트 노트에서 시작 → 왼쪽 자식 노드로 이동

02단계) 왼쪽 노드의 자식이 없을 때까지 이동 후 자신 방문

03단계) 오른쪽 노드 방문 후 거슬러 올라가서 부모 노드 방문

04단계) 왼쪽 트리 전체 완료 후 오른쪽 트리 시작할 때도 같은 방식

노드 삭제

• 부모 먼저 삭제 X
• 자식부터 삭제해야 트리가 유지되고, 재귀로 루트 노드까지 삭제 가능

* 자식 노드부터 방문한다는 특성이 있는 후위 순회는 트리 삭제에 자주 활용

포인터로 표현하기

포인터로 트리 표현 시 노드부터 정의 필요

노드는 노드의 값, 왼쪽 자식 노드와 오른쪽 자식 노드를 가짐

포인터로 표현한 트리는 배열과 달리 인덱스 연산을 하지 않으므로, 메모리 공간 낭비 X

3) 이진 트리 탐색하기

이진 트리에서 가장 중요한 부분 : 탐색을 효율적으로 할 수 있도록 트리 구축하는 것

이진 탐색 트리(Binary Search Tree) 구축하기

이진 탐색 트리 정렬 방식
: 데이터 크기를 따져 크기가 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치

이진 탐색 트리 탐색하기

1) 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료하고 크면 오른쪽 노드 탐색

2) 본인이 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드 탐색

3) 값을 찾으면 종료. 노드가 없을 때까지 계속 탐색했는데 값이 없으면 현재 트리에 값이 없는 것

이진 탐색 트리는 크면 오른쪽, 작으면 왼쪽

모든 탐색 알고리즘에서 탐색 효율을 개선하는 방법은 같음 - 탐색 대상이 아닌 노드를 한 번에 많이 제외할 수 있으면 됨

$\therefore$ 데이터 크기에 따라 하위 데이터 중 한 방향을 검색 대상에서 제외 - 검색 빨라짐

이진 탐색 트리의 시간 복잡도

이진 탐색 트리의 시간 복잡도는 트리 균형에 의존. 즉, 각 노드의 차수가 비슷하게 유지되면서 각 노드의 자식 노드 수가 비슷하게 유지되는 것을 의미

⇒ 트리에 저장된 노드가 N개 일 때 시간 복잡도는 O(logN)

균형 이진 탐색 트리(Balanced Binary Search Tree)

한 쪽으로만 치우쳐지지 않도록 균형을 유지하는 이진 탐색 트리

세부적으로 AVL 트리, 레드-블랙 트리 등으로 구분

이진 트리의 탐색 연산 횟수가 트리 높이에 비례하고 트리의 높이는 logN이므로 탐색 시간 복잡도를 O(logN)으로 유지 가능, But 구현 난이도가 높음

4) 몸 풀기 문제

문제 26) 트리 순회

이진 트리를 표현한 리스트 nodes를 인자로 받아 트리를 표현한 것. 해당 이진 트리에 대해 전위 순회, 중위 순회, 후위 순회 결과를 반환하는 함수 구현

def preorder(nodes, idx):
    res = []
    if idx < len(nodes):
      res.append(nodes[idx])
      res.extend(preorder(nodes, 2 * idx + 1 ))
      res.extend(preorder(nodes, 2 * idx + 2))
    return res

def inorder(nodes, idx):
  res = []
  if idx < len(nodes):
    res.extend(inorder(nodes, 2 * idx + 1))
    res.append(nodes[idx])
    res.extend(inorder(nodes, 2 * idx + 2))
  return res

def postorder(nodes, idx):
  res = []
  if idx < len(nodes):
    res.extend(postorder(nodes, 2 * idx + 1))
    res.extend(postorder(nodes, 2 * idx + 2))
    res.append(nodes[idx])
  return res

def solution(nodes):
  result = [
    preorder(nodes, 0),
    inorder(nodes, 0),
    postorder(nodes, 0)
  ]
  return result

문제 27) 이진 탐색 트리 구현

첫 번째 인수 lst를 이용하여 이진 탐색 트리 생성, 두 번째 인수 search_lst에 있는 각 노드를 이진 탐색 트리에서 찾을 수 있는지 확인하여 True or False를 담은 리스트 result를 반환하는 함수 작성

class Node:
	def __init__(self, item):
		self.left = None
		self.right = None
		self.item = item
  
class BinaryTree:
  def __init__(self):
    self.root = None
    
  def insert(self, key):
    self.root = self._insert(self.root, key)
      
  def _insert(self, root, key):
    if root is None:
      return Node(key)
    
    if key < root.item:
      root.left = self._insert(root.left, key)
    else:
      root.right = self._insert(root.right, key)
    
    return root
  
  def search(self, root, value):
    if root is None or root.item == value:
      return root is not None
    
    if value < root.item:
      return self.search(root.left, value)
    else:
      return self.search(root.right, value)

def solution(lst, search_lst):
  tree = BinaryTree()
  for value in lst:
    tree.insert(value)
  
  result = [tree.search(tree.root, value) for value in search_lst]
  return result

5) 합격자가 되는 모의 테스트

문제 28) 예상 대진표

게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution()의 인수로 주어질 때 첫 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는 지 반환

def solution(n,a,b):
    answer = 0
    while a != b:
        a = (a + 1) // 2
        b = (b + 1) // 2
        answer += 1

    return answer