[알고리즘 이론] Tree

오늘은 트리에 대해서 알아보려고 합니다.

해당 내용은 종만북을 공부하고 정리한 내용입니다

 

✔︎ 트리 란 ?

계층적 구조를 갖는 자료들을 표현하기 위한 자료구조

주로 노드를 구조체로 표현하고 자식 노드를 포인터로 연결

 

✔︎ 순회

계층적 구조를 갖는 트리의 노든 노드를 확인하는 것은 중요

이를 순회라고 하며 주로 재귀적 속성을 활용해서 진행

 

⁃ 전위순회 : 부모 -> 왼쪽 자식 -> 오른쪽 자식

⁃ 중위순회 : 왼쪽 자식 -> 부모 -> 오른쪽 자식

⁃ 후위순회 : 왼쪽 자식 -> 오른쪽 자식 -> 부모

 

[ 대표문제 ] 트리 순회 순서 변경

전위순회 + 중회순회 주어졌을떄 후위순회 결과 출력

void printPostOrder(const vector<int>& preorder, const vector<int>& postorder){
	
    int nodeCnt = preorder.size();
    if(!nodeCnt) return;
    
    int root = preorder[0];
    
    int leftSubTreeSize = find(inorder.begin(), inorder.end(), root) - inorder.begin();
    int rightSubTreeSize = nodeCnt - leftSubTreeSize;
    
    printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));
    printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));
    
    cout<< root <<endl;
    
}

 

=> 역시 순회문제라서 그런지 재귀를 기반으로 해결합니다.

     전위순회, 중위순회를 기반으로 전체 값을 서브트리로 각각 나우어서 재귀로 돌리면

     왼쪽서브트리가 먼저, 오른쪽 서브트리가 그다음 마지막으로 루트가 출력되면서 

     후위순외가 출력되게 됩니다.

 

[ 추가문제 ] leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal

리트코드에서 예전에 풀었던 문제인데 생각나서 가져왔습니다.

위의 대표문제와 동일한 방식으로 풀이가 가능합니다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int nodeCnt = preorder.size();
        TreeNode* node = new TreeNode();
        
        if(!nodeCnt) return nullptr;
        
        int root = preorder[0];
        
        
        int leftSubSize = find(inorder.begin(), inorder.end(), root) - inorder.begin();
        int rightSubSize = nodeCnt - leftSubSize;
        
        vector<int> sub1(preorder.begin() + 1, preorder.begin() + 1 + leftSubSize);
        vector<int> sub2(inorder.begin(), inorder.begin() + leftSubSize);
        vector<int> sub3(preorder.begin() + 1 + leftSubSize, preorder.begin() + nodeCnt);
        vector<int> sub4(inorder.begin() + 1 + leftSubSize, inorder.begin() + nodeCnt);
        
        node->left = buildTree(sub1, sub2);
        
        node->val = root;
        
        node->right = buildTree(sub3, sub4);
        
        return node;
    }
};

 

[ 대표문제 ] 요새

문제는 간단합니다.

울타리(중심좌표와 반지름으로 표현)들이 주어졌을때 임의의 정점을 연결했을때 가장 많이 울타리를 넘어야 하는 경우를 출력하면 됩니다.

 

언뜻 봐선,, 도형나오고 그러닌간 벡터쪽 아냐?? 라고 생각할 수 있을 거 같고, 예전에 회사에서 SW 알고리즘 시험에서 이와 같은 문제가 나왔었고 나는 벡터쪽 알고리즘들을 적용해서 풀려고 했었던거 같습니다.

 

하지만 위의 문제는 그래프 문제로 힌트는 모든 울타리들이 겹치지 않는다는 것으로 울타리가 계층적인 구조라는 것을 파악한다면

울타리를 트리로 구성할 수 있으며 결국 문제는 가장 멀리 떨어진 두 노드를 구하는 문제로 바뀌게 됩니다.

 

