[자료구조] To convert Binary Tree to Binary Serach Tree

원문링크 : https://www.javatpoint.com/program-to-convert-binary-tree-to-binary-search-tree

Program to Convert Binary Tree to Binary Search Tree - javatpoint

Binary Tree

-node에 데이터를 저장하고 left, right child를 갖는 자료구조

Binary Search Tree

-해당 node의 데이터 보다 큰 date들은 right child에 작은 data들은 left child에 보관하는 자료구조

 

이하 BT , BST

처음 떠올린 알고리즘은 아래와 같다.

1. BT의 모든 node의 데이터들을 array에 저장한다.

2. array에 저장된 데이터를 가지고 BST를 만든다.

 

동적메모리할당을 배열을 선언하고 queue형식으로 저장하려고 했다.

즉 BT의 데이터들을 추출해 enqueue하고, 이를 dequeue하여 BST를 만드는 것이다.

데이터를 추출하는 과정에서는 In-order traverse를 적용하였다.

 

*queue

-자료구조의 한 형식으로 FIFO(First In First Out)의 방식으로 자료를 관리한다.

 

첫  배열 동적메모리할당 부분에서 오류가 발생했다.

 

15번 코드 줄에서 오류가 발생했는데, 이를 이해하기 위해서는 메모리구조 개념을 알아야 한다.

#include <stdio.h>
#include <stdlib.h>
 
struct node{
    int data;
    struct node* left;
    struct node* right;
};
 
struct node *root = NULL;
 
int front = -1;
int rear = 0;
int size = 1;
int *queue = (int*)malloc((sizeof(int)*10)*size)
 
void enqueue(int data){
    queue[rear] = data;
    rear++;
    if(size%10==9){
        queue = relloc(queue,sizeof(int)*size)
    }
}
 
int dequeue(){
    front++;
    return queue[front];
}
 
void collect(struct node *temp){
    if(temp->left!=NULL){
        collect(temp->left);
    }
    enqueue(temp->data);
    if(temp->right!=NULL){
        collect(temp->right);
    }
    return;
}
 
 
int main()
{
    printf("Hello World");
    enqueue(1);
 
    return 0;
}

메모리는 구조는 STACK과 DATA 그리고 HEAP 영역으로 이루어져 있는데, STACK,DATA 영역은 코드가 컴파일되는 동안에 할당될 메모리크기가 결정이된다.

 

*컴파일 : 고급언어인 C언어를 컴퓨터가 알아들을 수 있는 기계어로 바꾸는 과정

 

HEAP영역은 프로그램이 실행되는 동안 메모리가 할당될 크기가 결정된다. 즉 런타임에 할당될 크기가 정해진다. 메모리 동적 할당은 이 HEAP영역에서 이루어진다.

 

DATA, STACK 영역에 메모리를 할당할 경우 그 크기는 항상 상수여야 하고, 메모리 크기를 변수로 할당하고 싶으면 HEAP영역을 이용하여 동적할당해주어야 한다.

참고링크 : https://blog.naver.com/pk3152/221555917112

C 언어 기초 (45) 메모리 구조 (Heap 동적할당)

15번 줄에서 int* queue가 전역변수로 초기화되면서 DATA영역에서 할당되어 이의 메모리크기는 상수여야 한다. 컴파일 시기 때 메모리 크기가 정해지기 때문에 변수일 경우 컴퓨터는 이를 이해하지 못한다. (초기화 문의 변수 값은 런타임 때 정해짐)

 

이 문제를 해결하고 queue구조로 이용할 배열을 동적할당하기 위해 다음과 같이 우회하였다.

1.int *queue를 DATA영역에 초기화하여 쓰레기값을 넣고

2.HEAP 영역에서 realloc를 이용하여 메모리 재할당을 했다

 

첫 값이 입력될 때 int data 10개를 저장할 수 있는 메모리공간을 queue에 realloc하고 이후 데이터가 배열에 추가로 10개째 저장될 때마다 10개 값을 넣을 메모리 공간을 추가로 할당하게끔 구현했다.

코드는 아래와 같다.

int front = -1;
int rear = 0;
int size = 1;
int *queue;
 
void enqueue(int data){
    if(rear==0){
        queue = realloc(queue,(sizeof(int)*10)*size);
        size++;
    }
    queue[rear] = data;
    rear++;
    return;
}

이를 반영한 총 코드는 아래와 같다.

#include <stdio.h>
#include <stdlib.h>
 
struct node{
    int data;
    struct node* left;
    struct node* right;
};
 
struct node *root = NULL;
struct node *BSTroot = NULL;
 
int front = -1;
int rear = 0;
int size = 1;
int *queue;
 
void enqueue(int data){
    if(rear==0){
        queue = realloc(queue,(sizeof(int)*10)*size);
        size++;
    }
    queue[rear] = data;
    rear++;
    return;
}
 
int dequeue(){
    front++;
    return queue[front];
}
 
