다음과 같은 입력이 들어와서 왼쪽으로 치우친(Left Skewed Tree)가 만들어졌다고 생각해보자. 우리는 이를 Binary Search Tree의 조건을 만족하도록 정렬할 것이다. 그 방법중 하나로 Quick Sort를 이용할 것이다. root 노드를 기준점으로 놓고, root보다 작으면 왼쪽으로 붙이고, root보다 크면 오른쪽으로 붙이면 된다. 이를 Recursive하게 구현하면 쉽게 구현할 수 있을것으로 생각된다. 그럼 실제 C 코드로 구현해보자. 1 2 3 4 typedef struct BTNode { int data; struct BTNode *left, *right; // binary tree: left and right children }T_NODE; Colored by Color Sc..

QuickSort Quicksort는 Divide and Conquer 알고리즘으로, 어떤 원소를 기준점(Pivot)으로 고른 후 그 기준으로 어레이를 나누는 알고리즘이다. 우선 Psuedo Code로 간략하게 알고리즘에 대해 이해해보자. 우선 Partition의 목적은 A[p....i] 어레이는 모두 Pivot보다 작은 값으로. A[j...n] 어레이는 모두 Pivot보다 큰 값으로 만들고자 하는 것이다. 위 Psuedo Code를 하나하나 차례대로 뜯어보자. 우선 Pivot x를 A[p]값으로 설정한다. i는 p보다 하나 작은 값, j는 r보다 하나 큰 값으로 설정한다. r은 partition할 어레이의 맨 마지막 부분이다. 이렇게 하면 Pivot P를 기준으로 P의 오른쪽 부분에서 스위칭이 일어나게..