일러두기
# 선형구조에서는 데이터를 저장하고 꺼내는 것이 중요한 작업이었지만 비선형구조에서는 저장된 데이터가 그 구조로 잘 표현되어 있는지가 더 중요하다.
# 즉, 삽입과 삭제는 데이터의 표현을 위해 기본적으로 제공되는 것이고, 목적에 맞는 검색과 순회가 가능한지가 더 중요하다.
트리의 구현
# 저장과 삭제가 빈번하게 이루어져야 한다면 트리를 배열을 기반으로 구현하는 것은 비효율적이다.
# 하지만 데이터의 구조가 완전이진트리라면 배열로 구현하는 것이 검색과 순회에 있어서 더 효율적일 수 있다.
# 그리고 이러한 구조의 완전이진트리는 다음에 소개할 힙에 활용된다.
배열로 구현한 완전 이진트리의 특징
# 뿌리 노드의 인덱스가 0일 경우
1) 인덱스 [K]에 있는 노드의 왼쪽 자식은 인덱스 [2*K+1]에 오른쪽 자식은 인덱스 [2*K+2]에 있다.
2) 인덱스 [K]에 있는 노드의 부모 노드는 인덱스 ((K-1)/2)에 있다.
# 뿌리 노드의 인덱스가 1일 경우
1) 인덱스 [K]에 있는 노드의 왼쪽 자식은 [2K]에 오른쪽 자식은 오른쪽 자식은 인덱스 [2K+1]에 있다.
2) 인덱스 [K]에 있는 노드의 부모노드는 [K/2]에 있다.
# 편한거 쓰면 되는데 인덱스를 1부터 시작하는 것을 더 많이 쓴다고 한다.
트리의 운행법
# 일반적인 트리의 운행법은 레벨 순서 운행법(상향식, 하향식), 족보 순서 운행법, 전위, 중위, 후위 운행법 등이 있다.
# 아래에서 검사한다는 것은 노드의 데이터를 읽어온다는 것을 뜻한다.
#레벨 순서 운행법(하향식)은 넓이 우선 탐색으로 가장 낮은 레벨의 모든 노드를 왼쪽에서 오른쪽 순서로 검사하고 그 다음 레벨의 모든 노드를 검사하는 방식이다.
#상향식은 가장 높은 레벨부터 시작한다.
ex) 하향식 : [1], [2]. [3], ... [9], [10], [11] / 상향식 : [8], [9], [10] ... [2], [3], [1]
# 족보 순서 운행법은 뿌리 노드를 검사하고, 뿌리 노드의 자식 노드를 검사하고, 가장 늦게 검사된 자식 노드부터 앞의 작업을 반복하는 방식이다.
ex) [1], [2], [3], [6], [7], [12], [4], [5], [10], [11], [8], [9]
# 딱히 잘 쓰이는 운행법은 아닌듯 하여 구현은 하지 않았다. (필요할 때 하면 되지 뭐...)
# 전위, 중위, 후위 운행법은 뿌리 노드를 언제 검사하는가에 따른 분류이다.
# 전위 운행법은 뿌리 노드를 먼저 검사하고, 뿌리 노드의 왼쪽 부트리와 오른쪽 부트리를 검사하는 방식이다.
# 중위 운행법은 왼쪽 부트리를 검사하고 뿌리 노드를 검사하고, 오른쪽 부트리를 검사하는 방식이다.
# 후위 운행법은 왼쪽 부트리를 검사하고, 오른쪽 부트리를 검사하고 뿌리 노드를 검사하는 방식이다.
# 이 때 각 부트리에서는 위의 순서로 모든 노드를 재귀적으로 검사한다.