[Data Structure] 트리(Tree)

5 minute read

트리 란?

tree란?
-> 계층 구조를 나타내는 데 사용하는 자료구조 ‘그래프’의 한 종류로, 각 노드를 거쳐 자기 자신으로 돌아오지 않는 연결 그래프 입니다.(순환구조가 아니다 라는 뜻입니다.)

노드(node)로 구성되며, 각 노드에는 부모 노드(parent node)와 자식 노드(child node)가 있습니다.
부모 노드에는 하나 이상의 자식 노드를 가질 수 있으며, 자식 노드는 하나의 부모 노드를 가집니다.

응용으로서 이진 트리(Binary Tree), B-트리, 힙 트리(Heap tree)..등이 있습니다.

tree

트리, 이진 트리, B-트리 차이점

자식 노드의 개수
- 트리 : 0개, 1개, 4~5개도 가능
- 이진 트리 : 최대 2개
- B-트리 : 2개 이상
데이터의 순서
- 트리 : 정렬되어 있지 않을 수 있음
- 이진 트리 : 정렬되어 있음
- B-트리 : 정렬되어 있음
메모리 효율성
- 트리 : 메모리 사용 효율성이 낮음
- 이진 트리 : 메모리 사용 효율성이 높음
- B-트리 : 메모리 사용 효율성이 높음
용도
- 트리 : 데이터의 저장 및 탐색에 사용 (시스템에서 파일의 구조를 저장, 인공 지능에서 탐색 및 검색 알고리즘 등)
- 이진 트리 : 데이터의 효율적인 검색 및 탐색에 사용됨 (데이터를 검색 및 정렬, 힙 구현, 게임에서 오브젝트 저장 등)
- B-트리 : 데이터베이스 및 파일 시스템에서 사용됨 (DB 또는 파일 시스템에서 데이터를 저장, 인공 지능에서 탐색 및 검색 알고리즘에 사용 등)

사용하는 이유(용도)

계층 구조를 나타내기 위해 사용
데이터를 효율적으로 저장하고 검색하기 위해 사용
트리 탐색 알고리즘을 사용하여 데이터를 처리하기 위해 사용

문제점&주의사항

트리는 계층 구조를 나타내기 때문에 노드의 개수가 많아질수록 메모리 사용량이 많아질 수 있습니다.
트리의 깊이에 따라 탐색하기 때문에 깊이기 깊을 수록 탐색하는데 많은 시간이 걸립니다.
구조를 변경하려면 많은 노드를 수정해야 하기 때문에 구조를 변경하기가 어렵습니다.

예제

[기본 트리]

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("아이템을 찾을 수 없습니다.");
        }
    }
}

Top

Twitter Facebook LinkedIn

C YC

[Data Structure] 트리(Tree)

트리 란?

트리, 이진 트리, B-트리 차이점

사용하는 이유(용도)

문제점&주의사항

예제

You May Also Enjoy

[Algorithm] 프림 알고리즘(Prim’s Algorithm)

[C++] 유한 상태 기계(Finite State Machine) 모델 접근 방법

[C++] C++의 표준 템플릿 라이브러리(STL)에 관하여