이번 챕터에서는 정말 중요한 자료구조 중 하나인 트리에 대해 공부하려고 한다. 정리 순서는 아래와 같다.
- 트리란 무엇인가?
- 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)가 된다.