[자료구조] 트리(Tree) - Tree의 Balance 확인하기

아래의 영상을 바탕으로 작성되었습니다. 좋은영상 감사합니다.
[자료구조 알고리즘] Tree의 Balance 확인하기
https://youtu.be/-m154rqFQng

(1) .h

코드1

	#pragma once
	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <queue>
	using namespace std;
	class Node
	{
	public:
	int data;
	Node* left, * right;
	Node(int data) {
	this->data = data;
	this->left = this->right = NULL;
	}
	};
	class Level
	{
	public:
	int min = INT_MAX;
	int max = INT_MIN;
	};
	class Tree
	{
	private:
	Node* root = NULL;
	int min = INT_MIN;
	vector<vector<Node*>> levels;
	public:
	Tree(vector<int> a)
	{
	root = bst(a, 0, a.size() - 1);
	}
	Node* bst(vector<int> a, int start, int end)
	{
	if (start <= end)
	{
	int mid = (start + end) / 2;
	Node* newNode = new Node(a[mid]);
	newNode->left = bst(a, start, mid - 1);
	newNode->right = bst(a, mid + 1, end);
	return newNode;
	}
	return NULL;
	}
	//밸런스체크1 : 시간복잡도 O(nlogn)
	bool isBalanced()
	{
	return isBalanced(root);
	}
	bool isBalanced(Node* node)
	{
	//재귀 돌리는데, 각 서브트리의 길이를 잰다
	if (node == NULL) return true;
	int heightDiff = getHeight(node->left) - getHeight(node->right);
	if (abs(heightDiff) > 1) return false;
	else {
	return isBalanced(node->left) && isBalanced(node->right);
	}
	}
	int getHeight(Node* node)
	{
	if (node == NULL) return -1;
	return max(getHeight(node->left), getHeight(node->right)) + 1;
	}
	//밸런스체크2 : 시간복잡도 O(n)
	bool isBalanced2()
	{
	//checkHeight리턴값이 min아니면 true반환
	return checkHeight(root) != min;
	}
	int checkHeight(Node* node)
	{
	if (node == NULL) return -1;
	int left = checkHeight(node->left);
	int right = checkHeight(node->right);
	if (left == min || right == min) return min;
	int heightDiff = left - right;
	if (abs(heightDiff) > 1) return min;
	else {
	return max(left, right) + 1;
	}
	}
	//좀더 엄격한 밸런스체크(양 서브트리의 길이 차가 2이상이면 언밸런스)
	bool isBalanced3()
	{
	return isBalanced3(root);
	}
	bool isBalanced3(Node* node)
	{
	Level* obj = new Level;
	checkBalanced(node, obj, 0);
	if (abs(obj->min - obj->max) > 1) return false;
	else return true;
	}
	void checkBalanced(Node* node, Level* obj, int level)
	{
	if (node == NULL)
	{
	if (level < obj->min) obj->min = level;
	else if (level > obj->max) obj->max = level;
	return;
	}
	checkBalanced(node->left, obj, level + 1);
	checkBalanced(node->right, obj, level + 1);
	}
	void bstToList()
	{
	levels = bstToList(root);
	}
	vector<vector<Node*>> bstToList(Node* node)
	{
	vector<vector<Node*>> lists;
	vector<Node*> current;
	if (node != NULL) current.push_back(node);
	lists.push_back(current);
	while (!current.empty())
	{
	vector<Node*> parent = current;
	current.clear();
	for (int i = 0; i < parent.size(); i++)
	{
	if (parent[i]->left) current.push_back(parent[i]->left);
	if (parent[i]->right) current.push_back(parent[i]->right);
	}
	if (!current.empty()) lists.push_back(current);
	}
	return lists;
	}
	void print()//레벨별 데이터값 출력
	{
	for (int i = 0; i < levels.size(); i++)
	{
	for (int j = 0; j < levels[i].size(); j++)
	cout << levels[i][j]->data << " ";
	cout << endl;
	}
	}
	};

view raw 트리_Tree의 Balance 확인하기.h hosted with ❤ by GitHub

(2) .cpp

	#include "header.h"
	int main() {
	//정렬 되어있는 배열을 넣는다
	Tree* t = new Tree({ 0,1,2,3,4,5,6,7,8,9});
	t->bstToList();
	t->print();
	(t->isBalanced() == true) ? puts("balanced") : puts("unbalanced");
	(t->isBalanced2() == true) ? puts("balanced") : puts("unbalanced");
	(t->isBalanced3()==true) ? puts("balanced") : puts("unbalanced");
	return 0;
	}

view raw 트리_Tree의 Balance 확인하기.cpp hosted with ❤ by GitHub