Tree

비선형 자료구조 트리(Tree)

트리(Tree)란?

예를 들어 카페에 갔는데 메뉴판을 보니 차가운 음료와 뜨거운 음료가 분리되어 있다. 차가운 음료 아래에는 스무디, 아아 등이 있고 뜨거운 음료에는 카푸치노, 라떼 같은 메뉴가 존재한다. 데이터 구조의 세계에서는 이를 트리 데이터 구조라고 한다. 우리는 트리 데이터 구조를 인지하지 못하고 일상생활에서 사용하는 듯하다.

트리는 서로 계층적 관계를 갖는 비선형 데이터 구조이고, 사이클이 존재하지 않은 방향 그래프이다. 즉, 트리는 그래프이지만 그래프는 트리가 아니다.

tree is graph

트리는 노드(Node)와 간선(Edge)로 구성되어 있고 다음과 같은 특징을 갖는다.

• 루트 노드(Root Nod) : 트리의 최상위 노드이며, 루트 노드로부터 시작된다.

• 노드(Node) : 트리의 데이터를 저장하고 있는 요소이다. 각 노드는 하나 이상의 자식 노드를 가질 수 있다.

  • 부모 노드 : 어떤 노드에 연결된 위에 있는 노드이다.

  • 자식 노드 : 어떤 노드에 연결된 아래에 있는 노드이다.

  • 리프 노드 : 자식 노드를 갖지 않는 노드이다. 단말 노드라고도 한다.

• 간선(Edge) : 노드들을 연결하는 선으로, 부모 노드와 자식 노드의 연결을 나타낸다.

트리의 사용 목적에 맞게 여러 형태의 트리가 있다.

대표적으로 이진 트리(Binary), 이진 탐색 트리(Binary Search), AVL 트리, B-트리, 힙(Heap), 그래프 등이 있다.

트리는 왜 사용할까? 선형 데이터 구조에서는 연산을 수행할 때 데이터의 크기가 증가하면 시간 복잡도도 증가한다. 트리에서는 데이터에 더 쉽고 빠르게 접근이 가능하고, 계층 구조를 형성하는 정보를 저장하기에 용이하기 떄문이다.

따라서 폴더 구조, 조직 구조, XML 등과 같은 계층적 데이터를 저장하는 경우 트리를 사용하는 것이 유용하다.

아래는 트리를 간단하게 구현 해보고, 결과를 출력 해보았다.

public class TreeNode<T> {
    T data;
    ArrayList<TreeNode<T>> children;

    public TreeNode(T data) {
        this.data = data;
        this.children = new ArrayList<>();
    }

    // ep : 트리 노드를 생성 할 때 이 트리 노드와 자식 사이에 링크를 생성하는 메소드
    public void addChild(TreeNode<T> node) {
        this.children.add(node);
    }

    public String print(int level) {
        String ret = "["+ level + "]" + "  ".repeat(level) + data + "\n";
        for (TreeNode<T> node : this.children) {
            ret += node.print(level + 1);
        }
        return ret;
    }
}

public static void main(String[] args) {
    TreeNode<String> drinks = new TreeNode<>("Drinks");
    TreeNode<String> hotDrinks = new TreeNode<>("Hot drinks");
    TreeNode<String> coldDrinks = new TreeNode<>("Cold drinks");
    drinks.addChild(hotDrinks);
    drinks.addChild(coldDrinks);

    hotDrinks.addChild(new TreeNode<>("hot americano"));
    coldDrinks.addChild(new TreeNode<>("smoothie"));
    System.out.println(drinks.print(0));
}


// 출력
// [0]Drinks
// [1]  Hot drinks
// [2]    hot americano
// [1]  Cold drinks
// [2]    smoothie