이번 챕터에서는 정말 중요한 자료구조 중 하나인 트리에 대해 공부하려고 한다. 정리 순서는 아래와 같다.
- 트리란 무엇인가?
- Linked Structure for Trees
- tree method & tree method's running time
그럼 시작!
1. 트리란 무엇인가?
트리는 그래프의 일종으로, 간단하게 이야기하면 노드로 이루어진 계층 구조를 나타낸다.
tree라고 정의될 수 있는 조건은
- 루트노드가 필수로 존재해야 한다
- 루트 밑에 있는 노드들도 트리 조건을 만족해야한다
- 자식노드는 부모노드가 1개여야만 한다
정도로 정의할 수 있다. 위 조건을 모두 만족해야 tree라고 정의할 수 있다.
트리는 File systems, Web sites, Databases 등에서 활용하고, linked list로 주로 구현한다.
1-1. 트리 구성요소
1) Root : 부모노드가 없는 노드 ex) A
2) Internal node : 자식노드를 갖는 노드 ex) A, B, C, F
3) External node : 자식노드를 갖지 않는 노드 = Leaves ex) D, E, G
4) Ancestors : 조상노드를 의미함 ex) G의 Ancestors >> F, C, A
5) Depth : ancestors의 노드 수 ex) G의 Depth >> 3
6) Height : 해당 tree에서 depth의 최댓값 ex) G가 3으로 가장 많으므로 이 트리의 height는 3
7) Descendant : 손자노드를 의미함 ex) C의 descendant >> F, G
8) Subtree : External node의 경우 그 자체로 subtree가 될 수 있으나, Internal node는 descendant까지 포함해야 subtree가 될 수 있음 ex) D는 subtree이고, F는 subtree가 아님
9) Siblings : 부모를 공유하는 형제노드. 형제노드간 연결은 불가능함 ex) D의 sibling : E
10) Path : 노드들 사이에 있는 노드 ex) G에서 A까지 path >> F, C
2. Linked Structure for Trees
트리를 linked list로 구현할 때 노드는 요소, 부모노드를 가리키는 포인터, 자식노드를 가리키는 포인터로 구성된다. 한 노드밖에 없는 부모노드와 달리 자식노드의 개수는 여러 개일 수 있으므로 리스트로 구현된다.
3. tree method & tree method's running time
Tree Method
이용하는 몇몇 메소드들이 정해져있다.
We use positions to abstract nodes
- Generic methods :
-integer size()
-boolean isEmpt()
-🌟Iterator iterator() >> 반복적으로 모든 노드들에게 적용되는 연산자
-Iterable positions() >> 특정노드위치를 알려줌 - Accessor methods :
-position root()
-position parent(p)
-Iterable children(p) - Query methods :
-boolean isInternal(p)
-boolean isExternal(p)
-boolean isRoot(p) - Update method :
-element replace(p,o) >> p노드를 o노드로 대체해달라
Method's ruuning time
메소드의 러닝타임은 다음과 같다.
▶ size의 시간복잡도가 O(1)인 이유는 size라는 전역변수를 정의해놨기 때문이다.
▶ tree의 모든 값을 리턴하는 함수인 elements, 해당 노드의 위치를 알려줘야하는 positions은 모든 노드를 스캔해야한다는 공통점을 가진다. 따라서 O(n)의 시간복잡도를 갖는다.
▶ replace는 어떤 노드를 바꿔야하는지 알려주기 때문에 O(1)이 된다.
▶ children(v)는 O안에 상수가 아닌 변수가 들어간다. 그 이유는 손자노드 없이 엄청 많은 수의 자식노드만 있는 구조일 수도 있기 때문이다. 그래서 worst case의 경우는 O(n)이 되고 보통의 경우 O(Cv)가 된다.
이렇게 general tree를 살펴봤다. 다음 챕터에서는 binary tree에 대해 다룰 예정! 2022/3/7 끗
