트리/힙/그래프(1) - 트리

• 비선형 자료 구조 사용해야 하는 경우 판별
• 데이터 표현과 문제 해결을 위해 트리 / 그래프 구조 구현하여 사용
• 다양한 방법으로 트리 순회
• 주어진 상황에 맞게 다양한 방법으로 그래프 표현

1. 비선형 문제

1) 계층적 문제

• 조직도와 같이 계층적 속성을 가지는 문제
• 트리라는 자료 구조를 사용
• 데이터가 저장된 노드와 노드와 노드를 잇는 엣지로 구성

2) 순환 종속성

• 친구관계도와 같이 그래프로 표현
• 노드와 엣지로 구성

2. 트리

1) 연습 문제 7: 조직도 구조 만들기

#include <iostream>
#include <queue>

struct node
{
	std::string position;
	node* first;
	node* second;
};

struct org_tree
{
	node* root;

	static org_tree create_org_structure(const std::string& pos)
	{
		org_tree tree;
		tree.root = new node {pos, NULL, NULL};
		return tree;
	}

	static node* find(node* root, const std::string& value)
	{
		if (root == NULL)
			return NULL;

		if (root->position == value)
			return root;

		auto firstFound = org_tree::find(root->first, value);

		if (firstFound != NULL)
			return firstFound;

		return org_tree::find(root->second, value);
	}

	bool addSubordinate(const std::string& manager, const std::string& subordinate)
	{
		auto managerNode = org_tree::find(root, manager);

		if (!managerNode)
		{
			std::cout << manager << "을(를) 찾을 수 없습니다: " << std::endl;
			return false;
		}

		if (managerNode->first && managerNode->second)
		{
			std::cout << manager << " 아래에 " << subordinate << "를 추가할 수 없습니다." << std::endl;
			return false;
		}

		if (!managerNode->first)
			managerNode->first = new node {subordinate, NULL, NULL};
		else
			managerNode->second = new node {subordinate, NULL, NULL};

		std::cout << manager << " 아래에 " << subordinate << "를 추가했습니다." << std::endl;

		return true;
	}
};

int main()
{
	auto tree = org_tree::create_org_structure("CEO");

	tree.addSubordinate("CEO", "부사장");
	tree.addSubordinate("부사장", "IT부장");
	tree.addSubordinate("부사장", "마케팅부장");
	tree.addSubordinate("IT부장", "보안팀장");
	tree.addSubordinate("IT부장", "앱개발팀장");
	tree.addSubordinate("마케팅부장", "물류팀장");
	tree.addSubordinate("마케팅부장", "홍보팀장");
	tree.addSubordinate("부사장", "재무부장");
}
// 해당 연습문제에서는 노드를 동적 생성한 이후 해제하지 않아 메모리 릭이 발생

2) 트리 순회

(1) 전위 순회

• 현재 노드를 방문하고 그다음은 현재 노드의 왼쪽 하위 노드를 마지막으로는 오른쪽 하위노드를 재귀적인 방식으로 방문
• 루트 노드에서만 수행하는 것이 아닌 루트 노드 아래의 서브 트리에 모두 해당

static void preOrder(node* start)
{
	if(!start)
		return ;
	std::cout<<start->position<<",";
	preOrder(start->first);
	preOrder(start->second);
}

(2) 중위 순회

• 왼쪽 노드를 제일 먼저 방문하고 그 다음에는 현재 노드 마지막으로 오른쪽 노드 방문

static void inOrder(node* start)
{
	if(!start)
		return ;
	inOrder(start->first);
	std::cout<<start->position<<",";
	inOrder(start->second);
}

(3) 후위 순회

• 두 자식 노드를 먼저 방문한 후 현재 노드 방문

static void postOrder(node* start)
{
	if(!start)
		return ;
	postOrder(start->first);
	postOrder(start->second);
	std::cout<<start->position<<",";

}

(4) 레벨 순서 순회

• 트리의 맨 위 레벨부터 아래 레벨까지 왼쪽 노드에서 오른쪽 노드 순서로 방문

3) 연습 문제 8: 레벨 순서 순회 구현하기

#include <iostream>
#include <queue>

struct node
{
	std::string position;
	node* first;
	node* second;
};

struct org_tree
{
	node* root;

	static org_tree create_org_structure(const std::string& pos)
	{
		org_tree tree;
		tree.root = new node {pos, NULL, NULL};
		return tree;
	}

