[자료구조] 트리(Tree)

트리

• 부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조

• 단, 자식 노드의 자식이 부모로 연결되는 경우는 보통 트리로 인정되지 않음

• rooted tree에서는 여러가지 용어를 정의

  • 높이(height)는 루트의 높이를 0으로 하고, 자식의 높이를 원래 노드보다 1 큰 것으로 정의
  • 말단 노드(leaf node)의 정의는 자식이 없는 노드

• unrooted tree에서는 차수가 1인 노드로 말단 노드를 정의

• Tree 관련 용어

  • 노드(node): 트리를 구성하는 기본 원소
  • 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점
  • 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
  • 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드
  • 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
  • 리프 노드(leaf node/leaf/terminal node): 자식이 없는 노드
  • 경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
  • 길이(length): 출발 노드에서 도착 노드까지 거치는 노드의 갯수
  • 깊이(depth): 루트 경로의 길이
  • 레벨(level): 루트 노드(1) 로 부터 노드까지 연결된 엣지의 수의 합
  • 높이(height): 가장 긴 루트 경로의 길이
  • 차수(degree): 각 노드의 자식의 갯수
  • 트리의 차수(degree of tree): 트리의 최대 차수
  • 크기(size): 노드의 개수
  • 너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기
  • Tree의 응용
  • 이진트리(Binary Tree)
  • 이진탐색트리(Binary Search Tree, BST)
  • 스레드 이진 트리
  • 힙(Heap)
  • B-tree
  • 포레스트(Forest)
  • 트라이(Trie)

자료구조

• Tree 인터페이스 작성
  • search 추상메서드와 insert 추상메서드 작성
  • Comparable 인터페이스 타입의 원소를 저장할 수 있도록 제네릭 생성
  • Node 클래스를 자식으로 갖는 또 다른 재귀 타입

public interface Tree<E extends Comparable> {
    boolean search(E toFind);
    void insert(E toInsert);
}

• Node 클래스 작성

  • 데이터와 left, right Node 클래스를 재귀 타입으로 갖는 클래스
  • constructor, Tree 인터페이스로부터 search, insert 메서드를 구현

public class Node<E extends Comparable> implements Tree<E> {

    private E value;
    private Tree<E> left;
    private Tree<E> right;

    public Node(E value, Tree<E> left, Tree<E> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public E getValue() { return value; }
    public Tree<E> getLeft() { return left; }
    public Tree<E> getRight() { return right; }
    public void setLeft(Tree<E> left) { this.left = left; }
    public void setRight(Tree<E> right) { this.right = right; }

    @Override
    public boolean search(E toFind) {
        // right element 검색
        if (toFind.equals(value)) return true;

        /* 
         * toFind를 value와 비교하여 같으면 0, '>' 는 양수, '<'는 음수
         * 음수일 경우 left Node를 검색
         * 같거나 양수일 경우 right Node를 검색
         */
        if (toFind.compareTo(value) < 0) { return left.search(toFind); }

        // 위 조건문에서 양수일 경우 right Node를 검색
        return right.search(toFind);
    }

    @Override
    public void insert(E toInsert) {
        /* 
         * toInsert 값을 value값과 비교하여 같으면 0, '>' 는 양수, '<'는 음수
         * 음수일 경우 left Node에 삽입
         * 같거나 양수일 경우 right Node에 삽입
         */
        if (toInsert.compareTo(value) < 0) { left.insert(toInsert);
        } else { right.insert(toInsert); }

    }
}

• Leaf 클래스

public class Leaf<E extends Comparable> implements Tree<E> {

    private final Node<E> parent;

    public Leaf(Node<E> parent) {
        this.parent = parent;
    }

    @Override
    public boolean search(E toFind) {
        return false;
    }

    @Override
    public void insert(E toInsert) {
        /*
         * toInsert 값을 상위노드 값과 비교, 같으면 0, '>' 는 양수, '<'는 음수
         * 상위노드의 left 노드에 새로 Node 삽입
         */
        if (toInsert.compareTo(parent.getValue()) < 0)
            parent.setLeft(new Node<>(toInsert, new Leaf<>(parent), new Leaf<>(parent)));
        else
            parent.setRight(new Node<>(toInsert, new Leaf<>(parent), new Leaf<>(parent)));
    }
}

이진트리 검색 알고리즘

• 단순 트리 구조

