트리
계층적인 자료의 표현에 적합한 자료구조이다
ex) 회사 조직도, 컴퓨터 폴더구조, 의사결정트리
용어
-
노드 : 하나의 데이터를 표현하는 점
-
간선 : edge, link :: 노드 사이를 잇는 선, 관계
-
루트 노드 : 트리의 최상단에 위치한 단 하나의 노드
-
부모 노드 : 루트 노드를 제외한 모든 노드는 단 하나의 부모 노드를 가진다, 부모는 여러개의 자식노드를 가질 수 있다.
-
자식 노드 : 모든 노드는 자식노드를 가질 수 있다, 자식 노드는 단 하나의 부모노드를 가진다.
-
형제 노드 : sibling :: 같은 부모노드를 가지는 (= 같은 레벨에 위치한) 모든 노드를 가리킴
-
조상 노드 : 부모 노드를 포함해 계층적으로 현재 노드보다 상위에 존재하는 모든 노드를 가리킴
-
자손 노드 : 자식 노드를 포함해 현재 노드보다 계층적 하위에 있는 모든 노드를 가리킨다.
-
Leaf 노드 : 단말노드, Terminal node :: 자식을 가지지 않는 노드, 노드 차수가 0이다.
-
Branch 노드 : 비단말 노드, Internal node(내부 노드) :: 차수가 0이 아닌 노드, 자식을 가진 노드
-
노드의 차수 Degree :: 노드에 직접 연결된 관계(edge)의 수,
-
트리의 차수 : 트리가 가진 모든 노드 중 최대 degree의 값
-
레벨 : 루트노드를 기준으로 노드가 위치한 깊이
-
트리의 높이 : 루트 노드로부터 가장 깊숙히 들어간 노드의 깊이, 최대 레벨
-
포레스트
일반 트리의 표현법
- 배열을 이용 : 비효율적
- Linked List : 비효율적
이진 트리 : Binary Tree
모든 노드가 2개의 서브트리를 갖는다.
- 서브트리는 공집합일 수 있다.
- 루트와 왼쪽 소브트리, 오른쪽 서브 트리로 구성된 노드들의 집합.
- 이진트리는 순환적으로 정의하며, 이진트리의 서브 트리들도 모드 이진트리이다.
- 자연히 모든 노드의 차수는 2 이하이다.이진트리의 분류(상태)
- 포화 이진트리 ( Perfect Binary Tree )
- 트리의 각 레벨에 공집합 없이 노드가 꽉 차있는 트리
- 완전 이진 트리 ( Complete binary Tree )
- 높이가 h인 트리일 때, 레벨 1부터 h-1(최대 직전 레벨)까지는 노드가 모두 채워짐- 마지막 레벨인 h에서는 노드가 순서대로 채워져 있으나 꽉 차있지는 않은 상태
- 기타 이진 트리
- 꽉차있지 않다, 순서대로 채워져 있지 않아 지나온 노드에 공집합이 존재한다.
이진트리의 성질
Node수로 Edge수 구하기
노드 수 : N
-> 엣지 수 : N-1
트리 높이가 h
-> 최소 노드 수 : h
-> 최대 노드 수 : 2^h -1
노드 수 n
-> 최소 트리 높이 : log(n+1)
-> 최대 트리 높이 : n
n개의 각 노드를 편향 이진트리로 일렬로 늘어놓을 경우 최대높이인 n,
n개의 노드를 루트부터 빼곡히 채워 완전이진트리로 만들 경우 최소높이인 log(n+1)이진트리의 표현법
배열을 이용한 표현
- 노드 i의 부모 노드 인덱스 = i/2
- 노드 i의 왼쪽 자식 노드 인덱스 = 2i
- 노드 i의 오른쪽 자식 노드 인덱스 = 2i + 1 - 구현이 간단
- 빈칸이 발생할 수 있음 -> 비효율
- 배열의 메모리 사전할당으로 인한 높이 제한 -> 비효율링크 표현법
class TreeNode :
def __init__ (self, data, left, right) :
self.data = data # 현재 노드의 데이터
self.left = left # 왼쪽 서브트리 로의 링크
self.right = right # 오른쪽 서브트리로의 링크 - 구현이 복잡
- 메모리 낭비가 없다
- 이진트리의 구조와 직관적으로 동일한 구현 가능이진트리의 순회 (Traversal)
순회(Traversal) : 트리에 속하는 모든 노드를 한번씩 방문 하는 것
- 선형 자료구조는 순회 방법이 단순하다.
- 트리는 다양한 순회 방법이 있다.TIP!!) 전/중/후 순회는 print() 위치와 재귀적 실행을 파악하면 정확한 이해 가능
1. 전위 순회 (Pre-order traversal : VLR)
활용 예 : 노드의 레벨 계산, 구조화된 문서 출략
현재 노드 출력이 코드의 전위에 오는 것 : LEFT탐색,RIGHT탐색으로 인한 재귀스택이 쌓이는 것 보다 앞선다는 것에 주목
def preorder(n) : #n은 현재 노드
if n is not None : # n이 LEAF노드일 경우 함수 종료
print(n.data, end=' ') #출력 위치: 전위
preorder(n.lett) #왼쪽 서브트리 탐색 시작
preorder(n.right) #오른쪽 서브트리 탐색 시작2. 중위 순회 (In-order traversal : LVR)
활용 예 : 정렬
현재 노드 출력이 코드의 중위에 오는 것 : LEFT탐색 직후에 수행되므로, RIGHT탐색으로 인한 재귀스택이 쌓이는 것 보다 앞선다는 것에 주목
def inorder(n) :
if n is not None :
inorder(n.left)
print(n.data, end=' ') # print를 left 서브트리 탐색 종료 이후 실행
inorder(n.right)3. 후위 순회 (Post-order traversal : LRV)
활용 예 : 폴더 용량 계산 - 하위 폴더 용량이 계산되어야 현재 폴더용량 계산가능
현재 노드 출력이 코드의 후위에 오는 것 : LEFT탐색,RIGHT탐색이 모두 끝난 이후 print가 수행되므로, 내부의 모든 재귀가 끝난 이후 현재 노드를 출력 한다는 점에 주목
def postorder(n) :
if n is not None :
postorder(n.left)
postorder(n.right)
print(n.data) # 후위 출력 : 모든 서브트리 탐색 끝낸 이후 현재노드 출력4. 레벨 순회
노드를 레벨 순으로 검사하는 순회 방법
큐를 사용해 구현
루트부터 왼->오 순으로, 큐에서 노드를 하나 꺼내 방문하고 그 자식들을 큐에 삽입한다.def levelorder(root) :
queue = CircularQueue() # 큐 객체 초기화
queue.enqueue(root) # 최초 큐에는 루트 노드만 삽입
#규칙1
while not queue.isEmpty() : # 큐가 공백상태가 아닌 동안 반복
n = queue.dequeue() # 큐에서 맨 앞의 노드 n을 꺼낸다
#규칙2
if n is not None :
print(n.data, end=' ') # 먼저 꺼낸 n의 데이터 출력
queue.enqueue(n.left) # n의 왼쪽 자식 노드를 큐에 삽입
queue.enqueue(n.right) # n의 오른쪽 자식 노드를 큐에 삽입
이진트리 연산
이진트리의 노드 개수 연산
# 순환을 이용해 트리의 노드 수를 계산하는 함수
def count_node(n) :
# 순환 중, leafNode일 경우 종료
if n is None :
return 0
# 좌우 서브트리의 노드 수의 합 + 1을 반환 (순환 응용), +1은 루트노드 포함을 위해
else :
return 1 + count_node(n.left) + count_node(n.right)이진트리의 Leaf Node 수 연산
def count_leaf(n) :
# 공백트리 -> 0 반환
if n is None :
return 0
# leaf노드 -> 1 반환
elif n.left in None and n.right is None :
return 1
# branch노드 -> 좌우 서브트리 결과 합 반환 ( 순환 응용 )
else :
return count_leaf(n.left) + count_leaf(n.right)이진트리의 높이 연산
def calc_height(n) :
if n in None : # 공백트리 -> 0 반환
return 0
hLeft = calc_height(n.left) # 왼쪽 트리 높이 연산 (순환)
hRight = calc_height(n.right) # 오른쪽 트리 높이 연산 (순환)
# 왼쪽, 오른쪽 중 더 높은 트리 높이에 1을 더해 반환 : 1은 루트노드 높이 고려한 덧셈
if(hLeft > hRight) :
return hLeft + 1
else :
return hRight + 1