[Data Structure / Algorithms] Tree (1)

전성훈·2023년 11월 4일

Algorithms datastructure swift

Data Structure-Algorithm

목록 보기

11/35

주제: Tree구조의 기초

특징

Tree는 높은 중요도를 나타내는 Data Structure이다. Software development의 여러 요소에서 활용되며, 예를들면
- 계층 구조 관계를 대표하는 것.
- 정렬된 데이터를 관리하는 것.
- 작동을 빠르게 확인하는 것. 등이 있다.

용어

Node

Linked List와 같이 trees는 node들로 만들어졌다.
각 각의 노드는 데이터를 갖고 있으며, node의 children를 확인 할 수 있다.

Parent and child

진짜 나무의 뒤집은 모양으로 위에서부터 아래로 퍼져나가는 모습으로 보여진다.
제일 위에 있는 노드를 제외하고는 모든 노드는 위에 하나의 노드와 연결되어 있다. 그 노드들을 child 노드라고 부르며, 모든 child 노드들은 정확히 하나의 parent 노드를 갖고 있다.

Root

가장 높은 위치에 있는 노드를 말하며, 오직 하나만 존재한다.

Leaf

children 노드가 없는 노드들을 말하며, 가장 아래에 존재한다.

구현

public class TreeNode<T> {
	public var value: T
	public var children: [TreeNode] = []
	
	public weak var parent: TreeNode?
	
	public init(_ value: T) { 
		self.value = value
	}
	
	public func add(_ child: TreeNode) { 
		children.append(child)
	}
}

func makeBeverageTree() -> TreeNode<String> {
  let tree = TreeNode("Beverages")

  let hot = TreeNode("hot")
  let cold = TreeNode("cold")

  let tea = TreeNode("tea")
  let coffee = TreeNode("coffee")
  let chocolate = TreeNode("cocoa")

  let blackTea = TreeNode("black")
  let greenTea = TreeNode("green")
  let chaiTea = TreeNode("chai")

  let soda = TreeNode("soda")
  let milk = TreeNode("milk")

  let gingerAle = TreeNode("ginger ale")
  let bitterLemon = TreeNode("bitter lemon")

  tree.add(hot)
  tree.add(cold)

  hot.add(tea)
  hot.add(coffee)
  hot.add(chocolate)

  cold.add(soda)
  cold.add(milk)

  tea.add(blackTea)
  tea.add(greenTea)
  tea.add(chaiTea)

  soda.add(gingerAle)
  soda.add(bitterLemon)

  return tree
}

let tree = makeBeverageTree()

Traversal Algorithms

배열이나 연결 리스트와 같은 선형 컬렉션을 Traversal하는 것은 간단하다. 선형 컬렉션은 명확한 시작과 끝을 가지고 있기 때문이다.
하지만 Tree 구조를 Traversal하는 것은 조금 복잡하다.
왼쪽에 있는 노드가 우선적인가? 노드의 깊이는 우선순위와 어떤 관계를 가지나? 등 노드를 순회하는 전략은 해결하려는 문제에 따라 달라진다.
서로 다른 트리와 문제에 따라 다양한 전략이 있으며, 크게 DFT(Depth-first traversal)깊이 우선 순회, LOT(Level-order traversal) 층별 탐색 등 이 있습니다.

Depth-first traversal

이 기법은 루트에서 시작하여 가능한 한 깊게 들어가서 되돌아올 때까지 노드를 방문하는 것 이다.

extension TreeNode { 
	public func forEachDepthFirst(visit: (TreeNode) -> Void) { 
		 visit(self)
		 children.forEach { 
			 $0.forEachDepthFirst(visit: visit)
		 }
	}
}

Beverages
hot
tea
black
green
chai
coffee
cocoa
cold
soda
ginger ale
bitter lemon
milk

Level-order traversal

재귀 호출 대신 큐를 사용하여 레벨 순서대로 방문하는 것이다. 일반적으로 재귀 호출을 사용하여 깊이 우선 탐색을 수행할 때는, 스택을 사용하여 방문한 노드를 기록하고 백트래킹(Backtracking)을 수행하는데 반해, LOT는 큐를 사용하여 레벨 단위로 방문한 노드를 기록하고 순차적으로 처리한다.

extension TreeNode { 
	public func forEachLevelOrder(visit: (TreeNode) -> Void) { 
		visit(self)
		
		var queue = Queue<TreeNode>()
		children.forEach { queue.enqueue($0) }
		while let node = queue.dequeue() { 
			visit(node)
			node.chlidren.forEach { queue.enqueue($0) }
		}
	}
}

Beverages
hot
cold
tea
coffee
cocoa
soda
milk
black
green
chai
ginger ale
bitter lemon

Search

extension TreeNode where T: Equtable { 
	public func search(_ value: T) -> TreeNode? { 
		var result: TreeNode?
		forEachLevelOrder { node in 
			if node.value == value { 
				return = node
			}
		}
		return result
	}
}

Print Tree

extension TreeNode { 
	public func forEachLevelOrderPrint() { 
		var queue = Queue<TreeNode>() 
		var nodeLeftInCurrentLevel = 0 
		queue.enqueue(self)
		
		while !queue.isEmpty { 
			nodeLeftInCurrentLevel = queue.count
			
			while nodeLeftInCurrentLevel > 0 { 
				guard let node = queue.dequeue() else { break }
				print("\(node.value)", terminator: "")
				node.children.forEach { queue.enqueue($0) }
				nodeLeftInCurrentLevel -= 1 
			}
			print()
		}
	}
}

Beverages 
hot cold 
tea coffee cocoa soda milk 
black green chai ginger ale bitter lemon