[데이터 구조와 활용] 트리

1. 트리

 (1) 트리의 정의

  - 트리 : 노드와 간선으로 구성된 계층적이고 비선형인 데이터 구조

 - 트리는 순환이 없는 연결된 그래프의 한 형태임

(2) 경로 : 한노드에서 다른 노드로 이동하는 동안 거치는 노드들의 순서

  - 연결된 간선을 따라 이동하는 노드들의 나열이 경로

  - 노드는 중복해서 방문 가능하며, 어떤 노드도 두 번 이상 방문하지 않는 경로를 단순 경로라 함

(3) 순환 : 한 노드에서 출발하여 연결된 간선을 따라 노드들을 이동하다가 다시 출발 노드로 돌아올 수 있는 경로

  - 적어도 하나 이상의 독립적인 간선을 포함해야 함

(4) 연결된 그래프 : 그래프 내에서 어떤 두 노드도 경로를 통해 서로 연결될 수 있음을 의미

  - 한 노드에서 다른 노드로 이동할 수 있는 경우가 없으면 연결된 그래프

(5) 트리의 주요 표현

 - 루트 : 트리의 최상위 노드, 부모가 없는 노드

 - 부모 : 특정 노드 바로 위에 연결된 노드

 - 자식 : 특정 노드 바로 아래에 연결된 노드

 - 형제 : 동일한 부모를 공유하는 노드 

 - 리프 : 자식 노드가 없는 노드(트리의 말단)

 - 높이 : 루트에서 가장 깊은 리프까지의 간선 수

 - 깊이 : 루트에서 특정 노드까지 간선 수

 - 차수 : 특정 노드가 가진 자식 수

 - 레벨 : 루트 노드를 레벨 0으로 하여 같은 깊이를 가진 노드들의 집합

 - 서브 트리 : 트리 내에서 특정 노드를 루트로 하는 더 작은 트리 구조 

(6) 트리의 종류

 - 일반 트리 : 일반적인 트리 구조

 - 이진 트리 : 자식 노드가 최대 2개인 트리

 - 완전 이진 트리 : 마지막 레벨을 제외한 모든 레벨이 노드가 채워지고 마지막 레벨은 왼쪽부터 순서대로 채워진 구조

 - 포화 이진 트리 : 노드가 꽉차있는 형태로 데이터 표현에 명확, 모든 노드가 0개 혹은 2개의 자식을 가짐

 - 이진 탐색 트리 : 모든 노드가 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 높은 값을 가지는 트리 구조

(7) 이진 탐색 트리 : 효율적인 데이터 탐색과 관리를 위한 특별한 구조의 이진 트리

 - 왼쪽 서브트리의 모든 노드는 항상 부모 노드보다 작은 값을 가짐

 - 오른쪽 서브트리의 모든 노드는 항상 부모 노드보다 큰 값을 가짐

 - 데이터 검색/삽입/삭제 연산을 평균적으로 O(logN)의 빠른 수행 시간 안에 탐색 가능

(8) 트리 활용 사례 : 파일 시스템, 가계도, 회사 조직도, 의사결정 트리, 웹사이트 메뉴 구조

 

2. 트리 표현

(1) 배열 사용 : 노드를 뱅ㄹ의 인덱스에 저장하여 표현 (List)

 - 완전 이진 트리 또는 포화 이진 트리처럼 노드가 균형 잡혀 있는 경우

 - 빠른 접근 속도

 - 노드 추가/삭제 비효율

(2) 연결 리스트 : 노드를 포인터(링크)로 연결하여 표현 (Dictionary)

 - 노드의 추가 및 삭제가 빈번한 경우 

 - 노드 추가/삭제 효율적

 - 느린 노드 접근 속도

(3) 배열을 통한 이진 트리 표현

 - 배열의 첫 번째 인덱스는 일반적으로 사용하지 않고 보통 1번 인덱스부터 루트 노드를 저장

 > 배열의 인덱스 계산을 간단하게 하기 위해서임

 - 인덱스가 i인 노드에 대해 , 

 > 왼쪽 자식은 2 * i에 위치

 > 오른쪽 자식은 2 * i + 1에 위치

 > 부모 노드는 i//2에 위치

t = [None, 'A', 'B', 'C', 'D', 'E', 'F', 'G'] print('B의 왼쪽 자식 : ', t[2*2])  # D print('B의 오른쪽 자식 : ', t[2*2+1]) # E print('F의 부모 : ',t[6//2]) # C

(4) 연결 리스트 이용한 트리 표현

 - 연결 리스트 방식에서는 각 노드가 자식 노드를 참조(링크) 함

 - 각 노드는 자신이 연결된 노드 정보를 갖고 있어 자식 노드를 쉽게 참조할 수 있음

t = [None, 'A', 'B', 'C', 'D', 'E', 'F', 'G'] print('B의 왼쪽 자식 : ', t[2*2])  # D print('B의 오른쪽 자식 : ', t[2*2+1]) # E print('F의 부모 : ',t[6//2]) # C t2 = {     'A' : ['B','C'],     'B' : ['D','F'],     'C' : ['F','G'],     'D' : [] , 'E' : [], 'F' : [], 'G' : []     } print('A의 자식 : ', t2['A'])  // A의 자식 :  ['B', 'C'] print('B의 자식 : ', t2['B']) // B의 자식 :  ['D', 'F'] if not t2['D'] : // True     print('D는 리프 노드입니다.')

 

3. 트리 순회

(1) 트리 순회 : 트리 구조의 저장된 모든 노드를 일정한 규칙에 따라 정확히 한번씩 방문하는 과정

순회 방법	순서
전위 순회	부모 > 왼쪽 자식 > 오른쪽 자식
중위 순회	왼쪽 자식 > 부모 > 오른쪽 자식
후위 순회	왼쪽 자식 > 오른쪽 자식 > 부모

(2) 전위 순회 구현

 - 부모 > 왼쪽 자식 > 오른쪽 자식 > 순서로 방문 ( A B D E C F G )

t = [None, 'A', 'B', 'C', 'D', 'E', 'F', 'G'] def preorder(i) :     if i >= len(t) :         return     print(t[i], end = ' ' )     preorder(i*2)     preorder(i*2+1) preorder(1)

 - 가장 먼저 루트 노드 방문, 왼쪽 서브 트리를 모두 방문 후 마지막으로 오른쪽 서브 쿼리 방문

 - 재귀 호출을 이용하여 현재 노드, 왼쪽 자식, 오른쪽 자식 순으로 탐색

(3) 중위 순회 구현

 - 왼쪽 자식 > 부모 > 오른쪽 자식 순서로 방문 ( D B E A F C G )

t = [None, 'A', 'B', 'C', 'D', 'E', 'F', 'G'] def preorder(i) :     if i >= len(t) :         return     preorder(i*2)     print(t[i], end = ' ' )     preorder(i*2+1) preorder(1)

 - 이진 탐색 트리에서 데이터를 오름차순으로 출력할 수 있는 방법

(4) 후위 순회 구현

 - 왼쪽 자식 > 오른쪽 자식 > 부모 순서로 방문 ( D E B F G C A )

t = [None, 'A', 'B', 'C', 'D', 'E', 'F', 'G'] def preorder(i) :     if i >= len(t) :         return     preorder(i*2)     preorder(i*2+1)     print(t[i], end = ' ' ) preorder(1)