09_tree_bst.cpp

Download
cpp 388 lines 10.8 KB 
  1/*
  2 * νŠΈλ¦¬μ™€ 이진 탐색 트리 (Tree and BST)
  3 * Tree Traversal, BST Operations, LCA
  4 *
  5 * 계측적 자료ꡬ쑰의 κ΅¬ν˜„κ³Ό ν™œμš©μž…λ‹ˆλ‹€.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <queue>
 11#include <stack>
 12#include <algorithm>
 13#include <climits>
 14
 15using namespace std;
 16
 17// =============================================================================
 18// 1. 이진 트리 λ…Έλ“œ
 19// =============================================================================
 20
 21struct TreeNode {
 22    int val;
 23    TreeNode* left;
 24    TreeNode* right;
 25    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 26};
 27
 28// =============================================================================
 29// 2. 트리 순회
 30// =============================================================================
 31
 32// μ „μœ„ 순회 (Preorder)
 33void preorder(TreeNode* root, vector<int>& result) {
 34    if (!root) return;
 35    result.push_back(root->val);
 36    preorder(root->left, result);
 37    preorder(root->right, result);
 38}
 39
 40// μ€‘μœ„ 순회 (Inorder)
 41void inorder(TreeNode* root, vector<int>& result) {
 42    if (!root) return;
 43    inorder(root->left, result);
 44    result.push_back(root->val);
 45    inorder(root->right, result);
 46}
 47
 48// ν›„μœ„ 순회 (Postorder)
 49void postorder(TreeNode* root, vector<int>& result) {
 50    if (!root) return;
 51    postorder(root->left, result);
 52    postorder(root->right, result);
 53    result.push_back(root->val);
 54}
 55
 56// 레벨 순회 (Level Order)
 57vector<vector<int>> levelOrder(TreeNode* root) {
 58    vector<vector<int>> result;
 59    if (!root) return result;
 60
 61    queue<TreeNode*> q;
 62    q.push(root);
 63
 64    while (!q.empty()) {
 65        int size = q.size();
 66        vector<int> level;
 67        for (int i = 0; i < size; i++) {
 68            TreeNode* node = q.front();
 69            q.pop();
 70            level.push_back(node->val);
 71            if (node->left) q.push(node->left);
 72            if (node->right) q.push(node->right);
 73        }
 74        result.push_back(level);
 75    }
 76
 77    return result;
 78}
 79
 80// 반볡적 μ€‘μœ„ 순회
 81vector<int> inorderIterative(TreeNode* root) {
 82    vector<int> result;
 83    stack<TreeNode*> st;
 84    TreeNode* curr = root;
 85
 86    while (curr || !st.empty()) {
 87        while (curr) {
 88            st.push(curr);
 89            curr = curr->left;
 90        }
 91        curr = st.top();
 92        st.pop();
 93        result.push_back(curr->val);
 94        curr = curr->right;
 95    }
 96
 97    return result;
 98}
 99
100// =============================================================================
101// 3. BST μ—°μ‚°
102// =============================================================================
103
104class BST {
105public:
106    TreeNode* root;
107
108    BST() : root(nullptr) {}
109
110    // μ‚½μž…
111    TreeNode* insert(TreeNode* node, int val) {
112        if (!node) return new TreeNode(val);
113
114        if (val < node->val)
115            node->left = insert(node->left, val);
116        else if (val > node->val)
117            node->right = insert(node->right, val);
118
119        return node;
120    }
121
122    void insert(int val) {
123        root = insert(root, val);
124    }
125
126    // 검색
127    TreeNode* search(TreeNode* node, int val) {
128        if (!node || node->val == val) return node;
129
130        if (val < node->val)
131            return search(node->left, val);
132        return search(node->right, val);
133    }
134
135    bool search(int val) {
136        return search(root, val) != nullptr;
137    }
138
139    // μ΅œμ†Ÿκ°’
140    TreeNode* findMin(TreeNode* node) {
141        while (node && node->left)
142            node = node->left;
143        return node;
144    }
145
146    // μ‚­μ œ
147    TreeNode* remove(TreeNode* node, int val) {
148        if (!node) return nullptr;
149
150        if (val < node->val) {
151            node->left = remove(node->left, val);
152        } else if (val > node->val) {
153            node->right = remove(node->right, val);
154        } else {
155            // μžμ‹μ΄ μ—†κ±°λ‚˜ ν•˜λ‚˜
156            if (!node->left) {
157                TreeNode* temp = node->right;
158                delete node;
159                return temp;
160            }
161            if (!node->right) {
162                TreeNode* temp = node->left;
163                delete node;
164                return temp;
165            }
166
167            // μžμ‹μ΄ λ‘˜
168            TreeNode* successor = findMin(node->right);
169            node->val = successor->val;
170            node->right = remove(node->right, successor->val);
171        }
172        return node;
173    }
174
175    void remove(int val) {
176        root = remove(root, val);
177    }
178};
179
180// =============================================================================
181// 4. 트리 속성
182// =============================================================================
183
184// 높이
185int height(TreeNode* root) {
186    if (!root) return 0;
187    return 1 + max(height(root->left), height(root->right));
188}
189
190// λ…Έλ“œ 개수
191int countNodes(TreeNode* root) {
192    if (!root) return 0;
193    return 1 + countNodes(root->left) + countNodes(root->right);
194}
195
196// κ· ν˜• 검사
197bool isBalanced(TreeNode* root) {
198    if (!root) return true;
199
200    int leftH = height(root->left);
201    int rightH = height(root->right);
202
203    return abs(leftH - rightH) <= 1 &&
204           isBalanced(root->left) &&
205           isBalanced(root->right);
206}
207
208// BST μœ νš¨μ„± 검사
209bool isValidBST(TreeNode* root, long long minVal = LLONG_MIN, long long maxVal = LLONG_MAX) {
210    if (!root) return true;
211
212    if (root->val <= minVal || root->val >= maxVal)
213        return false;
214
215    return isValidBST(root->left, minVal, root->val) &&
216           isValidBST(root->right, root->val, maxVal);
217}
218
219// =============================================================================
220// 5. LCA (Lowest Common Ancestor)
221// =============================================================================
222
223// 일반 이진 트리의 LCA
224TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
225    if (!root || root == p || root == q) return root;
226
227    TreeNode* left = lowestCommonAncestor(root->left, p, q);
228    TreeNode* right = lowestCommonAncestor(root->right, p, q);
229
230    if (left && right) return root;
231    return left ? left : right;
232}
233
234// BST의 LCA
235TreeNode* lcaBST(TreeNode* root, TreeNode* p, TreeNode* q) {
236    while (root) {
237        if (p->val < root->val && q->val < root->val)
238            root = root->left;
239        else if (p->val > root->val && q->val > root->val)
240            root = root->right;
241        else
242            return root;
243    }
244    return nullptr;
245}
246
247// =============================================================================
248// 6. 경둜 ν•©
249// =============================================================================
250
251// λ£¨νŠΈμ—μ„œ λ¦¬ν”„κΉŒμ§€ 합이 target인 경둜 쑴재 μ—¬λΆ€
252bool hasPathSum(TreeNode* root, int targetSum) {
253    if (!root) return false;
254
255    if (!root->left && !root->right)
256        return targetSum == root->val;
257
258    return hasPathSum(root->left, targetSum - root->val) ||
259           hasPathSum(root->right, targetSum - root->val);
260}
261
262// λͺ¨λ“  경둜 μ°ΎκΈ°
263void pathSumHelper(TreeNode* root, int sum, vector<int>& path, vector<vector<int>>& result) {
264    if (!root) return;
265
266    path.push_back(root->val);
267
268    if (!root->left && !root->right && sum == root->val) {
269        result.push_back(path);
270    } else {
271        pathSumHelper(root->left, sum - root->val, path, result);
272        pathSumHelper(root->right, sum - root->val, path, result);
273    }
274
275    path.pop_back();
276}
277
278vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
279    vector<vector<int>> result;
280    vector<int> path;
281    pathSumHelper(root, targetSum, path, result);
282    return result;
283}
284
285// =============================================================================
286// ν…ŒμŠ€νŠΈ
287// =============================================================================
288
289void printVector(const vector<int>& v) {
290    cout << "[";
291    for (size_t i = 0; i < v.size(); i++) {
292        cout << v[i];
293        if (i < v.size() - 1) cout << ", ";
294    }
295    cout << "]";
296}
297
298int main() {
299    cout << "============================================================" << endl;
300    cout << "νŠΈλ¦¬μ™€ BST 예제" << endl;
301    cout << "============================================================" << endl;
302
303    // ν…ŒμŠ€νŠΈ 트리 생성
304    //       4
305    //      / \
306    //     2   6
307    //    / \ / \
308    //   1  3 5  7
309    TreeNode* root = new TreeNode(4);
310    root->left = new TreeNode(2);
311    root->right = new TreeNode(6);
312    root->left->left = new TreeNode(1);
313    root->left->right = new TreeNode(3);
314    root->right->left = new TreeNode(5);
315    root->right->right = new TreeNode(7);
316
317    // 1. 트리 순회
318    cout << "\n[1] 트리 순회" << endl;
319    vector<int> pre, in, post;
320    preorder(root, pre);
321    inorder(root, in);
322    postorder(root, post);
323
324    cout << "    μ „μœ„: ";
325    printVector(pre);
326    cout << endl;
327    cout << "    μ€‘μœ„: ";
328    printVector(in);
329    cout << endl;
330    cout << "    ν›„μœ„: ";
331    printVector(post);
332    cout << endl;
333
334    // 2. 레벨 순회
335    cout << "\n[2] 레벨 순회" << endl;
336    auto levels = levelOrder(root);
337    for (size_t i = 0; i < levels.size(); i++) {
338        cout << "    레벨 " << i << ": ";
339        printVector(levels[i]);
340        cout << endl;
341    }
342
343    // 3. BST μ—°μ‚°
344    cout << "\n[3] BST μ—°μ‚°" << endl;
345    BST bst;
346    bst.insert(50);
347    bst.insert(30);
348    bst.insert(70);
349    bst.insert(20);
350    bst.insert(40);
351
352    cout << "    μ‚½μž…: 50, 30, 70, 20, 40" << endl;
353    cout << "    검색 30: " << (bst.search(30) ? "있음" : "μ—†μŒ") << endl;
354    cout << "    검색 60: " << (bst.search(60) ? "있음" : "μ—†μŒ") << endl;
355
356    // 4. 트리 속성
357    cout << "\n[4] 트리 속성" << endl;
358    cout << "    높이: " << height(root) << endl;
359    cout << "    λ…Έλ“œ 수: " << countNodes(root) << endl;
360    cout << "    κ· ν˜• μ—¬λΆ€: " << (isBalanced(root) ? "예" : "μ•„λ‹ˆμ˜€") << endl;
361    cout << "    μœ νš¨ν•œ BST: " << (isValidBST(root) ? "예" : "μ•„λ‹ˆμ˜€") << endl;
362
363    // 5. LCA
364    cout << "\n[5] μ΅œμ†Œ 곡톡 쑰상 (LCA)" << endl;
365    TreeNode* lca = lowestCommonAncestor(root, root->left->left, root->left->right);
366    cout << "    LCA(1, 3) = " << lca->val << endl;
367    lca = lowestCommonAncestor(root, root->left, root->right);
368    cout << "    LCA(2, 6) = " << lca->val << endl;
369
370    // 6. 경둜 ν•©
371    cout << "\n[6] 경둜 ν•©" << endl;
372    cout << "    ν•© 7 경둜 쑴재: " << (hasPathSum(root, 7) ? "예" : "μ•„λ‹ˆμ˜€") << endl;
373    cout << "    ν•© 15 경둜 쑴재: " << (hasPathSum(root, 15) ? "예" : "μ•„λ‹ˆμ˜€") << endl;
374
375    // 7. λ³΅μž‘λ„ μš”μ•½
376    cout << "\n[7] λ³΅μž‘λ„ μš”μ•½" << endl;
377    cout << "    | μ—°μ‚°       | 평균      | μ΅œμ•…      |" << endl;
378    cout << "    |------------|-----------|-----------|" << endl;
379    cout << "    | 검색       | O(log n)  | O(n)      |" << endl;
380    cout << "    | μ‚½μž…       | O(log n)  | O(n)      |" << endl;
381    cout << "    | μ‚­μ œ       | O(log n)  | O(n)      |" << endl;
382    cout << "    | 순회       | O(n)      | O(n)      |" << endl;
383
384    cout << "\n============================================================" << endl;
385
386    return 0;
387}