[2017.05.15~2017.05.19] 자료구조 4/5

셸 정렬

일정한 간격으로 떨어져있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽 입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법

병합 정렬

여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법

부분집합으로 분할하고, 각 부분집합에 대해서 정렬 작업을 완성한 후에 정렬된 부분집합들을 다시 결 합하는 분할 정복 기법 사용

기수 정렬(radix sort)

원소의 키값을 나타내는 기수를 이용한 정렬 방법

트리

이미지 출처 : http://stackoverflow.com/questions/19330731/tree-implementation-in-java-root-parents-and-children

원소들 간에 1대 다 관계를 가지는 비선형 자료구조

원소들 간에 계층고나계를 가지는 계층형 자료구조

상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조

이진트리

이미지 출처 : 위키 https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC

• 트리의 노드 구조를 일정하게 정의하여 트리의 구현과 연산이 쉽도록 정의한 트리
• 이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드 만을 가진다.
• 부모 노드와 자식 노드 수와의 관계 1:2
• 공백 노드도 자식 노드로 취급한다.
• 0 <= 노드의 차수  <= 2

이진트리의 특성

• n개의 노드를 가진 이진 트리는 항상 (n-1)개의 간선을 가진다.
• 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^(h+1)-1)개가 된다.

히프(heap)

완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조

• 최대힙
• 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
• 부모노드의 키값 >= 자식노드의 키값
• 루트 노드 : 키 값이 가장 큰 노드
• 최소힙
• 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
• 부모노드의 키값 <= 자식노드의 키값
• 루트 노드 : 키 값이 가장 작은 노드