[자료구조] 트리란 (Swift)

트리 자료구조의 개념

 

 

출처 https://yoongrammer.tistory.com/68

 

 

트리 자료구조란 위의 사진처럼 노드(Node)들이 나무 가지처럼 연결된 계층적 자료구조입니다.

트리는 노드들과 노드들을 연결하는 간선(edge)들로 구성되어 있습니다.

루트 노드는 0개 이상의 자식 노드를 가지고 있으며 그 자식 노드 또한 0개 이상의 자식노드를 갖고있으며 이것이 반복된 것이 트리 자료구조 입니다.

트리는 사이클이 존재할 수 없으며 사이클이 존재하는 그래프와 다르다는 것이 큰 특징입니다.

 

 

트리 구현

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

class Tree<T> {
    var root: TreeNode<T>?
    
    init(rootValue: T) {
        root = TreeNode(value: rootValue)
    }
}

 

트리 만들기

let tree = Tree<String>(rootValue: "A")

let nodeB = TreeNode(value: "B")
let nodeC = TreeNode(value: "C")
let nodeD = TreeNode(value: "D")

tree.root?.addChild(nodeB)
tree.root?.addChild(nodeC)
nodeB.addChild(nodeD)

 

루트 노드를 "A" 로 지정후 루트 노드에 자식 "B" , "C"를 추가합니다. 그후 "B"의 노드에 자식 "D"를 추가하면 위의 그림처럼 트리가 구성이 됩니다.

 

왜 사용해야할까 or 나만의 고민

계층적 자료구조이기 때문에 우선순위를 고려한 데이터인경우 매우 효과적임(최대/최소 힙 구조 , 우선순위 큐)

트리가 이진트리 + 편중된 트리구조가 아닌 경우 데이터를 탐색하는데 O(logN) 시간 소요  vs  Linked List 는 O(N)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

참조)

https://conandevdaily.tistory.com/32