	static node* find(node* root, const std::string& value)
	{
		if (root == NULL)
			return NULL;

		if (root->position == value)
			return root;

		auto firstFound = org_tree::find(root->first, value);

		if (firstFound != NULL)
			return firstFound;

		return org_tree::find(root->second, value);
	}

	bool addSubordinate(const std::string& manager, const std::string& subordinate)
	{
		auto managerNode = org_tree::find(root, manager);

		if (!managerNode)
		{
			std::cout << manager << "을(를) 찾을 수 없습니다: " << std::endl;
			return false;
		}

		if (managerNode->first && managerNode->second)
		{
			std::cout << manager << " 아래에 " << subordinate << "를 추가할 수 없습니다." << std::endl;
			return false;
		}

		if (!managerNode->first)
			managerNode->first = new node {subordinate, NULL, NULL};
		else
			managerNode->second = new node {subordinate, NULL, NULL};

		std::cout << manager << " 아래에 " << subordinate << "를 추가했습니다." << std::endl;

		return true;
	}
	
	static void preOrder(node* start)
	{
		if (!start)
			return;

		std::cout << start->position << ", ";
		preOrder(start->first);
		preOrder(start->second);
	}

	static void inOrder(node* start)
	{
		if (!start)
			return;

		inOrder(start->first);
		std::cout << start->position << ", ";
		inOrder(start->second);
	}

	static void postOrder(node* start)
	{
		if (!start)
			return;

		postOrder(start->first);
		postOrder(start->second);
		std::cout << start->position << ", ";
	}

	static void levelOrder(node* start)
	{
		if (!start)
			return;

		std::queue<node*> q;
		q.push(start);

		while (!q.empty())
		{
			int size = q.size();
			for (int i = 0; i < size; i++)
			{
				auto current = q.front();
				q.pop();

				std::cout << current->position << ", ";
				if (current->first)
					q.push(current->first);
				if (current->second)
					q.push(current->second);
			}

			std::cout << std::endl;
		}
	}
};

int main()
{
	auto tree = org_tree::create_org_structure("CEO");

	tree.addSubordinate("CEO", "부사장");
	tree.addSubordinate("부사장", "IT부장");
	tree.addSubordinate("부사장", "마케팅부장");
	tree.addSubordinate("IT부장", "보안팀장");
	tree.addSubordinate("IT부장", "앱개발팀장");
	tree.addSubordinate("마케팅부장", "물류팀장");
	tree.addSubordinate("마케팅부장", "홍보팀장");
	tree.addSubordinate("부사장", "재무부장");

//	org_tree::preOrder(tree.root); std::cout << std::endl;
//	org_tree::inOrder(tree.root); std::cout << std::endl;
//	org_tree::postOrder(tree.root); std::cout << std::endl;

	org_tree::levelOrder(tree.root);
}

3. 다양한 트리 구조

1) 이진 검색 트리 (Binary Search Tree)

• 부모 노드의 값 ≥ 왼쪽 자식 노드의 값 부모 노드의 값 ≤ 오른쪽 자식 노드의 값
• 부모 노드보다 작은 원소 무조건 왼쪽에 위치, 크거나 같은 원소는 오른쪽에 위치

(1) BST에서 원소 검색

• 이진 검색 트리의 속성을 이용하여 검색
• 원소 검색 시 트리의 모든 원소를 방문하지 않아도 됨

(2) BST에서 새 원소 삽입하기

• 먼저 원소가 삽입될 위치의 부모 노드 확인 (원소 검색과 유사)
• 부모 노드 밑에 삽입

(3) BST에서 원소 삭제하기

• 삭제할 노드 찾기
• 자식 노드가 없는 경우 : 단순히 해당 노드 삭제
• 자식 노드가 하나만 있는 경우 : 노드 삭제 후, 부모 노드의 포인터가 해당 자식 노드를 가르키도록 조정
• 자식 노드가 두 개 있는 경우 : 노드 삭제 후, 현재 노드를 후속 노드로 대체 → 후속 노드 (자식 노드 다음으로 큰 숫자를 가진 노드)

2) 트리 연산의 시간 복잡도

• 이론적으로는 O(log N) 이지만 트리의 모양에 따라 바뀔 수 있어 정확하진 않음

3) 연습문제 9: BST 구현하기

#include <iostream>

struct node
{
	int data;
	node* left;
	node* right;
};

struct bst
{
	node* root = nullptr;

