Chapter 10: Trees

Tree는 정보를 구성하는 또 다른 방법으로, children과 parents의 개념을 사용한다. 매우 중요한 자료구조로, 소프트웨어 개발의 다양한 측면에서 사용된다.

• 계층적 관계를 나타낸다.
• 정렬된 데이터를 관리한다.
• 빠른 조회 작업을 처리한다.

모양과 크기가 다양한 여러 종류의 Tree가 있다.

 

Terminology

Tree에 관련된 여러가지 용어(Terminology)들이 있다.

 

Node

연결리스트(Linked List)와 마찬가지로, Tree는 Node로 구성된다. 

각 node는 데이터를 가질 수 있으며, 자식(children) node를 추적한다.

 

Parent and child

Tree는 실제 나무처럼 가지를 치는데, 방향은 반대로 위에서 시작해 아래로 뻗어나간다. 모든 node(최상위 root 제외)는 바로 위쪽으로 하나의 node와 연결된다. 이를 부모(parent) node라 한다. 바로 아래에 연결되어 있는 node는 자식(child) node라 한다. Tree에서 모든 child는 정확히 하나의 parent를 가진다.

 

Root

Tree의 최상위 node를 루트(Root)라고 한다. Parent가 없는 유일한 node이다.

 

Leaf

잎(leaf)는 child가 없는 node이다.

 

Implementation

트리(Tree)는 노드(Node)로 구성되어 있으므로, 가장 먼저, TreeNode를 만들어야 한다.

public class TreeNode<T> {
    public var value: T
    public var children: [TreeNode] = []
    
    public init(_ value: T) {
        self.value = value
    }
}

각 node는 value를 가지고 있으며, Array를 사용해 모든 child에 대한 참조를 보유한다. 자식 노드를 추가하는 메서드를 작성한다.

extension TreeNode {
    public func add(_ child: TreeNode) { //child node를 추가한다.
        children.append(child)
    }
}

Tree를 직접 작성해 확인해 본다.

example(of: "creating a tree") {
    let beverages = TreeNode("Beverages")
    
    let hot = TreeNode("Hot")
    let cold = TreeNode("Cold")
    
    beverages.add(hot)
    beverages.add(cold)
}

Tree는 자연스럽게 계층적인 구조를 이룬다. 여기서는 세 개의 서로 다른 node를 정의하고, 논리적인 계층 구조(logical hierarchy)를 구성했다. 

 

Traversal algorithms

배열(Array)이나, 연결 리스트(LinkedList)와 같은 선형(linear) collection은 명확한 시작과 끝이 있으므로 반복하는(Iterating) 것이 간단하다.

하지만 Tree는 non-linear collection이므로 반복하는(Iterating) 것이 쉽지 않다.

어느 node를 먼저 순회할지는 해결하려는 문제에 따라 달라진다. 

 

Depth-first traversal

깊이 우선 순회(depth-first traversal)는 Root에서 시작하여 역추적(backtracking) 전까지 최대한 깊이 탐색을 하는 방법이다.

extension TreeNode {
    public func forEachDepthFirst(visit: (TreeNode) -> Void) {
        visit(self) 
        //클로저 호출 //여기서는 print($0.value) 이므로, self의 value가 출력된다.
        
        children.forEach {
            $0.forEachDepthFirst(visit: visit) //재귀
        }
    }
}

위에서는 재귀로 구현했지만, 대신 Stack을 사용해 구현할 수도 있다. 구현 확인을 위해 예제 트리를 반환하는 함수를 작성한다.

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
}

위 함수는 다음과 같은 트리를 반환한다.

여기에 깊이 우선 순회(depth-first traversal)를 적용한다.

example(of: "depth-first traversal") {
    let tree = makeBeverageTree()
    tree.forEachDepthFirst { print($0.value) }
    // Beverages
    // hot
    // tea
    // black
    // green
    // chai
    // coffee
    // cocoa
    // cold
    // soda
    // ginger ale
    // bitter lemon
    // milk
}

출력은 다음과 같다.

