[Data Structure] Tree(1)

"트리"(Tree) ADT는 계층 구조를 가지는 그래프의 일종으로 비선형 자료구조이다. 

그래프의 일종이기 때문에, 노드와 간선으로 이루어져 있다.

이때, 각 노드는 하나의 부모 노드만을 가지며, 여러 개의 자식 노드를 가질 수 있다.

이러한 계층 구조에 의해 트리에서는 절대로 순환이 발생하지 않는다.

 

즉, 트리는 각 노드를 한 번씩만 방문했을 때, 절대 순환이 발생하지 않는 연결 그래프이다. 

 

이렇게 최상위의 노드를 루트노드라 부르며, 모든 트리에는 항상 하나만 존재한다. 

또한, 트리 구조는 각 노드를 루트 노드로 하여 하위트리로 분류할 수 있으며, 이러한 특성에 의해 재귀적 자료구조라고도 부른다. 

 

• 루트 노드(root) : 모든 트리에 하나만 존재하며, 부모가 없는 최상위 노드 
• 리프(단말) 노드(leaf) : 자식이 없는 노드
• 내부(비단말) 노드(internal) : 자식이 있는 노드 (리프 노드가 아닌 노드)
• 형제 노드(sibiling) : 부모가 같은 노드
• 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 수
• 노드의 깊이(depth) :  루프에서 해당 노드까지 도달하기 위한 간선의 수
• 노드의 레벨(level) : 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree) : 하위 트리 개수 / 간선의 수 (ex. A노드의 경우 2, E노드의 경우 1)
• 트리의 차수(degree) :  트리의 최대 차수
• 트리의 높이(height) : 루프 노드 기준으로 가장 깊숙이 있는 노드의 깊이(depth)

 

트리의 종류 

이진 트리

"이진트리"란 각 노드가 최대 2개의 자식을 갖는 트리를 말한다. 

이러한 이진트리는 특성에 따라 여러개로 분류된다. 

• 정 이진 트리 : 모든 노드의 자식 노드가 0개 혹은 2개로만 구성된 이진 트리 
• 완전 이진 트리 : 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 경우 왼쪽서부터 순차적으로 채워져 있는 트리
• 변질 이진 트리 : 자식 노드가 하나밖에 없는 트리
• 포화 이진 트리 : 모든 노드가 꽉 차 있는 이진 트리 
• 균형 이진 트리 : 왼쪽과 오른쪽 서브 트리의 높이차가 1 이하인 이진 트리

 

힙

"힙" 자료구조는 완전 이진트리의 일종으로, 

우선순위에 대한 규칙을 기반으로 부모 자식 관계를 형성한다. 

 

"최대 힙"(max heap)은 부모 노드의 키 값이 자식의 키값보다 큰 완전 이진트리를 말하며, 

"최소 힙"(min heap)은 부모 노드의 키 값이 자식의 키값보다 작은 완전 이진트리를 말한다. 

 

힙 자료구조는 우선순위 큐를 구현할 때 사용하며, 자세한 내용은 해당 포스팅을 참고 바란다. 

https://seokyoungg.tistory.com/91#2.%20Heap%C2%A0

[Data Structure] Priority Queue

 

이진 탐색 트리 

"이진 탐색 트리"는 다음과 같은 특징을 만족하는 이진트리로, 주로 탐색에 사용된다. 

• 노드의 왼쪽 서브트리는 그 노드의 값보다 작은 값들을 가진 노드들로 이루어져 있다. 
• 노드의 오른쪽 서브트리는 그 노드의 값보다 큰 값들을 가진 노드들로 이루어져 있다. 
• 좌우 서브트리는 각각 위의 2 조건을 만족한다. 

 

하지만, 삽입을 반복하다 보면 다음과 같은 편향 트리가 될 수 있는데, 이는 탐색 시간을 $O(logN)$이 아닌 $O(N)$이 되게 된다. 

 

이를 방지하기 위해 항상 좌우 높이차가 1인 균형 이진트리가 되도록 보장하는 
이진 검색 트리에는 AVL트리, Red-Black 트리가 있다. 

 

스패닝 트리 

"스패닝 트리"란 그래프 내의 모든 정점을 포함하지만 사이클이 없는 트리를 의미한다. 

즉, 그래프 내의 모든 정점을 포함하되 사이클이 발생해선 안된다. 

만약 가중치가 존재하는 그래프의 경우, 가중치의 합이 최소인 스패닝 트리를 "최소 스패닝 트리" (MST \ Minimum Spanning Tree)라 부른다. 

이러한 MST를 생성하는 알고리즘으로는 크루스칼, 프림 알고리즘이 대표적이다. 

 

 

이는 loop 구조를 가지는 네트워크에서 브로드캐스트가 계속 발생하는 것을 억제할 때 사용된다. 즉, 네트워크 내의 사이클을 없앨 때 사용된다. 

 

 

구현 

트리의 경우는 다음과 같이 리스트를 활용한다. 

public class TreeNode<T> {
  public var value: T 

  public weak var parent: TreeNode? 
  public var children = [TreeNode<T>]()

  public init(value: T) {
    self.value = value
  }

  public func addChild(_ node: TreeNode<T>) { 
    children.append(node) 
    node.parent = self 
  }
}

 

하지만, 이진트리의 경우 이전 Heap 구현 포스팅에서 살펴보았듯이, 리스트가 아닌 배열을 통해서도 표현이 가능하다. 

 

 

References 

위키 백과

• Tree (data structure)

https://www.kodeco.com/1053-swift-algorithm-club-swift-tree-data-structure