자료구조론

트리

트리의 차수는 이들 중 가장 큰 값으로 선택되므로 이 트리의 차수는 3

 

노드의 간선 N-1

 

노드의 최대 높이 N, 최소 높이 2N

 

전위순회 중 왼 위

중위순회 왼 중 위

후위순회 왼 오 중

 

---

힙

최대 힙은 각 노드의 키(key) 값이 그 자식의 키 값보다 작지 않은 완전이진트리

최소 힙은 각 노드의 키 값이 그 자식의 키 값보다 크지 않은 완전 이진트리

최대 힙의 루트는 그 트리에서 가장 큰 키 값을 가지고 있고, 최소 힙의 루트는 그 트리에서 가장 작은 키값을 가지고 있다.

 

---

정렬

1.선택정렬

방법: 선택된 값과 나머지 데이터 중에 비교하여 알맞는 자리를 찾는 알고리즘

 

2.삽입정렬(Insertion Sort)

데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳으로 삽입하는 알고리즘

 

3.버블정렬(Bubble Sort)

거품이 수면으로 올라오는 듯 하여 붙여진 버블정렬. 인접한 두 수를 비교하여 오름차순 내림차순,안정성 보장

 

4. 병합정렬(Merge Sort)

설명: 둘 이상의 부분집합으로 가르고, 각 부분집합을 정렬한 다음 부분집합들을 다시 정렬된 형태로 합치는 방식

 

5. 힙 정렬

내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다

 

6.퀵 정렬

데이터 집합내에 임의의 기준값을 정하고 해당 피벗으로 집합을 기준으로 두 개의 부분집합으로 나눈다.