---Example of: depth-first traversal---
Beverages
hot
tea
black
green
chai
coffee
cocoa
cold
soda
ginger ale
bitter lemon
milk

 

Level-order traversal

레벨 순서 순회(Level-order traversal)는 node의 깊이(depth)를 기준으로 각 node를 순회한다.

extension TreeNode {
    public func forEachLevelOrder(visit: (TreeNode) -> Void) {
        visit(self) //클로저 호출 //여기서는 print($0.value) 이므로, self의 value가 출력된다.
        
        var queue = Queue<TreeNode>() //Queue를 사용해, Level 순서대로 순회한다.
        children.forEach { queue.enqueue($0) } 
        //해당 node의 child를 먼저 Queue에 삽입 한다.
        
        while let node = queue.dequeue() {
            visit(node) //클로저 호출 //여기서는 print($0.value) 이므로, node의 value가 출력된다.
            node.children.forEach { queue.enqueue($0) } 
            //순회 하면서 node의 child가 계속해서 Queue에 삽입 된다.
        }
    }
}

forEachLevelOrder는 각 node를 level 순서 대로 순회한다.

Stack을 사용하는 단순한 재귀는 효과가 없다. 구현을 확인해 본다.

example(of: "level-order traversal") {
    let tree = makeBeverageTree()
    tree.forEachLevelOrder { print($0.value) }
    // Beverages
    // hot
    // cold
    // tea
    // coffee
    // cocoa
    // soda
    // milk
    // black
    // green
    // chai
    // ginger ale
    // bitter lemon
}

출력은 다음과 같다.

---Example of: level-order traversal---
Beverages
hot
cold
tea
coffee
cocoa
soda
milk
black
green
chai
ginger ale
bitter lemon

 

Search

node를 순회하는 메서드를 사용해, 검색(Search) 알고리즘을 쉽게 구현할 수 있다.

extension TreeNode where T: Equatable { 
    //T가 Equatable를 구현해야 한다.
    public func search(_ value: T) -> TreeNode? {
        var result: TreeNode?
        
        forEachLevelOrder { node in //level 우선 방식으로 Search를 구현한다.
            if node.value == value {
                result = node
            }
        }
        return result
    }
}

구현을 확인한다.

example(of: "searching for a node") {
    let tree = makeBeverageTree()
    
    if let searchResult1 = tree.search("ginger ale") {
        print("Found node: \(searchResult1.value)")
    }
    
    if let searchResult2 = tree.search("WKD Blue") {
        print(searchResult2.value)
    } else {
        print("Couldn't find WKD Blue")
    }
    
    // Found node: ginger ale
    // Couldn't find WKD Blue
}

출력은 다음과 같다.

---Example of: searching for a node---
Found node: ginger ale
Couldn't find WKD Blue

여기에서는 레벨 순서 순회(Level-order traversal) 알고리즘을 사용했다. 모든 node를 순회하므로, 중복되는 값이 있다면, 마지막에 찾은 node가 반환된다. 즉, 어떤 순회 방법을 사용하느냐에 따라 다른 객체를 얻게 될 수 있다.

 

Key points

• 트리(Tree)는 연결 리스트(Linked List)와 유사한 점이 많다. 그러나 연결 리스트의 노드(node)는 하나의 후속(successor) 노드만 연결하지만, 트리 노드는 다수의 하위 노드를 연결 할 수 있다.
• root 노드를 제외한, 모든 트리 노드는 정확히 하나의 상위(parent) 노드가 있다.
• root 노드는 상위(parent) 노드가 없다.
• 잎(leaf) 노드는 하위(child) 노드가 없다.
• parent, child, leaf, root과 같은 트리 용어(terminology)에 익숙해져야 한다. 이 용어들은 공통적이므로 다른 tree 구조를 설명하는 데 사용된다.
• 깊이 우선 순회(depth-first traversal)와 레벨 순서 순회(level-order traversal) 같은 순회 알고리즘은 일반 tree에 국한되지 않는다. 다른 tree에서도 같은 방식으로 작동하지만, 구조에 따라 구현 방식이 약간씩 다를 수 있다.