  • search를 통해 값이 있는지 확인
  • insert를 통해 상위노드와 비교하여 값이 작으면 left 노드에 삽입, 값이 같거나 클 경우 right 노드에 삽입

public class SimpleTree<E extends Comparable> {
    private E value;
    private SimpleTree<E> left;
    private SimpleTree<E> right;

    public SimpleTree(E value, SimpleTree<E> left, SimpleTree<E> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public E getValue() { return value; }
    public SimpleTree<E> getLeft() { return left; }
    public SimpleTree<E> getRight() { return right; }

    public boolean search(final E toFind) {
        // 찾으려는 값이 Tree에 있는 것을 확인
        if (toFind.equals(value)) return true;

        /* 
         * toFind를 value와 비교하여 같으면 0, '>' 는 양수, '<'는 음수
         * left 노드가 존재하고, 음수일 경우 left Node를 검색
         * 같거나 양수일 경우 right Node를 검색
         */
        if (toFind.compareTo(value) < 0 && left != null) return left.search(toFind);

        return right != null && right.search(toFind);
    }

    public void insert(final E toInsert) {
        // 입력할 값을 비교, 같으면 0, '>' 는 양수, '<'는 음수
        if (toInsert.compareTo(value) < 0) {
            // 입력 값이 작고, left Node가 null일 경우 새로 생성
            if (left == null) left = new SimpleTree<>(toInsert, null, null);
            // 입력 값이 작고, left Node가 null이 아닐 경우 삽입
            else left.insert(toInsert);

        } else {
            // 입력 값이 같거나 크고, right Node 값이 null인 경우 새로 생성
            if (right == null) right = new SimpleTree<>(toInsert, null, null);
            // 입력 값이 같거나 크고, right Node 값이 null이 아닌 경우 새로 생성
            else right.insert(toInsert);

        }
    }
}

• 단순트리 검색 테스트
  • 단순 트리 구조의 insert, search 테스트

public class SimpleTreeTest {

    private SimpleTree<Integer> root;

    @Before
    public void createSampleTree() {
        final SimpleTree<Integer> t1 = new SimpleTree<>(1, null, null);
        final SimpleTree<Integer> t5 = new SimpleTree<>(5, null, null);

        final SimpleTree<Integer> t3 = new SimpleTree<>(5, t1, t5);
        final SimpleTree<Integer> t9 = new SimpleTree<>(9, null, null);
        /*     7
         *   5   9
         * 1 5
         */
        root = new SimpleTree<>(7, t3, t9);

    }

    @Test
    public void search() {
        assertTrue(root.search(7));
        assertFalse(root.search(70));
    }

    @Test
    public void insert() {
        root.insert(10);
        assertTrue(root.search(10));
        /*     7
         *   5   9
         * 1 5     10
         */
        assertEquals(Integer.valueOf(10), root.getRight().getRight().getValue());
    }

    @Test
    public void createTree() {
        final SimpleTree<Integer> root = new SimpleTree<>(7, null, null);
        root.insert(3);
        root.insert(9);
        root.insert(10);
        assertTrue(root.search(10));
        /*     7
         *   3   9
         *            10
         */
        assertEquals(Integer.valueOf(10), root.getRight().getRight().getValue());
    }

    @Test
    public void linkedListTree() {
        final SimpleTree<Integer> root = new SimpleTree<>(1, null, null);
        root.insert(2);
        root.insert(3);
        root.insert(4);
        root.insert(5);

        /*     1
         *       2
         *            3
         *              4
         *                5
         */
        assertEquals(Integer.valueOf(1), root.getValue());
        assertEquals(Integer.valueOf(2), root.getRight().getValue());
        assertEquals(Integer.valueOf(3), root.getRight().getRight().getValue());
        assertEquals(Integer.valueOf(4), root.getRight().getRight().getRight().getValue());
        assertEquals(Integer.valueOf(5), root.getRight().getRight().getRight().getRight().getValue());
    }
}

• Complex 트리 검색

public class ComplexTreeTest {

    @Test
    public void insert() {
        final Node<Integer> root = new Node<>(7, null, null);
        root.setLeft(new Leaf<>(root));
        root.setRight(new Leaf<>(root));

        root.insert(3);
        assertTrue(root.search(3));
        assertFalse(root.search(13));
    }
}

코드 참고 - 자바 프로그래밍 면접 이렇게 준비한다