레코드, 키의 정의 및 검색 트리

레코드, 키의 정의 및 검색 트리

 트리에대한 알고리즘 공부에 앞서 트리에 대해 알아보는 시간을 가진다. 
대부분의 자료는 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

 

알고리즘을 공부하기위해 특징을 리마인드하기위한 포스팅이라서 구현방법같은 자료구조 영역은 생략한다. 자세한 사항은 출처를 확인하면 좋다.