옆집 스위프트: 1-5) 데이터 구조 - 트리(Tree)

오늘은 트리~

 

5. 트리(Tree)

• 트리에 대하여
  • 트리는 파일 시스템, 계층적 데이터 및 검색 알고리즘과 같은 다양한 응용 프로그램에서 사용되는 기본 데이터 구조이다.
  • 트리는 간선으로 연결된 노드로 구성된 계층적 데이터 구조이다.
  • 트리의 각 노드는 0개 이상의 자식 노드를 가질 수 있다.
  • 트리의 노드는 루트에서 트리의 다른 모든 노드로 가는 경로가 있도록 구성된다.
  • 트리의 유형
    • 이진 트리: 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리의 일종으로, 일반적으로 왼쪽 자식과 오른쪽 자식으로 불린다. 단순성과 구현의 용이성을 가지고 있다.
    • 이진 탐색 트리(BST): 왼쪽 자식의 값이 부모 노드보다 작고, 오른쪽 자식의 값이 부모 노드보다 큰 이진 트리이다. 이 속성 덕분에 효율적인 검색, 삽입 및 삭제 작업이 가능하다.
    • AVL 트리: 어떤 노드의 왼쪽 및 오른쪽 서브트리의 높이가 최대 1만큼 차이나는 자기 균형 이진 탐색 트리이다. 이 자기 균형 속성은 균형을 유지하게 하여 작업의 성능을 향상 시킨다.
  • 트리에 대한 일반적인 작업
    • • 너비 우선 탐색(BFS): Breadth-First Search, 루트 노드로부터 시작하여 레벨별로 노드를 방문한다. 이 순회 전략은 검색 작업이 루트 근처에서 해결책을 찾을 가능성이 높을때 유용하다. 큐(queue)를 사용한다.
      • 깊이 우선 탐색(DFS): Depth-First Search, 루트 노드로부터 시작하여 가능한 한 각 가지를 깊이 탐색하다가 다시 돌아온다. 이 순회 전략은 검색 작업이 트리의 깊은 레벨에서 해결책을 찾을 가능성이 높을 때 유용하다. 스택(stack)을 사용한다.트리 순회: 트리의 각 노드를 정확히 한번 방문하는것을 말한다.
    • 노드 삽입: 노드를 삽입하려면 특정 규칙이나 트리 타입의 속성을 따라 적절한 위치를 찾아야 한다. 예를 들어 이진 탐색 트리에서는 특정 노드의 왼쪽 자식 또는 오른쪽 자식으로 삽입되어야 하는지를 결정하는 것이 포함된다.
    • 노드 삭제: 노드를 삭제하는것은 삭제할 노드를 찾아 그에 따라 트리 구조를 재배치 하는것이 포함된다. 삭제 과정은 트리의 타입 및 속성에 따라 다르다.

1)BFS / 2)DFS 방문 순서 순회 예시

// Swift에서 구현하는 Binary Tree!

// Tree 노드를 클래스로 
class BinaryTreeNode<T> {
	var value: T
	var leftChild: BinaryTreeNode?
	var rightChild: BinaryTreeNode?
	
	init(_ value: T) {
		self.value = value
		self.leftChild = nil
		self.rightChild = nil
	}
}

// 중위 노드 탐색
func inorderTraversal<T>(_ node: BinaryTreeNode<T>?) {
	guard let node = node else {
		return
	}
	
	inorderTraversal(node.leftChild)
	print(node.value)
	inorderTraversal(node.rightChild)
}
// 전위 노드 탐색
func preorderTraversal<T>(_ node: BinaryTreeNode<T>?) {
	guard let node = node else {
		return
	}
	
	print(node.value)
	preorderTraversal(node.leftChild)
	preorderTraversal(node.rightChild)
}
// 후위 노드 탐색
func postorderTraversal<T>(_ node: BinaryTreeNode<T>?) {
	guard let node = node else {
		return
	}
	
	postorderTraversal(node.leftChild)
	postorderTraversal(node.rightChild)
	print(node.value)
}

// 위 클래스를 이용하여 이진트리를 구성
// 일단 노드 초기화
let rootNode = BinaryTreeNode(10)
let leftChild = BinaryTreeNode(5)
let rightChild = BinaryTreeNode(15)

// leftChild와 rightChild 노드를 rootNode에 연결
rootNode.leftChild = leftChild
rootNode.rightChild = rightChild

print("Inorder traversal: ")
inorderTraversal(rootNode)
print("Preorder traversal: ")
preorderTraversal(rootNode)
print("Postorder traversal: ")
postorderTraversal(rootNode)
/* 
실행결과: 
Inorder traversal: 
5
10
15
Preorder traversal: 
10
5
15
Postorder traversal: 
5
15
10
*/