	node* find(int value)
	{
		return find_impl(root, value);
	}

private:
	node* find_impl(node* current, int value)
	{
		if (!current)
		{
			std::cout << std::endl;
			return NULL;
		}

		if (current->data == value)
		{
			std::cout << value << "을(를) 찾았습니다." << std::endl;
			return current;
		}

		if (value < current->data) // value 값이 현재 노드 왼쪽에 있는 경우
		{
			std::cout << current->data << "에서 왼쪽으로 이동: ";
			return find_impl(current->left, value);
		}

		// value 값이 현재 노드 오른쪽에 있는 경우
		std::cout << current->data << "에서 오른쪽으로 이동: ";
		return find_impl(current->right, value);
	}

public:
	void insert(int value)
	{
		if (!root)
			root = new node {value, NULL, NULL};
		else
			insert_impl(root, value);
	}

private:
	void insert_impl(node* current, int value)
	{
		if (value < current->data)
		{
			if (!current->left)
				current->left = new node {value, NULL, NULL};
			else
				insert_impl(current->left, value);
		}
		else
		{
			if (!current->right)
				current->right = new node {value, NULL, NULL};
			else
				insert_impl(current->right, value);
		}
	}

public:
	void inorder()
	{
		inorder_impl(root);
	}

private:
	void inorder_impl(node* start)
	{
		if (!start)
			return;

		inorder_impl(start->left);			// 왼쪽 하위 트리 방문
		std::cout << start->data << " ";	// 현재 노드 출력
		inorder_impl(start->right);			// 오른쪽 하위 트리 방문
	}

public:
	node* successor(node* start)
	{
		auto current = start->right;
		while (current && current->left)
			current = current->left;
		return current;
	}

	void deleteValue(int value)
	{
		root = delete_impl(root, value);
	}

private:
	node* delete_impl(node* start, int value)
	{
		if (!start)
			return NULL;

		if (value < start->data)
			start->left = delete_impl(start->left, value);
		else if (value > start->data)
			start->right = delete_impl(start->right, value);
		else
		{
			if (!start->left) // 자식 노드가 전혀 없거나, 왼쪽 자식 노드만 없는 경우
			{
				auto tmp = start->right;
				delete start;
				return tmp;
			}

			if (!start->right) // 오른쪽 자식 노드만 없는 경우
			{
				auto tmp = start->left;
				delete start;
				return tmp;
			}

			// 자식 노드가 둘 다 있는 경우
			auto succNode = successor(start);
			start->data = succNode->data;

			// 오른쪽 하위 트리에서 후계자(successor)를 찾아 삭제
			start->right = delete_impl(start->right, succNode->data);
		}

		return start;
	}
};

int main()
{
	bst tree;
	tree.insert(12);
	tree.insert(10);
	tree.insert(20);
	tree.insert(8);
	tree.insert(11);
	tree.insert(15);
	tree.insert(28);
	tree.insert(4);
	tree.insert(2);

	std::cout << "중위 순회: ";
	tree.inorder(); // BST의 모든 원소를 오름차순으로 출력합니다.
	std::cout << std::endl;

	tree.deleteValue(12);
	std::cout << "12를 삭제한 후 중위 순회: ";
	tree.inorder(); // BST의 모든 원소를 오름차순으로 출력합니다.
	std::cout << std::endl;
	
	if (tree.find(12))
		std::cout << "원소 12는 트리에 있습니다." << std::endl;
	else
		std::cout << "원소 12는 트리에 없습니다." << std::endl;
}

4) 균형 트리

• 이진 검색 트리에서 한 쪽으로 편향될 경우 검색을 하는 데 시간이 소요가 큼
• 따라서 트리의 높이를 최적화하여 시간 복잡도를 최적화함
• 트리의 균형을 잡는 방법은 AVL트리, 레드-블랙 트리 등
• AVL 트리 : BST의 속성은 유지하면서 트리 높이의 균형을 위해 약간의 회전 수행

5) N-항 트리

• 각 노드에 N개의 자식을 가질 수 있음

struct nTree
{
	int data;
	std::vector<nTree*> children;
};

• 컴퓨터 파일 시스템 구조 / 컴파일러 등에서 사용하고 있음

6) 실습 문제 4 : 파일 시스템 자료 구조 만들기

#include <iostream>
#include <vector>
#include <algorithm>

struct n_ary_node
{
	std::string name;
	bool is_dir;
	std::vector<n_ary_node*> children;
};

struct file_system
{
	using node = n_ary_node;
	using node_ptr = node*;

private:
	node_ptr root;
	node_ptr cwd;

public:
	file_system()
	{
		root = new node {"/", true, {}};
		cwd = root; // 처음에는 루트를 현재 디렉토리로 설정
	}

