트리, 고급 정렬

이진 트리

-모든 노드의 차수를 2 이하로 제한하여 전체 트리 차수가 2 이하

-이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드만 가짐(공백 노드도 자식으로 취급)

-0 <= 노드의 차수 <= 2

 

이진 트리의 종류

 

 

-포화 이진 트리

모든 레벨에 노드가 포화상태인 이진 트리

높이가 h일 때, (2^(h+1)-1)개의 노드를 가졌다.

 

-완전 이진 트리

이 사진은 완전 이진 트리이다.

하지만 만약 12번에 노드가 없고 13번에 노드가 있으면, 즉 노드가 연속하지 않으면 완전 이진 트리가 아니다.

---

heap

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

 

 

-최대 heap

부모 노드 >= 자식 노드

루트 노드는 키값이 가장 큰 노드

 

-최소 heap

부모 노드 <= 자식 노드

루트 노드는 키값이 가장 작은 노드

 

heap 삽입 연산

왼쪽에 23을 삽입하면 맨 끝에 23을 넣는다. 그리고 크기를 비교한다.

23은 부모 노드인 19보다 커서 자리를 바꾼다.

그리고 20보다도 커서 20과 23도 바꾼다.

 

heap 삭제 연산

맨 위에 노드를 삭제한다. 그리고 맨 마지막 노드를 가져와서 루트 자리에 넣고 비교해준다.

---

병합 정렬

처음에 숫자가 있으면 반으로 나눈다.

 

그리고 각각 정렬한다.

그러고나서 뒤에꺼부터 비교를 해준다.

뒤에 첫번째 11은 8보다 크고 31보다 작아서 그 사이에 넣어준다.

두번째인 15는 11보다 크고 31보다 작아서 그 사이에 넣어준다.

이런식으로 정렬을 한다.

 

최종적으로 이렇게 정렬이된다.

병합 정렬이 삽입 정렬보다는 효율성이 좋다.

 

퀵 정렬

기준 값을 중심으로 두고 왼쪽, 오른쪽 부분 집합으로 분할하여 정렬하는 방법

기준 값으로 피봇을 가지는데 이것은 중앙값이다.

 

-기준점 가운데

총 7개라서 2로 나눈 값은 3이라 3번째에 있는 2를 피봇으로 정했다.]

 

1. L은 왼쪽, R은 오른쪽에 두고 R을 왼쪽으로 움직이면서 피봇보다 작은 원소를 찾는다.

2. 만약 피봇보다 큰 원소와 작은 원소를 찾으면 L, R 두 개의 자리를 바꾼다.

3. 피봇보다 작은 원소를 못찾아서 L과 R이 만나면 L, R이 있는 숫자와 피봇의 값을 바꿔준다.

 

따라서 69와 2를 바꿔주고 2는 자리를 확정한다.

 

1. 2를 확정지어서 다시 피봇을 가운데 값인 16으로 바꿔주고 16보다 큰 수와 작은 수를 찾는다.

2. 왼쪽에서는 30이 16보다 크고, 오른쪽에서는 8이 16보다 작다. 그래서 30과 8의 자리를 바꾼다.

3. 바꾸는데 성공해서 피봇은 16으로 그대로 둔다. 그리고 다시 L과 R을 찾는다. 하지만 오른쪽에 16보다 큰게 없어서 L과 R이 16으로 온다. 따라서 69와 16의 자리를 바꾸고 16은 자리가 고정된다.

 

16이 고정되어서 왼쪽 부분집합과 오른쪽 부분집합이 나눠져서 왼쪽부터 정렬했다.

 

-기준점 끝(시험에선 이걸로 풀어야됨)

15를 기준점으로 잡는다.

 

그러면 이런 결과가 나온다.

이때 왼쪽 집합은 끝인 3을 기준으로 잡고, 오른쪽 집합은 끝인 73을 기준으로 잡은 다음에 또 정렬해준다.

---

기수 정렬

1. 일의 자리 수부터 나열을 한다.

2. 십의 자리 수로 나열

3. 백의 자리 수로 나열

4. 천의 자리 수로 나열

 

---

퀵 정렬과 버블 정렬이 자주 쓰인다.