지난 내용
조상 노드, 깊이(depth), 자식 노드를 고려시 자기자신은 포함x!!!
- 트리는 계층 구조를 이룸
- 트리의 높이(height) = 노드들중에서 깊이의 최댓값
- 노드끼리 parent-child 관계로 연결되어있다.
즉, 어떤 노드를 보더라도 parent와 child가 있다.
(시작과 끝은 각각 parent와 child가 null 일 뿐)
cf. parent, child를 알 필요 없는 트리의 경우 둘 중 하나를 안주기도 한다.
Tree ADT
- 트리는 노드의 포지션으로 데이터에 접근함
- 노드로 구현하는 것이 일반적
- 노드 구조체 내부
- parent의 위치들과 child 위치들을 잘 알수있도록 노드 구조체 내부가 잘 구현되어 있어야함
- 구성요소 : 노드형 포인터 parent, 노드형 포인터 child들의 리스트
=> 트리에서는 child가 몇개일지 모르므로, 리스트에 child 노드형 포인터들을 저장
메소드
- position root()
- list< position > positions()
- position parent()
- list< position > childern()
- boolean isRoot()
- boolean isExternal()
- integer size()
- bool empty()
메소드 상세설명
- 바깥에서 access 할수있는 point를 제공해주는 메소드들
- position root() : 루트 노드의 position을 리턴
- list< position > positions() : 전체 노드의 position을 list 형식으로 리턴
- 노드들의 position 리스트. 링크드 리스트 형태로 유지
- position 기반 메소드들
- position parent() : 주어진 position에 대한 해당노드의 부모노드 position을 리턴
- list< position > childern() : 주어진 position에 대한 해당노드의 자식들의 position 리스트를 리턴
3.판단 메소드들
- boolean isRoot() : 루트 노드인지 판별
- boolean isExternal() : 외부 노드인지 판별
4.기타 메소드
- integer size()
- bool empty()
Preorder Traversal (전위순회)
-
traversal : 트리의 모든 노드들을 한번씩 방문(=작업을)하는 알고리즘
-
가장 먼저 자기자신을 작업한후, child를 문제에서 지정해준 방문순서에 따라 처리한다
-
시간복잡도 : O(1) => 각 노드에 대한 작업(visit)은 딱 한번만 한다.
-
각 자식들에 대해서 작업을 실행하려고 봤더니 작업할 자식이 더 없다면 return 해서 되돌아간다
Algorithm preOrder(v) // v가 루트노드인 트리에 대해서 전위순회를 한다
visit(v) // 자기 자신을 먼저 처리하고
for each child w of v // v의 각각의 child에 대해서 다 각각 전위순회를 실행
preOrder(w) // 재귀호출- child의 방문순서는 딱히 없지만, 시험문제 출제시 편의상 자식방문 순서를 지정해준다.
- 실제 코드상에서는 그 노드들이 어떤 순서대로 저장되있거나, 아무렇게나 지정되있는 자식들을 비교해서 sorting 해야하므로 시간복잡도가 달라진다.
- 아무렇게 방문하거나 특정 순서를 주고 그대로 순회를 한다면 O(1)이다.
- ex) 정수의 작은수부터 큰 순서대로 방문한다는 조건 / 알파벳 순서로 방문
Postorder Traversal
- 자식들을 다 처리후에 자신을 처리
- O(1) : 마찬가지로 각 노드들은 한번씩 처리된다.
- 활용분야 : 폴더의 하위폴더들의 용량을 다 더해서 총 용량을 구하는 것
Algorithm postOrder(v)
for each child w of v
postOrder(w)
visit(v)Binary Trees (이진트리)
-
정의 : 모든 internal 노드의 자식 노드가 2개 이하인 트리
-
재귀적 정의1 : 노드 하나만 있으면(single node) 이진트리
-
재귀적 정의2 : 트리인데 두 child 가 ordered pair(순서쌍)이고 각각이 다시 이진트리인 트리
-
활용분야 : 이항 연산자와 같은 수식표현(arithmetic expression), decision processes, 탐색(BST)
-
proper binary tree
- 모든 노드가 2개 또는 0개의 자식을 갖는 트리
- 구현시 dummy 노드를 추가해서 external node가 더이상 없음을 알려줄 수도 있다 (선택사항)
=> 데이터가 없는 노드를 트리 끝에 넣음으로써 트리의 끝임을 알려주기 위함
-
어떤 노드의 자식은 순서쌍(ordered pair)으로 이루어진다.
=> 왼쪽 자식(left child), 오른쪽 자식(right child) -
트리는 순서를 지정하지 않을 수 있지만, 이진 트리는 왼쪽자식 먼저 순서가 정해져있다.
https://haon.blog