Tree

- 객체간의 계층적인 관계를 나타낸다
- 빠르고 효율적으로 탐색할 수 있다
- 데이터의 정렬된 형태를 보여준다
- 사이클이 없는 그래프
- 텍스트의 prefix 매칭을 빠르게 할 수 있다.

ex)
   - 회사나 정부의 조직 구조
   - 나라, 지방, 시•군별 등 계층적인 데이터
   - 인덱스

 

오늘은 기본적이지만 아주 중요한 Tree에 대해 알아보겠습니다.
Tree 자체보다도 여기서 파생된 트리들이 더 중요하지만 그래도 기본부터 정리해보려고 해요 :)

자료구조란 데이터들을 잘 관리하게 생겨났을텐데요, 트리는 왜, 언제 필요할까요?

트리는 계층적인 관계를 나타내기 위해 사용합니다. 계층 관계는 우리 일상 생활과 아주 많이 밀접해있습니다. 먼저 우리 가족의 관계도를 그려본다고 생각해봅시다. 부모님 형제 자매가 있고, 다시 부모님의 형제 자매, 자식들이 있죠. 쭉쭉쭉 타고 올라가다보면 언젠가 처음의 조상님이 있겠죠? 물론 인간의 기원은 좀 복잡하긴 하지만.. 아무튼 처음의 시작부터 그 밑으로 파생된 관계를 나타낼 때 적합합니다.

네 그냥 그림보면 한 방이에요. 

출처: https://www.raywenderlich.com/1053-swift-algorithm-club-swift-tree-data-structure

 

왜 필요한지는 더 말씀드릴 필요가 없을 것 같고, 몇몇 특징들만 기억합시다. 

- 하나의 루트 노드를 갖는다. (루트를 제외한 각 노드는 하나의 부모 노드를 갖는다.)
- 0개 이상의 자식 노드를 갖는다.

트리도 노드와 선이 있는, 사이클이 없는 하나의 그래프 입니다. 나타낼 데이터를 노드(Node) 라고 부르구요. 노드는 부모는 오직 하나만 가질 수 있어서 두 노드 사이의 선은 최대 하나밖에 올 수 없습니다.

 

기본 용어 정리

기본적으로 부르는 용어도 한번 정리해볼까요? 그냥 보시면 아~ 할 수 있는 내용들이실거에요.

- 노드의 차수(degree) : 노드의 부속 트리의 개수

- 트리의 차수(degree of tree) : 트리의 최대 차수

- 맆(leaf, 단말, terminal) 노드: 차수가 0인 노드, 즉 맨 끝에 달린 노드들이다.

- 내부(internal, non-terminal) 노드 : 차수가 1 이상인 노드

- 부모(parent) : 부속 트리(subtree)를 가진 노드 - 자식(child) : 부모에 속하는 부속노드

- 형제(sibling) : 부모가 같은 자식 노드들

- 조상(ancestor) : 노드의 부모 노드들의 총 집합

- 자손(descendant) : 노드의 부속 트리에 있는 모든 노드들 -

레벨(level) : 루트 노드들로부터 깊이(루트 노드의 레벨 = 1)

- 트리의 깊이(depth of tree) : 트리에 속한 노드의 최대 레벨

 

구현

기본적인 트리는 구현도 어렵지 않게 할 수 있습니다. 

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

extension Node where T: Equatable {
    func search(_ value: T) -> Node? {
        guard self.value != value else { return self }
        for child in children {
            guard let found = child.search(value) else { continue }
            return found
        }
        return nil
    }
}

 

 

너무 간단해서 막상 트리가 뭐죠? 왜 쓰죠? 에 대한 고민을 해보지 않았던 것 같습니다. 그냥 그거.... 😅하고 말았던 것 같아요.

한번 정리하고 가니 좋네요! 조금이라도 도움이 되셨다면 좋겠습니다 :)