Tree
Tree란?
트리는 비선형적이며 계층 구조를 갖는 자료구조입니다. 트리는 데이터를 담는 노드와 노드들을 연결하는 간선으로 구성되며 노드들은 다른 노드들과 부모-자식 관계를 갖습니다.
용어
- 루트 노드(Root node): 부모가 없는 최상위 노드로, 트리에서 하나만 존재하고 트리의 Access Point입니다.
- 내부 노드(Internal node): 적어도 하나 이상의 자식 노드를 갖는 노드를 말합니다.
- 외부 노드(External node): 자식 노드가 없는 노드를 말하며 Leaf node라고도 합니다.
- 조상 노드(Ancestor node): 노드 X 가 개념적으로 노드 Y 의 조상이라면 노드 X 를 노드 Y 의 조상 노드라고 합니다.
- 후손 노드(Descendant): 노드 X 가 개념적으로 노드 Y 의 후손이라면 노드 X 를 노드 Y 의 후손 노드라고 합니다.
- 형제 노드(Sibling): 동일한 부모를 갖는 노드들을 형제 노드라고 합니다.
- 노드의 차수(Degree): 노드 X 의 서브 트리 수를 노드 X 의 차수라고 합니다.
- 노드의 깊이(Depth): 루트 노드에서 해당 노드까지의 경로에서 거쳐가는 노드의 수를 말합니다.
- 노드의 레벨(Level): 같은 깊이를 가지는 노드 집합을 말합니다.
- 트리의 높이(Height): 모든 노드의 깊이 중 최댓값을 트리의 높이라고 합니다.
트리의 성질
- 트리는 그래프의 한 종류로 Cycle이 없는 Connected Graph 혹은 DAG(Directed Acyclic Graph)입니다.
- 트리 속 임의의 두 노드 사이의 경로는 오직 하나만 존재합니다.
- 트리 속 노드의 개수가 N개라면 트리 속 간선의 개수는 항상 N - 1개입니다.
트리 순회
트리의 순회란 루트 노드부터 시작하여 트리의 모든 노드를 한 번씩 방문하는 것을 말합니다.
Pre-Order Traversal (전위 순회)
- A -> B -> D -> E -> H -> I -> C -> F -> G -> J -> K -> L
- 현재 노드를 방문
- 현재 노드의 서브 트리들에 대해 전위 순회
Post-Order Traversal (후위 순회)
- D -> H -> I -> E -> B -> F -> J -> K -> L -> G -> C -> A
- 현재 노드의 서브 트리에 대해 후위 순회
- 현재 노드를 방문
Binary Tree
Binary Tree란?
이진 트리는 각 노드가 최대 두개의 자식 노드만 가질 수 있는 트리입니다. 이에 이진 트리에서 각 노드의 자식 노드는 Left Child node와 Right Child node로 구분합니다.
이진 트리 구현
배열을 이용한 구현
- 1차원 배열을 이용
- 루트 노드는 배열의 1번 인덱스에 저장
- 나머지 노드들은 부모 노드의 인덱스를 i 라고 할 때, 왼쪽 자식인 경우엔 2 x i 에 저장하고 오른쪽 자식인 경우엔 2 x i + 1 에 저장
- Complete Binary Tree가 아닌 경우 메모리가 낭비됨
리스트를 이용한 구현
- 각 노드는 데이터와 왼쪽 자식 노드를 가리키는 포인터, 오른쪽 자식 노드를 가리키는 포인터로 구성됨
- 추가적으로 부모 노드를 가리키는 포인터를 가지게 할 수 있음
이진 트리 순회
Pre-Order Traversal (전위 순회)
- A -> B -> D -> E -> H -> I -> C -> F -> G -> J
- 현재 노드를 방문
- 현재 노드의 왼쪽 서브 트리에 대해 전위 순회
- 현재 노드의 오른쪽 서브 트리에 대해 전위 순회
Post-Order Traversal (후위 순회)
- D -> H -> I -> E -> B -> F -> J -> G -> C -> A
- 현재 노드의 왼쪽 서브 트리에 대해 후위 순회
- 현재 노드의 오른쪽 서브 트리에 대해 후위 순회
- 현재 노드를 방문
In-Order Traversal (중위 순회)
- D -> B -> H -> E -> I -> A -> F -> C -> J -> G
- 현재 노드의 왼쪽 서브 트리에 대해 중위 순회
- 현재 노드를 방문
- 현재 노드의 오른쪽 서브 트리에 대해 중위 순회
이진 트리 종류
Proper Binary Tree (Full Binary Tree)
Proper Binary Tree는 트리의 모든 노드가 0개 혹은 2개의 자식을 갖는 이진 트리입니다.
Complete Binary Tree
Complete Binary Tree는 마지막 레벨을 제외한 모든 레벨에 존재할 수 있는 모든 노드를 갖고 있는 이진 트리입니다. Complete Binary Tree의 마지막 레벨은 왼쪽에서부터 오른쪽으로 채워져야 합니다.
Perfect Binary Tree
Perfect Binary Tree는 모든 레벨에 존재할 수 있는 모든 노드를 갖고 있는 이진 트리입니다. 모든 Internal node 는 2개의 자식 노드를 가지며 모든 Leaf node 는 동일한 깊이를 갖습니다.
Heap
Heap이란?
힙은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 (혹은 작은) Complete Binary Tree입니다. 힙은 최대값이나 최소값을 빠르게 찾아내도록 만들졌으며 Priority Queue를 구현하는데 사용됩니다. 또한 중복된 값을 허용하며 일반적으로 배열로 구현됩니다.
Operation
탐색
힙의 탐색 연산은 루트 노드를 반환하는 것이며 O(1) 의 시간복잡도를 갖습니다.
삽입
힙의 삽입 연산은 힙의 마지막 노드 다음에 새로운 노드를 삽입하고 Up Heap하는 것입니다. Up Heap이란 힙의 성질을 만족시킬 때까지 삽입된 노드를 부모 노드와 교환하는 과정을 말합니다.
Up Heap을 할 때 삽입된 노드가 최대 루트 노드 까지 올라갈 수 있으므로 힙의 삽입 연산은 O(log n) 의 시간복잡도를 갖습니다.
삭제
힙의 삭제 연산은 힙의 마지막 노드를 루트 노드에 덮어쓰고 기존 위치의 노드는 삭제한 뒤 Down Heap하는 것입니다. Down Heap이란 힙의 성질을 만족시킬 때까지 루트 노드로 올라간 노드를 자식 노드와 교환하는 과정을 말합니다.
Down Heap을 할 때 자식 노드 중 더 큰 값과 교환을 진행하며 최대 Leaf node 까지 내려갈 수 있으므로 힙의 삭제 연산은 O(log n) 의 시간복잡도를 갖습니다.
