자료구조 - 트리(Java 구현)

트리

트리는 트리 모양으로 만든 자료구조이다. 즉, 모양은 트리구조지만, 내부적으로는 리스트이다.

자세히 다루자면 아래와 같다.

트리는 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조이다.

그렇다면 트리는 어디서 많이 사용되는가?

• 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨

 

용어

트리를 공부하다보면 용어가 많이 나와 이를 정리해 보았다.

• Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
• Root Node: 트리 맨 위에 있는 노드
• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
• Child Node: 어떤 노드의 상위 레벨에 연결된 노드
• Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
• Sibling (Brother Node): 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

 

 

 

이진트리 & 이진탐색트리

이진트리와 이진탐색트리는 엄밀히 말해 조금 다른 특징을 가진다.

• 이진 트리: 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
  • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음

 

 

 

장점 & 용도

• 데이터 검색(탐색)

  • 정렬된 이진트리 같은 경우 엄청나게 빠른 데이터 검색 속도를 보장한다.

• 장점: 탐색 속도를 개선할 수 있음

 

트리 구현

• 인터페이스로 명세를 해준다.

public interface ITree<T> {
    void insert(T val);
    void delete(T val);
    boolean contains(T val);
    int size();
}

public class Tree {
  private Node root = new Node();
  public void add(String data) {}
  public List<String> findPrefix(String prefix) {}
  public boolean contains(String data) {}
  private class Node {}
}

• Node 클래스는 node 하나를 만들어주는 클래스이다.

private class Node {
    private String data;
    private Map<Character, Node> children;

    public Node() {
        this.data = null;
        this.children = new TreeMap<>();
    }

    public Node(String data) {
        this.data = data;
        this.children = new TreeMap<>();
    }
}

• 노드를 추가해주는 메서드이다.

public void add(String data) {
        Node current = this.root;
        for (Character ch : data.toCharArray()) {
            if (!current.children.containsKey(ch)) {
                current.children.put(ch, new Node());
            }
            current = current.children.get(ch);
        }
        current.data = data;
    }

• 트리에서 하나를 찾는 메서드이다.

 public List<String> findPrefix(String prefix) {
        Node current = this.root;
        for (Character ch : prefix.toCharArray()) {
            if (!current.children.containsKey(ch)) {
                return List.of();
            }
            current = current.children.get(ch);
        }

        List<String> ret = new ArrayList<>();
        Queue<Node> q = new ArrayDeque<>();
        q.add(current);
        while (!q.isEmpty()) {
            Node node = q.poll();
            if (node.data != null) {
                ret.add(node.data);
            }
            for (Character nn : node.children.keySet()) {
                q.add(node.children.get(nn));
            }
        }
        return ret;
    }

• 요소가 있는지 없는지 확인해 주는 메서드이다.

public boolean contains(String data) {
    Node current = this.root;
    for (Character ch : data.toCharArray()) {
        if (!current.children.containsKey(ch)) {
            return false;
        }
        current = current.children.get(ch);
    }
    return data.equals(current.data);
}

 

Referance

참고 자료
penjee blog