	node_ptr find(const std::string& path)
	{
		if (path[0] == '/') // 절대 경로
		{
			return find_impl(root, path.substr(1));
		}
		else // 상대 경로
		{
			return find_impl(cwd, path);
		}
	}

private:
	node_ptr find_impl(node_ptr directory, const std::string& path)
	{
		if (path.empty())
			return directory;
		auto sep = path.find('/');
		std::string current_path = sep == std::string::npos ? path : path.substr(0, sep);
		std::string rest_path = sep == std::string::npos ? "" : path.substr(sep + 1);
		auto found = std::find_if(directory->children.begin(), directory->children.end(),
			[&](const node_ptr child) {
				return child->name == current_path;
			});
		if (found != directory->children.end())
		{
			return find_impl(*found, rest_path);
		}
		return NULL;
	}

public:
	bool add(const std::string& path, bool is_dir)
	{
		if (path[0] == '/')
		{
			return add_impl(root, path.substr(1), is_dir);
		}
		else
		{
			return add_impl(cwd, path, is_dir);
		}
	}

private:
	bool add_impl(node_ptr directory, const std::string& path, bool is_dir)
	{
		if (not directory->is_dir)
		{
			std::cout << directory->name << "은(는) 파일입니다." << std::endl;
			return false;
		}

		auto sep = path.find('/');

		// path에 '/'가 없는 경우
		if (sep == std::string::npos)
		{
			auto found = std::find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child) {
				return child->name == path;
				});

			if (found != directory->children.end())
			{
				std::cout << directory->name << "에 이미 " << path << " 이름의 파일/디렉토리가 있습니다." << std::endl;
				return false;
			}

			directory->children.push_back(new node {path, is_dir, {}});
			return true;
		}

		// path에 '/'가 있는 경우, 즉, 디렉토리 이름을 포함하고 있는 경우.
		std::string next_dir = path.substr(0, sep);
		auto found = std::find_if(directory->children.begin(), directory->children.end(), [&](const node_ptr child) {
			return child->name == next_dir && child->is_dir;
			});

		if (found != directory->children.end())
		{
			return add_impl(*found, path.substr(sep + 1), is_dir);
		}

		// path에 디렉토리 이름이 포함되어 있지만, 해당 디렉토리가 없는 경우.
		std::cout << directory->name << "에 " << next_dir << " 이름의 디렉토리가 없습니다." << std::endl;
		return false;
	}

public:
	bool change_dir(const std::string& path)
	{
		auto found = find(path);
		if (found && found->is_dir)
		{
			cwd = found;
			std::cout << "현재 디렉토리를 " << cwd->name << "로 이동합니다." << std::endl;
			return true;
		}

		std::cout << path << " 경로를 찾을 수 없습니다." << std::endl;
		return false;
	}

public:
	void show_path(const std::string& path)
	{
		auto found = find(path);
		if (not found)
		{
			std::cout << path << " 경로가 존재하지 않습니다." << std::endl;
			return;
		}

		if (found->is_dir)
		{
			for (auto child : found->children)
			{
				std::cout << (child->is_dir ? "d " : "- ") << child->name << std::endl;
			}
		}
		else
		{
			std::cout << "- " << found->name << std::endl;
		}
	}
};

int main()
{
	file_system fs;
	fs.add("usr", true);       // "/"에 usr 디렉토리 추가
	fs.add("etc", true);       // "/"에 etc 디렉토리 추가
	fs.add("var", true);       // "/"에 var 디렉토리 추가
	fs.add("tmp_file", false); // "/"에 tmp_file 파일 추가

	std::cout << "\\"/\\"의 파일/디렉토리 목록:" << std::endl;
	fs.show_path("/");        // "/"의 파일/디렉토리 목록 출력

	std::cout << std::endl;
	fs.change_dir("usr");
	fs.add("gilbut", true);
	fs.add("gilbut/Downloads", true);
	fs.add("gilbut/Downloads/newFile.cpp", false);

	std::cout << "현재 디렉토리에서 usr의 파일/디렉토리 목록: " << std::endl;
	fs.show_path("usr"); // 현재 디렉토리에는 usr 디렉토리가 없으므로 정상적으로 출력하지 못합니다.

	std::cout << "\\"/usr\\"의 파일/디렉토리 목록:" << std::endl;
	fs.show_path("/usr");

	std::cout << "\\"/usr/gilbut/Downloads\\"의 파일/디렉토리 목록" << std::endl;
	fs.show_path("/usr/gilbut/Downloads");
}

 

 

출처 : 코딩 테스트를 위한 자료 구조와 알고리즘 with C++ (길벗)