struct node* createNode(int data){
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
 
void collect(struct node *temp){
    if(temp->left!=NULL){
        collect(temp->left);
    }
    enqueue(temp->data);
    if(temp->right!=NULL){
        collect(temp->right);
    }
    return;
}
 
void BSTinsert(int data){
    struct node *newNode = createNode(data);
    struct node *current = NULL;
    struct node *parent = NULL;
    
    if(root==NULL){
        root = newNode;
        printf(" to the root\n");
        return;
    }
    else{
        current=root;
        while(1){
            parent = current;
            if(current->data > data){
                if(current->left==NULL){
                    current->left = newNode;
                    printf(" left\n");
                    return;
                }
                current = current->left;
                printf(" left");
            }
            else{
                if(current->right==NULL){
                    current->right = newNode;
                    printf(" right\n");
                    return;
                }
                current = current->right;
                printf(" right");
            }
        }
    }
}
 
void BTtoBST(struct node* btRoot){
    root=NULL;
    collect(btRoot);
    for(int i = front + 1 ; i < rear ; i++){
        int j = dequeue();
        printf("Insert %d",j);
        BSTinsert(j);
        
    }
    return;
}
 
void inOrder(struct node *root){
    if(root->left!=NULL){
        inOrder(root->left);
    }
    printf("%d ",root->data);
    if(root->right!=NULL){
        inOrder(root->right);
    }
    return;
}
 
int main()
{
    printf("Hello World\n");
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    
    printf("Binary Tree\n");
    inOrder(root);
    printf("\n");
    BTtoBST(root);
    
    printf("Binary Search Tree\n");
    inOrder(root);
 
    return 0;
}

 

위의 코드대로라면 BT의 데이터를 in-order순서로 array에 넣고 FIFO 순서로 데이터들을 BST에 하나씩 추가한다.

여기서 또 문제가 발생하는데 In-order 순서로 array에 담고 queue 방식으로 dequeue하여 BST를 만들게 되면 BT의 left leaf가 BST의 root가 되게 된다. 즉 제공되는 array의 구조, 순서에 따라 만들어지는 BST가 달라지게 된다는 말이다.

(알고리즘을 완성하고 원문과 비교하다가 문제를 발견)

 

위의 그림을 예로들면 4가 array의 제일 첫 값이 되어 오른쪽에 보이는 4가 root인 BST가 만들어졌다. 기존에 만들려고 했던 TREE와 구조가 다른 것을 확인할 수 있는데. 이는 array에서 5가 6보다 앞에 있어 먼저 dequeue되어 insert되기 때문에 6이 5의 parent가 될 수 없는 구조이다.

 

운이 좋아 4가 array의 맨 앞에 있어 그래도 무난한 TREE가 만들어졌지 만약 1이나 2가 첫값이었다면, 만들어진 BST는 right subtree만 엄청나게 긴 모습을 보였을 것이다.

 

이를 해결하고 child 가 균등하게 잘 배치되어있는 BST를 만들기 위해서는,

 

BST에서 root가 array의 중간값이 되어야 하고 따로 추가되는 data들의 순서도 남은 데이터들의 중간값이 우선적으로 추가되어야 한다. (BSTinsert 함수 구조상 어쩔 수 없음)

 

이를 구현하기 위해 아래와같은 과정을 추가한다.

1. BT를 array에 담은 다음 오름차순으로 sort한다.

2. array의 중간값을 BST에 insert한다.

3. 중간값을 기준으로 양 옆으로 left와 right array로 나눈다

4. 나누어진 두 array의 중간값을 BST에 insert한다.

5. 2~4번 과정을 array의 사이즈가 1일 때까지 반복한다.

 

프로세스를 수정하면서 queue 자료구조의 활용성이 떨어져 단순한 배열에 데이터를 저장했다.

그림으로 표현하면 아래와 같다.

이를 코드로 아래와 같이 구현했다.

#include <stdio.h>
#include <stdlib.h>
 
struct node{
    int data;
    struct node* left;
    struct node* right;
};
 
struct node *root = NULL;
struct node *BSTroot = NULL;
 
int size = 0;
int queue[100];
 
void add(int data){
    queue[size] = data;
    size++;
    return;
}
 
void sort(int *queue){
    int temp=0;
    int arr_size = size;
    for(int i=0; i<arr_size ; i++){
        for(int j=i+1; j<arr_size;j++){
            if(queue[i]>queue[j]){
                temp = queue[i];
                queue[i] = queue[j];
                queue[j] = temp;
            }
        }
    }
}
 
struct node* createNode(int data){
    struct node *newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
 
void collect(struct node *temp){
    if(temp->left!=NULL){
        collect(temp->left);
    }
    add(temp->data);
    if(temp->right!=NULL){
        collect(temp->right);
    }
    return;
}
 
void BSTinsert(int data){
    struct node *newNode = createNode(data);
    struct node *current = NULL;
    struct node *parent = NULL;
    
    if(root==NULL){
        root = newNode;
        printf(" root ");
        printf("inserted data = %d\n",newNode->data);
        return;
    }
    else{
        current=root;
        while(1){
            parent = current;
            if(current->data > data){
                if(current->left==NULL){
                    current->left = newNode;
                    printf(" left ");
                    printf("insertd data = %d\n",newNode->data);
                    return;
                }
                current = current->left;
                printf(" left");
            }
            else{
                if(current->right==NULL){
                    current->right = newNode;
                    printf(" right ");
                    printf("insertd data = %d\n",newNode->data);
                    return;
                }
                current = current->right;
                printf(" right");
            }
        }
    }
}
 
void BSTroop(int* queue,int arr_size){
    if(arr_size==1){
        BSTinsert(queue[0]);
        return;
    }
    else{
        int arr_mid = arr_size/2;
        int arr_size_r;
        
        printf("arr_size is %d\n",arr_size);
        printf("arr is = ");
        for(int i =0; i<arr_size;i++){
            printf("%d ",queue[i]);
        }
        printf("\n");
        BSTinsert(queue[arr_mid]);
        
        int arr_left[arr_mid];
        
        if(arr_size%2==0){
            arr_size_r = arr_size-(arr_mid-1);
        }
        else{
            arr_size_r = arr_mid;
        }
        
        int arr_right[arr_size_r];
        
        for(int i=0 ; i < arr_mid ; i++){
            arr_left[i] = queue[i];
        }
        for(int i=0 ; i < arr_size_r ; i++){
            arr_right[i] = queue[i+arr_size_r+1];
        }
        BSTroop(arr_left,arr_mid);
        BSTroop(arr_right,arr_size_r);
    }
    return;
}
 
void inOrder(struct node *root){
    if(root->left!=NULL){
        inOrder(root->left);
    }
    printf("%d ",root->data);
    if(root->right!=NULL){
        inOrder(root->right);
    }
    return;
}
 
void queueprint(){
    for(int i = 0 ; i<size;i++){
        printf("%d ",queue[i]);
    }
    return;
}
 
int main()
{
    printf("Hello World\n");
    root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    
    printf("Binary Tree\n");
    inOrder(root);
    printf("\n");
    
    collect(root);
    printf("sorted queue\n");
    sort(queue);
    queueprint();
    printf("\n");
    root=NULL;
    BSTroop(queue,size);
    
    inOrder(root);
    
    return 0;
}

원문의 글과 알고리즘은 같으나 내 코드가 복잡성이 더 높아 열등한 것 같다.

특히 array 중간값을 insert하고 이를 기준으로 두 array로 나누는 과정의 알고리즘은 원문의 것이 더 나은 것 같다. 

(아래 원문 해당 알고리즘 코드)

struct node* createBST(int start, int end) {  
      
