[알고리즘/Algorithm] 이진 트리(Binary Search Tree)에서의 퀵 소트(Quick Sort) 구현

Left Skewed Binary Tree(LHBT)

다음과 같은 입력이 들어와서 왼쪽으로 치우친(Left Skewed Tree)가 만들어졌다고 생각해보자.

우리는 이를 Binary Search Tree의 조건을 만족하도록 정렬할 것이다. 그 방법중 하나로 Quick Sort를 이용할 것이다.

 

root 노드를 기준점으로 놓고, root보다 작으면 왼쪽으로 붙이고, root보다 크면 오른쪽으로 붙이면 된다.

이를 Recursive하게 구현하면 쉽게 구현할 수 있을것으로 생각된다.

 

그럼 실제 C 코드로 구현해보자.

typedef struct BTNode {
  int data;    
  struct BTNode *left, *right;    // binary tree: left and right children
}T_NODE;

void *insert_left_node_to_bst(T_NODE *root, T_NODE *newPtr)
{
  if(root){
        if(root->left == NULL) root->left = newPtr;
        else{
            insert_left_node_to_bst(root->left, newPtr);
        }
  }
}
 
T_NODE *generate_BST_quicksort_basic(T_NODE *lhbt)
{
    T_NODE* newPtr, *savePtr;
    T_NODE* root = lhbt;
    if(!root) {return root;} // if lhbt is NULL
    newPtr = root->left;
    if(!newPtr)    // if left pivot is empty
    {
        root->left = NULL;
        return root;
    }
    root->left = NULL;    //disconnect root and root left
 
    while(newPtr != NULL){ 
        if(root->data < newPtr->data){ // if newPtr > root
            if(root->right == NULL){
                    root->right = newPtr;}
            else{
                insert_left_node_to_bst(root->right,newPtr); // insert newPtr to root->right
            }
        }
        else{  // if newPtr < root
            insert_left_node_to_bst(root, newPtr);
 
        }
        savePtr = newPtr;
        newPtr = newPtr->left;
        savePtr->left = NULL; // disconnect newPtr
    }
    // Recursive
    root->left = generate_BST_quicksort_basic(root->left);
    root->right = generate_BST_quicksort_basic(root->right);
 
    return root;
}

 

위 코드를 돌려보자.

{1 4 0 8 9 8 5 7 9}로 생성된 left skewed tree를 quick sort로 정렬해보았다.

Quick Sort 결과

'/'는 right child를 뜻하고 '+'는 left child를 뜻한다. 정렬이 제대로 수행됨을 확인할 수 있다.

quick sort 함수 내부 동작 확인

다음으로는 Tree를 예쁘게 print 하는 방법, BST에서의 insertion sort,

BST를 Complete Binary BST로 변환시키는 방법에 대해 업로드할 생각이다.