[자료구조] Tree - 기초개념

자료구조 05 - 1 / Tree

---

정의 

그래프의 일종으로 최상위 노드 Root Node를 시작으로 노드를 이어가는 자료구조

비순환, 비선형 자료구조로, 계층적관계 (Hierarchical Relationship)를 표현한다.

 

 

트리를 구성하고 있는 구성요소

Root Node : 트리 구조에서 최상위 노드

Node : 트리를 구성하고 있는 각 요소

 

Terminal Node (= Leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드

Edge : 트리를 구성하기 위해 노드와 노드를 연결하는 선

 

Internal Node : 단말 노드를 제외한 모든 노드로 루트 노드 포함

 

Parent Node : 현재 노드의 상위 레벨에 이어진 상위 노드

 

Child Node : 현재 노드의 하위레벨에 이어진 하위 노드

 

 

 

github

GitHub - keeplo/SwiftTools: 자료구조 알고리즘 등 직/간접적으로 사용가능한 예제

구현 

class Node<T: Equatable> {
    var value: T
    var children: [Node] = []
    weak var parent: Node?
    
    init(value: T) {
        self.value = value
    }
    
    func add(child: Node) {
        children.append(child)
        child.parent = self
    }
    
    func search(value: T) -> Node? {
        if value == self.value {	// Equatable
            return self
        }
        
        for child in children {
            if let found = child.search(value: value) {
                return found
            }
        }
        
        return nil
    }
    
    func printValue() {
        print(value)
    }
}

 

부모 노드와 자식노드 형태로 각 노드가 이어지면서 root부터 leaf까지 이어진다.

 

추가적으로 생각해볼 내용

월드컵 본선 대진표, 회사나 학교 등 조직도, 인터넷 상점의 상품 분류 등 계층구조를 가지는 데이터 활용사례
폴더 구조, DBMS, 검색엔진 등 탐색에 용의한 자료구조

 

선형구조의 배열과 연결리스트와 달리 계층과 방향성을 가지고 다양한 데이터를 분류하기 효율적

 

freedompenguin.com / www.co-bw.com

 

Wikipedia
Interview_Question_github
raywenderlich.com
Photo Reference : Personal Blog