[자료구조] 트리 (Tree)

트리 (Tree) 란?

• 트리는 계층적인 구조를 가진 자료구조로, 부모와 자식 노드 간의 관계를 나타낸다.
• 데이터 구조화가 용이해 파일 시스템, 계층적 데이터 저장 등에 사용 가능.

트리 (Tree)

장단점

장점

• 데이터 검색, 삽입, 삭제가 효율적 (특히 이진 탐색 트리의 경우).
• 데이터 구조화가 용이해 파일 시스템, 계층적 데이터 저장 등에 사용 가능.

단점

• 균형이 맞지 않을 경우 성능 저하 가능.
• 구현이 복잡하고 노드 추가 시 메모리 오버헤드 발생

트리 (Tree)는 대충보면 링크드리스트 (Linked List)랑 구조가 비슷하다고 생각할수도 있는데.

트리 (Tree)에 경우에는 하나의 부모가 여러개의 자식을 가지고 있고, 최상위의 노드의 경우에는 부모가 따로 없는 구조를 가지고있다.

구현

#include <map> 을 활용한 다중계층 트리구현

#include <iostream>
#include <string>
#include <map>

class TreeNode
{
private:
	std::string data;
	std::map<std::string, std::shared_ptr<TreeNode> > children;
public:
	TreeNode(const std::string& value) : data(value) {};
	~TreeNode() {};

	std::string getData() { return data; }
	std::map<std::string, std::shared_ptr<TreeNode> > getChildren() { return children; }

	std::shared_ptr<TreeNode> getChild(const std::string& childName) {
		return children[childName];
	}

	void addChild(const std::string& childName) {
		children[childName] = std::make_shared<TreeNode>(childName);
	}

};

void printTree(const std::shared_ptr<TreeNode>& node, int level = 0) {
	if (!node) return;

	std::cout << std::string(level * 2, ' ') << node->getData() << std::endl;
	
	for (const auto& child : node->getChildren()) {
		printTree(child.second, level + 1);
	}
}

int main() {

	auto root = std::make_shared<TreeNode>("A");

	root->addChild("B");
	root->addChild("C");

	root->getChild("B")->addChild("D");
	root->getChild("B")->addChild("E");

	root->getChild("C")->addChild("F");
	root->getChild("C")->addChild("G");
	root->getChild("C")->addChild("H");

	printTree(root);

	return 0;
}

• 이진 트리, AVL 트리, 레드-블랙 트리 등 여러 변형 존재한다.