    //It will avoid overflow  
    if (start > end) {  
        return NULL;  
    }  
      
    //Variable will store middle element of array and make it root of binary search tree  
    int mid = (start + end) / 2;  
    struct node *temp = createNode(treeArray[mid]);  
   
    //Construct left subtree  
    temp->left = createBST(start, mid - 1);  
   
    //Construct right subtree  
    temp->right = createBST(mid + 1, end);  
   
    return temp;  
}

parameter로 start 와 end를 받고 이를 활용해 재귀함수를 만들어 구현한 것이 인상적이다.

만약 BST를 만들기 위해 이용될 array가 이미 sort되어 있다고 하면 기존에 BST를 construct할 때 썼던 BSTinsert함수를 이용할 필요가 없다.

 

*기존 BSTinsert함수는 입력될 데이터값과 기존의 데이터값을 비교하여 어디에 추가될 것인지 결정했음

 

이미 sort 되어 있기 때문에 단지 위의 코드처럼 left array중간값을 left subtree에 넣고 right array중간값을 right subtree에 넣으면 된다. 이는 실제 컴퓨터 연산적 측면에서 불필요한 일을 하지 않고 코드도 덜 복잡하다.

복잡해 보이는 과정을 심플하게 구현해내는 것이 중요한 것 같다.

 

내가 이 문제를 풀면서 이룬 것은,

1. BT를 array로 받아 BST를 만든다는 알고리즘을 떠올린 것

2. 원문과 비교하여 발견한 문제점을 해결하는 알고리즘을 이해하고, 이를 코드로 구현한 것.

 

이루지 못한것

1. 한번에 완성도 높은 알고리즘을 떠올리는 것

2. 알고리즘을 구현하고 이를 최적화 하는 것

 

-알고리즘을 떠올리고, 코드를 짜기 전 섬세하게 피드백하여 완성도를 높히기.

-구현했을 때 여러가지 케이스를 검사해보고 다양한 예외사항 체크하기

-최적화할 수 있는 부분 체크하기

-코드 잔실수 줄이기

여러 문제상황과 코드를 접해보고 기록하자.

 

**

메모리구조

재귀함수

BinaryTree

BinarySearchTree

Queue

Array

Sorting

Heap

DATA

STACK

DynamicAllocation