가장 먼 두 노드는 두가지 케이스 중 하나입니다.

  1. 루트 - 리프노드

  2. 리프노드 - 리프노드

 

1번 케이스는 트리의 높이라서 순회하면서 체크하면 됩니다.

2번 케이스는 언뜻 생각했을때는 루트노드의 각각의 서브트리의 최대높이 2개의 합일 것 같습니다.

하지만 아래의 이미지를 확인해보시면 모든 서브트리에서 위의 합들을 최대값을 찾아야한다는 것을 알 수 있습니다.

따라서 위의 케이스도 순회하면서 체크하면됩니다.

 

 

 

 

struct TreeNode {
    vector<TreeNode*> children;
};

int longest;

int height(TreeNode* root){
    vector<int> heights;
    
    for(int i = 0; i<root->children.size(); ++i){
    	heights.push_back(height(root->children[i]));
    }
    
    if(heights.empty()) return 0;
    
    sort(heights.begin(), heights.end());
    
    if(heights.size() >= 2){
    	longest = max(longest, 2 + heights[heights.size() - 2] + heights[heights.size() - 1]);
    }
    
    return heights.back() + 1;
}

int sole(TreeNode* root){
    longest = 0;
    
    int h = height(root);
    return max(longest, h);
}

 

✔︎ 이진 검색 트리

트리에 자료들은 일정한 순서와 규칙을 적용해서 저장한 상태를 말합니다.

원소의 추가와 삭제뿐만 아니라 특정 원소의 존재 여부 등 다양한 연산을 빠르게 처리할 수 있는 강력한 자료구조입니다~

 

[ 규칙 ]

자식 노드를 2개만 가진다.

각 노드의 왼쪽 서브트리에는 해당 노드의 원소보다 작은 원소만 저장, 반대로 오른쪽 서브트리에는 큰 원소만을 저장

 

위의 같은 규칙을 가지고 있어 특정한 값을 찾을때 이진 탐색과 비슷하게 진행됩니다.

 

[ 장점 ]

최소 값과 최대 값을 찾기 쉽다. => 이진트리의 왼쪽 끝과 오른쪽 끝

특정 값을 찾기 쉽다. => 바이너리 서치처럼 비교마다 비교대상이 절반씩 줄어듬

원소를 추가 및 삭제하는 조작연산의 편리함 => 이는 기존의 배열을 사용했을때보다 효율적

 

배열의 경우 삽입할 위치를 찾고 해당 위치부터 원소들을 뒤로 하나씩 미루고 삽입하게 됩니다. 최악의 경우 O(n)이 소요됩니다.

이진 검색 트리의 경우에는 삽입할 위치만 찾고 그곳에 노드를 추가하기만 하면됩니다. 

삭제의 경우에는 삭제할 위치를 찾고 삭제한 다음 트리구조를 다시 정비하는 작업이 필요하긴 합니다.

하지만 재정비 작업도 서브트리에서만 이루어지는 연산이어서 어렵지 않습니다.

 

✔︎ 균형잡힌 이진 검색 트리

이진 검색 트리의 장점을 활용하기 위해선 트리의 구조가 잘 잡혀서 높이가 log(N)에 수렴해야 합니다.

균형잡힌 이진 검색 트리는 추가적인 제약사항을 통해 항상 높이가 log(N)을 유지하는 자료구조로 대표적으로 레드-블랙 트리가 있습니다.

 

 

[ 대표문제 ] 너드인가, 너드가 아닌가?

문제를 요약하면 문제풀이 갯수와 라면 식사수의 정보가 하나씩 들어올때, 만약 기존의 있던 정보 중에서 새롭게 들어온 문제풀이 갯수, 라면

식사 수가 모두 작은 데이터는 제외하고 전체 갯수를 체크하는 문제입니다.

 

하나씩 모든 경우를 체크하면 아마 타임이웃이 뜰테니 좀 더 효율적인 방안을 생각해야 할 것 같습니다.