[Data Structure] 트리(Tree)
트리(Tree) 란?
트리는 계층 구조를 나타내는 데 사용하는 자료구조로, 노드(node)와 간선(edge)으로 이루어져 있습니다. 각 노드는 부모 노드(parent node)와 자식 노드(child node)를 가질 수 있으며, 최상위 노드를 루트 노드(root node)라고 합니다. 트리는 다음과 같은 특징을 가지고 있습니다.
- 계층 구조: 데이터가 부모-자식 관계를 가지며 계층적으로 구성됩니다. 마치 나무처럼, 뿌리에서 시작하여 가지가 뻗어나가는 형태로 데이터를 관리합니다.
- 비선형 구조: 데이터가 선형으로 연결되지 않고, 여러 개의 자식을 가질 수 있습니다. 마치 조직도처럼, 각 부서가 여러 개의 하위 부서를 가질 수 있습니다.
- 순환 구조 없음: 노드를 거쳐 자기 자신으로 돌아오는 순환 구조가 존재하지 않습니다. 마치 미로처럼, 왔던 길을 다시 돌아가지 않습니다..
트리의 종류
-
이진 트리(Binary Tree): 각 노드가 최대 2개의 자식 노드(왼쪽 자식, 오른쪽 자식)를 갖는 트리입니다. 이진 트리는 검색, 정렬 등 다양한 알고리즘에 사용됩니다. 마치 두 갈래 길처럼, 각 노드에서 왼쪽 또는 오른쪽 자식 노드로 이동할 수 있습니다.
-
B-트리(B-tree): 각 노드가 2개 이상의 자식 노드를 가질 수 있는 트리입니다. B-트리는 데이터베이스 인덱싱 등 대용량 데이터 관리에 효율적으로 사용됩니다. 마치 여러 갈래 길처럼, 각 노드에서 여러 개의 자식 노드로 이동할 수 있습니다.
-
힙 트리(Heap tree): 특정 규칙에 따라 부모-자식 관계가 결정되는 트리입니다. 힙 트리는 우선순위 큐(Priority Queue)를 구현하는 데 사용됩니다. 마치 계층 구조의 경기 토너먼트처럼, 각 노드의 값이 부모 노드보다 크거나 작습니다.
트리, 이진 트리, B-트리 차이점
- 자식 노드의 개수
- 트리 : 0개, 1개, 4~5개도 가능
- 이진 트리 : 최대 2개
- B-트리 : 2개 이상
- 데이터의 순서
- 트리 : 정렬되어 있지 않을 수 있음
- 이진 트리 : 정렬되어 있음
- B-트리 : 정렬되어 있음
- 메모리 효율성
- 트리 : 메모리 사용 효율성이 낮음
- 이진 트리 : 메모리 사용 효율성이 높음
- B-트리 : 메모리 사용 효율성이 높음
- 용도
- 트리 : 데이터의 저장 및 탐색에 사용 (시스템에서 파일의 구조를 저장, 인공 지능에서 탐색 및 검색 알고리즘 등)
- 이진 트리 : 데이터의 효율적인 검색 및 탐색에 사용됨 (데이터를 검색 및 정렬, 힙 구현, 게임에서 오브젝트 저장 등)
- B-트리 : 데이터베이스 및 파일 시스템에서 사용됨 (DB 또는 파일 시스템에서 데이터를 저장, 인공 지능에서 탐색 및 검색 알고리즘에 사용 등)
장단점
장점
- 계층 구조 표현: 데이터를 계층적으로 표현하여 데이터를 직관적으로 관리할 수 있습니다. 마치 파일 시스템처럼, 트리 구조를 통해 데이터를 폴더별로 정리할 수 있습니다.
- 효율적인 데이터 검색: 트리 탐색 알고리즘을 사용하여 데이터를 효율적으로 검색할 수 있습니다. 마치 책의 목차처럼, 트리를 통해 원하는 정보를 빠르게 찾을 수 있습니다.
- 다양한 알고리즘 활용: 트리 순회, 검색, 삽입, 삭제 등 다양한 알고리즘을 활용하여 데이터를 처리할 수 있습니다. 마치 연장 도구처럼, 트리는 다양한 알고리즘을 통해 데이터를 관리할 수 있습니다.
단점
- 메모리 사용량 증가: 노드의 개수가 많아질수록 메모리 사용량이 증가할 수 있습니다. 마치 큰 나무처럼, 트리는 많은 가지와 잎을 저장하기 위해 많은 메모리 공간이 필요합니다.
- 탐색 시간 증가: 트리의 깊이가 깊어질수록 탐색 시간이 증가할 수 있습니다. 마치 깊은 숲 속에서 길을 찾는 것처럼, 트리의 깊이가 깊어질수록 데이터를 찾는 데 시간이 오래 걸릴 수 있습니다.
- 구조 변경 어려움: 트리의 구조를 변경하려면 많은 노드를 수정해야 하므로 어려움이 있을 수 있습니다. 마치 건물의 구조를 변경하는 것처럼, 트리는 구조 변경이 쉽지 않습니다.
활용 분야
- 파일 시스템: 파일과 디렉터리 구조를 트리 형태로 표현합니다.
- 데이터베이스 인덱스: 데이터베이스의 데이터를 빠르게 검색하기 위해 트리 구조를 사용합니다.
- 인공 지능: 의사 결정 트리, 게임 AI 등 다양한 분야에서 트리 구조를 활용합니다.
- 컴퓨터 네트워크: 네트워크 토폴로지를 트리 형태로 표현합니다.
문제점&주의사항
-
메모리 관리: 트리의 노드 수가 많아지면 메모리 사용량이 증가하므로 메모리 관리에 주의해야 합니다. 더 이상 사용하지 않는 노드는 메모리에서 해제하여 메모리 누수를 방지해야 합니다. 마치 사용한 컵을 깨끗이 씻는 것처럼, 트리를 사용 후에는 메모리를 정리해야 합니다.
-
탐색 효율성: 트리의 깊이가 깊어지면 탐색 시간이 증가할 수 있습니다. 따라서 트리의 균형을 유지하거나 효율적인 탐색 알고리즘을 사용하는 것이 좋습니다. 마치 지도를 보면서 길을 찾는 것처럼, 트리를 탐색할 때는 효율적인 방법을 선택해야 합니다.
-
구조 변경: 트리의 구조를 변경하려면 많은 노드를 수정해야 하므로 신중하게 결정해야 합니다. 마치 건물의 구조를 변경하는 것처럼, 트리는 구조 변경이 쉽지 않습니다.
예제
[기본 트리]
using System;
using System.Collections.Generic;
class Node
{
public string data {get; set;}
public List<Node> children {get; set;}
public Node(string _data)
{
data = _data;
children = new List<Node>();
}
}
class Tree
{
static Node CreateTree()
{
Node root = new Node("root");
Node child_00 = new Node("child_00");
Node child_01 = new Node("child_01");
root.children.Add(child_00);
root.children.Add(child_01);
return root;
}
static void Main(string[] args)
{
Node tree = CreateTree();
Console.WriteLine("tree data : " + tree.data);
Console.WriteLine("tree children : " + tree.children);
foreach(Node child in tree.children)
{
Console.WriteLine("output : " + child.data);
}
}
}
[이진 트리(Binary Tree)]
using System;
using System.Collections.Generic;
class Node
{
public int data {get; set;}
public Node left {get; set;}
public Node right {get; set;}
public Node(int _data)
{
data = _data;
left = null;
right = null;
}
}
class Tree
{
static Node CreateTree()
{
Node root = new Node(0);
Node left = new Node(1);
Node right = new Node(2);
root.left = left;
root.right = right;
left.left = new Node(3);
left.right = new Node(5);
right.left = new Node(7);
right.right = new Node(9);
return root;
}
static void Main(string[] args)
{
Node tree = CreateTree();
Preorder(tree);
Console.WriteLine();
Inorder(tree);
Console.WriteLine();
Postorder(tree);
Console.WriteLine();
}
static void Preorder(Node _node)
{
if(_node == null) return;
Console.WriteLine("Preorder : " + _node.data);
Preorder(_node.left);
Preorder(_node.right);
}
static void Inorder(Node _node)
{
if(_node == null) return;
Inorder(_node.left);
Console.WriteLine("Inorder : " + _node.data);
Inorder(_node.right);
}
static void Postorder(Node _node)
{
if(_node == null) return;
Postorder(_node.left);
Postorder(_node.right);
Console.WriteLine("Postorder : " + _node.data);
}
}
[B-트리]
using System;
using System.Collections.Generic;
// B-트리 노드 클래스
public class BTreeNode
{
public int[] Keys; // 키 배열
public int Degree; // 최소 차수
public BTreeNode[] Children; // 자식 노드 배열
public bool IsLeaf; // 리프 노드 여부
public int KeyCount; // 현재 키 개수
public BTreeNode(int degree, bool isLeaf)
{
Degree = degree;
IsLeaf = isLeaf;
Keys = new int[2 * degree - 1]; // 최대 키 개수
Children = new BTreeNode[2 * degree]; // 최대 자식 노드 개수
KeyCount = 0;
}
public void Traverse()
{
int i;
for (i = 0; i < KeyCount; i++)
{
if (!IsLeaf)
{
Children[i].Traverse();
}
Console.Write(Keys[i] + " ");
}
if (!IsLeaf)
{
Children[i].Traverse();
}
}
public BTreeNode Search(int key)
{
int i = 0;
while (i < KeyCount && key > Keys[i])
{
i++;
}
if (Keys[i] == key)
{
return this;
}
if (IsLeaf)
{
return null;
}
return Children[i].Search(key);
}
}
// B-트리 클래스
public class BTree
{
private BTreeNode root;
private int degree;
public BTree(int degree)
{
this.degree = degree;
root = null;
}
public void Traverse()
{
if (root != null)
{
root.Traverse();
}
}
public BTreeNode Search(int key)
{
return root == null ? null : root.Search(key);
}
public void Insert(int key)
{
if (root == null)
{
root = new BTreeNode(degree, true);
root.Keys[0] = key;
root.KeyCount = 1;
}
else
{
if (root.KeyCount == 2 * degree - 1)
{
BTreeNode newRoot = new BTreeNode(degree, false);
newRoot.Children[0] = root;
SplitChild(newRoot, 0, root);
int i = newRoot.Keys[0] < key ? 1 : 0;
InsertNonFull(newRoot.Children[i], key);
root = newRoot;
}
else
{
InsertNonFull(root, key);
}
}
}
private void InsertNonFull(BTreeNode node, int key)
{
int i = node.KeyCount - 1;
if (node.IsLeaf)
{
while (i >= 0 && node.Keys[i] > key)
{
node.Keys[i + 1] = node.Keys[i];
i--;
}
node.Keys[i + 1] = key;
node.KeyCount++;
}
else
{
while (i >= 0 && node.Keys[i] > key)
{
i--;
}
if (node.Children[i + 1].KeyCount == 2 * degree - 1)
{
SplitChild(node, i + 1, node.Children[i + 1]);
if (node.Keys[i + 1] < key)
{
i++;
}
}
InsertNonFull(node.Children[i + 1], key);
}
}
private void SplitChild(BTreeNode parent, int i, BTreeNode fullChild)
{
BTreeNode newChild = new BTreeNode(fullChild.Degree, fullChild.IsLeaf);
newChild.KeyCount = Degree - 1;
for (int j = 0; j < Degree - 1; j++)
{
newChild.Keys[j] = fullChild.Keys[j + Degree];
}
if (!fullChild.IsLeaf)
{
for (int j = 0; j < Degree; j++)
{
newChild.Children[j] = fullChild.Children[j + Degree];
}
}
fullChild.KeyCount = Degree - 1;
for (int j = parent.KeyCount; j >= i + 1; j--)
{
parent.Children[j + 1] = parent.Children[j];
}
parent.Children[i + 1] = newChild;
for (int j = parent.KeyCount - 1; j >= i; j--)
{
parent.Keys[j + 1] = parent.Keys[j];
}
parent.Keys[i] = fullChild.Keys[Degree - 1];
parent.KeyCount++;
}
}
// 게임 아이템 클래스
public class GameItem
{
public int Id { get; set; }
public string Name { get; set; }
public GameItem(int id, string name)
{
Id = id;
Name = name;
}
}
// 데이터베이스 시뮬레이션
public class GameDatabase
{
private Dictionary<int, GameItem> items;
public GameDatabase()
{
items = new Dictionary<int, GameItem>();
}
public void AddItem(GameItem item)
{
items[item.Id] = item;
}
public GameItem GetItem(int id)
{
return items.TryGetValue(id, out var item) ? item : null;
}
}
class Program
{
static void Main(string[] args)
{
// 데이터베이스 초기화
GameDatabase db = new GameDatabase();
db.AddItem(new GameItem(1, "Sword"));
db.AddItem(new GameItem(2, "Shield"));
db.AddItem(new GameItem(3, "Potion"));
// B-트리 초기화
BTree btree = new BTree(3);
// 아이템 ID 삽입
btree.Insert(1);
btree.Insert(2);
btree.Insert(3);
// 아이템 검색
int searchId = 2;
var node = btree.Search(searchId);
if (node != null)
{
var item = db.GetItem(searchId);
Console.WriteLine(item != null
? $"아이템 찾음: {item.Name}"
: "아이템이 데이터베이스에 없습니다.");
}
else
{
Console.WriteLine("아이템을 찾을 수 없습니다.");
}
}
}