레코드, 키의 정의 및 검색 트리
트리에대한 알고리즘 공부에 앞서 트리에 대해 알아보는 시간을 가진다.
대부분의 자료는 gmlwjd9405.github.io/2018/08/12/data-structure-tree.html 를 참조하였다. 알고리즘및 자료구조에관한 정리를 매우 잘 해놓은 블로그이니 참조하면 좋다.
레코드, 키의 정의 및 검색 트리
- 레코드
- 개체에대해 수집된 모든 정보를 포함하고있는 저장단위
- 필드
- 검색키
- 다른 레코드와 중복되지 않는 각 레코드를 대표하는 필드
- 키는 하나의 필드로 이루어질 수 도 있고 두개 이상의 필드로 이루어질 수 도 있다.
- 검색트리
- 각 노드가 규칙에 맞도록 하나씩의 키를 가지고있다.
- 이 키를 이용해 해당 레코드가 자정된 위치를 알 수 있다.
TREE 자료구조의 특징
- TREE는 노드로 이루어진 자료구조이다.
- 트리는 하나의 루트 노드를 가진다.
- 루트노드는 0개 이상의 자식 노드를 가진다.
- 그 자식노드도 0개이상의 자식 노드를 가진다.
- 트리는 노드(node)와 그 노드들을 연결하는 간선(edge)으로 이루어져있다.
- 트리의 노드 사이에는 CYCLE(순환)이 없다.
- 노드 사이엔 특정 순서가 있을수도 있고 없을수도있다.
- 각 노드는 부모도드로 연결이 있을수도있고 없을수도있다.
- 각 노드는 어떤 자료형으로도 표현이 가능하다.
- 비 선형 자료구조이고계층적 관계를 표현한다.
- 주어진 배열에서 최솟값을 찾는다.
- 그 값을 맨앞의 값과 교체한다.
- 맨처음 위치를 뺀 나머지 리스트를 같은 방법으로 교채한다.
- 하나의 원소만 남을때까지 위의 과정을 반복한다.
- 그래프의 한 종류이다.
- 사이클이 없는 연결그래프이다.
- DAG(Directed Acyclic Graph, 방향성이 있는 비순환그래프)의 한종류이다.
TREE 와 연관된 용어
- 루트(root)노드: 부모가 없는 노드. 트리는ㄴ 하나의 루트노드만 가진다.
- 단말(leaf)노드: 자식이 없는 노드.
- 내부(internal)노드: 루트도, 단말도 아닌 노드(부모와 자식이 있는 노드)
- 간선(edge): 노드들을 연결하는선. link, branch라고도 부른다.
- 형제(sibling)노드: 같은 부모를 가지는 노드
- 노드의 크기: 자신을 포함한 모든 자손 노드의 수
- 노드의 깊이(depth): 루트에서 특정 노드에 도달하기위해 거쳐야하는 간선의수
- 노드의 레벨(level): 루트에서 어떤 노드에 도달하기 위해 거처야하는 간선의 수
- 노드의 차수(degree): 하위 트리의 개수 / 간선 수 degree = 각 노느가 가진 가지의 수
- 트리의 타수(degree of tree): 트리의 최대 차수
- 트리의 높이(height): 루트에서 부터 가장 깊숙히 있는 노드의 깊이.
이미지 출처 https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
TREE 의 종류
- 이진트리(Binary Tree)
- 각노드가 최대 두개의 자식을 가질 수 있다.
- 모든 트리가 이진트리는 아니다.
- 중위(in-order), 전위(pre-order), 후위(post-order)순회가 가능
- 이진 탐색트리
- 모든 노드가 특정 순서를 따르는 속성이 있는 트리
- 모든 외쪽 자식들 < 부모 < 오른쪽자식들의 순서를 가지고있는다.
이외의 균형/비균형, 전이진/완전이진/포화이진 트리 및 힙 트라이 같은 파생형은 출처에서 공부하면좋다.
gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
[자료구조] 트리(Tree)란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
알고리즘을 공부하기위해 특징을 리마인드하기위한 포스팅이라서 구현방법같은 자료구조 영역은 생략한다. 자세한 사항은 출처를 확인하면 좋다.