[Java] Tree

트리 자료구조의 종류 : Tree, Binary Tree, Binary Serach Tree, Balanced Binary Serach Tree, Heap, Trie

이번 포스트에서는 기본적인 Tree에 대해서만 작성해보자.

 

Tree란 ?

 

Node와 Edge로 구성된 방향이 존재하는 비순환 Graph의 한 종류이다. 그래서 DAG(Directed Acyclic Graphs)라고도 한다.

그럼 Graph로 분류하면 되지 왜 Tree냐는 의심을 하게 된다.

Tree는 Graph에서 몇가지 특성을 더 가진다.

 

1. 루트 노드가 하나 존재한다.

2. 부모 노드는 하나밖에 존재하지 않는다.

3. 노드는 0개 이상의 자식을 가지고 있다.

4. 자식이 0개인 경우 단말노드(Leaf Node)라고 한다.

5.. 위 특성을 지키는 트리의 경우 엣지가 N-1개이다.

6. 엣지가 N-1개 이므로 두 정점간 경로는 1가지이다.

package com.study.datastructrue.nonlinear.tree;

import java.util.ArrayList;

public class Node<T> {
    private T data;
    private ArrayList<Node> children;

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

    public T getData() {
       return data;
    }

    public void setData(final T data) {
       this.data = data;
    }

    public ArrayList<Node> getChildren() {
       return children;
    }

    public void add(Node data) {
       children.add(data);
    }

}

 

기본적인 노드의 정보이다.

트리는 DAG라고 했으므로 자식이 여러개 일 수 있다.

package com.study.datastructrue.nonlinear.tree;

import java.util.ArrayList;

public class MyTree<T> {

    private Node<T> root;

    public MyTree() {
       this.root = null;
    }

    public void add(T to, T data) {
       if (this.root == null) {
          this.root = new Node(data);
          return ;
       }
       final Node node = findFirst(to);
       if (node == null) {
          throw new IllegalArgumentException("NOT Found Node");
       }
       node.add(new Node(data));
    }

    public Node findFirst(T data) {
       if (root.getData() == data) return root;
       return findFirst(root, data);
    }

    private Node findFirst(Node<T> cur, T data) {
       for (int i = 0; i < cur.getChildren().size(); i++) {
          if (cur.getChildren().get(i).getData() == data) {
             return cur.getChildren().get(i);
          }
       }
       for (Node node : root.getChildren()) {
          return findFirst(node, data);
       }
       return null;
    }

    public void printTree() {
       ArrayList<StringBuilder> sbs = new ArrayList<>();
       final int depth = depth(root, 0);
       for (int i = 0; i <= depth; i++) {
          sbs.add(new StringBuilder());
       }
       printTree(root, 0, sbs);
       for (StringBuilder sb: sbs) {
          System.out.println(sb.toString());
       }
    }

    private int depth(Node<T> cur, int level) {
       int maxLevel = level;
       for (int i = 0; i < cur.getChildren().size(); i++) {
          maxLevel = Math.max(depth(cur.getChildren().get(i), level + 1), maxLevel);
       }
       return maxLevel;
    }

    private void printTree(Node<T> cur, int level, final ArrayList<StringBuilder> sbs) {
       StringBuilder sb = sbs.get(level);
       sb.append(cur.getData() + " ");
       for (int i = 0; i < cur.getChildren().size(); i++) {
          printTree(cur.getChildren().get(i), level + 1, sbs);
       }
       sb.append("|");

    }


}

 

아무런 최적화 없이 트리를 설계하게 된다면 이렇게 효율적이지 못하게 된다.

특정 노드를 찾을 때에도 완전탐색을 해야하고 특정 노드의  자식으로 추가하려거나 교체하려면 특정 노드를 찾아야하므로 또 다시 완전탐색을 하게 된다.

 

이런 비효율적인 문제를 개선하기 위해 이진 탐색 트리(Binary Search Tree)라는 것이 나온다.

기준 값보다 작은 값은 왼쪽에 큰 값은 오른쪽에 비선형적, 계층적으로 저장해서 Log_2 N번만에 검색하는 방법이다.

그럼 삼진, 사진으로 나누면 더 빠르게 검색할 수 있는 것 아닌가? 라는 생각이 들었는데 실제로 DB에서 사용하고 있다. 이 부분은 나중에 작성.

 

package com.study.datastructrue.nonlinear.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

    public static void main(String[] args) {
       // 복잡한 트리 설계
       MyTree<Integer> tree = new MyTree<>();

       tree.add(0, 1);
       tree.add(1, 2);
       tree.add(2, 3);
       tree.add(2, 4);
       tree.add(2, 5);

       tree.printTree();

       // PS용 간단한 ADJ 트리 설계
       int vertexCount = 10;
       int level[] = new int[vertexCount + 1];
       ArrayList<ArrayList<Integer>> tree2 = new ArrayList<>();
       ArrayList<StringBuilder> sbs = new ArrayList<>();
       for (int i = 0; i <= vertexCount; i++) {
          sbs.add(new StringBuilder());
          tree2.add(new ArrayList<>());
       }
       tree2.get(1).add(2);
       tree2.get(2).add(3);
       tree2.get(2).add(4);
       tree2.get(2).add(5);
       Queue<Integer> q = new LinkedList<>();
       q.add(1);  level[1] = 1;  sbs.get(1).append(1);
       int maxLevel = 1;
       // BFS
       while (!q.isEmpty()) {
          int x = q.poll();
          maxLevel = Math.max(maxLevel, level[x]);
          for (int i : tree2.get(x)) {
             level[i] = level[x] + 1;
             sbs.get(level[i]).append(i + " ");
             q.add(i);
          }
       }
       for (int i = 1; i <= maxLevel; i++) {
          System.out.println(sbs.get(i).toString());
       }
    }

}

 

Graph에 가까운 Tree 사용과 PS 용으로 짧게 사용할 수 있는 코드