C++ 이진 검색 정렬

이진 검색 트리 문제

출처 : 백준 알고리즘

문제

P는 크기가 N인 배열이다. P에는 0보다 크거나 같고, N-1보다 작거나 같은 정수가 중복 없이 채워져 있다. 이진 검색 트리는 루트가 있는 이진 트리로, 각각의 노드에 정수 값이 저장되어 있는 트리이다. 이진 검색 트리를 P배열을 이용해서 만드는 법은 다음과 같다. 일단 root를 만들고 거기에 P[0]의 값을 넣은 후에 다음과 같은 과정을 거친다.

for (int i=1; i<=n-1; i++) {
    insert(root, P[i]);
}

여기서 insert함수는 다음과 같다.

void insert(Vertex V, int X) {
    if (x < V에 저장되어 있는 수) {
        if (V가 왼쪽 자식이 있으면) {
            insert(V의 왼쪽 자식, X);
        } else {
            V의 왼쪽 자식을 새로 만들고, 그 곳에 X를 저장함
        }
    } else {
        if (V가 오른쪽 자식이 있으면) {
            insert(V의 오른쪽 자식, X);
        } else {
            V의 오른쪽 자식을 새로 만들고, 그 곳에 X를 저장함
        }
    }
}

N과, 배열 P에 있는 수가 주어졌을 때, P로 이진 검색 트리를 만들었을 때, 모든 노드의 높이의 합을 출력하는 프로그램을 작성하시오. 트리의 높이는 루트에서 부터의 거리 + 1이다.

입력

첫째 줄에 N이 주어진다. N은 250,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 P[0]부터 P[N-1]의 원소가 한 줄에 하나씩 들어온다.

ex)

10  
9  
1  
4  
3  
2  
5  
6  
7  
8  
0

출력

주어진 P배열로 이진 검색 트리를 만들었을 때, 높이의 합을 출력한다. 이 값은 2^63보다 작다.

ex)

40

풀이

#include <iostream>
using namespace std;
    
int main() {
    int n;
    cin >> n;
    
    if(n<=250000) {
        int height[n];
        int list[n];
        int sum = 0;
        
        for(int i=0; i<n; i++) {
            int data;
            cin >> data;
            
            int front = 0;
            int back = i;
            int size = i;
            
            int spot;
            int leftHeight;
            int rightHeight;
            
            while(front<back) {
                int mid = (front+back) / 2;
                
                if(list[mid]<data) {
                    front = mid + 1;
                } else {
                    back = mid;
                }
            }
            
            spot = back;
            
            if(spot>0) {
                leftHeight = height[spot-1];
            } else {
                leftHeight = 0;
            }
            
            if(spot<size) {
                rightHeight = height[spot];
            } else {
                rightHeight = 0;
            }
            
            if(spot < size) {
                for(int j=size; j>spot; j--) {
                    list[j] = list[j-1];
                    height[j] = height[j-1];
                }
            }
            
            if(leftHeight>rightHeight) {
                height[spot] = leftHeight+1;
            } else {
                height[spot] = rightHeight+1;
            }
            
            list[spot] = data;
            sum += height[spot];
        }
        
        cout << sum << endl;
        return 0;
    } else {
        cout << "Over range" << endl;
    }
}