[자료구조] Java Tree 구현 / 자바 트리 구현

원래 적어도 이틀에 하나씩 글을 쓰려 했지만, 학기중 스케쥴이 은근 바빠서 실천하지 못했다..ㅠㅠ 여튼! 오늘은 Java Tree 구현법을 보려고 한다.

앞의 ArrayList, Stack, Queue를 모두 본 사람은 알겠지만, 우리는 정보를 담는 어떤 객체와 이 객체를 어떠한 구조를 사용하여 데이터를 저장할 것인가를 다룰 것이다.

트리 구조에서는 흔히 객체를 담는 구조를 노드라고 하며, 이를 가지로 연결하여 나무처럼 만든다 해서 트리라 부른다. 트리에 사용되는 용어는 다음과 같다.

root: 뿌리. 최상위 노드
parent: child node를 갖는 노드
child: parent node를 갖는 노드
edge: 노드를 연결하는 선, branch라고도 함
depth: root부터 어떤 특정 노드까지의 깊이
height: 해당 노드까지 트리의 높이 (level-1)
leaf: 자식이 없는 최말단 노드
degree: 자식 수

아 맞다. 구현하는 글을 쓰고 있었지. 트리의 개념은 따로 정리해서 글을 쓰겠다.

---

Top Down, Bottom Up

트리는 위에서부터 아래로 만들어 나가는 Top down 방식과 최말단 노드에서부터 위로 올라가는 Bottom Up 방식이 있다. 본 글에서는 탑다운 방식을 구현할 예정이다. Root를 먼저 만들고, 그 뿌리에 가지를 하나씩 이어나가는 방식으로 말이다.

---

Tree에는 어떤게 필요할까?

Full Binary Tree

나무(식물)을 떠올려보면, 모두 뿌리를 먼저 내리고 그 이후에 줄기, 기둥, 가지, 잎, 꽃, 그리고 열매를 만들어 나간다.

즉 우리는 먼저 트리의 뿌리, root를 먼저 내려야 한다. 따라서 root를 설정할 수 있어야 하고, 뿌리로부터 나머지 가지들을 칠 수 있어야 한다.

root를 설정하는건 생성자로 할 수도 있고, setRoot와 같은 함수를 통해 할 수도 있다.

가지를 치는 것은 부모에서 자식을 설정하는 것이고, (반대로 자식에서 부모를 찾는 기능이 추가적으로 있어도 된다!) 본 글에서는 이진트리(Binary Tree)를 구현할 예정이라 setLeft, setRight (혹은 addLeft, addRight)를 만들 예정이다.

추가로 있으면 좋을 기능에는 size, height, depth, 그리고 트리의 꽃인 순회 기능이 있다.

본 글에서는 size와 순회기능을 추가 구현하고, 늘 그렇듯 height와 depth는 간단하기 때문에 구현하지 않을 예정이다.

---

Tree의  Node!

우선 Tree를 책임질 Node를 만들 것이다. Node는 내 부모를 가리킬 수 있어야 하고, 내 자식들을 가리킬 수 있어야 한다.

상상해보라. 나무에서 가지가 끊어진 상태로 존재할수는 없다. 끊어진 나뭇가지는 본체와 아무관계가 없으며, 죽은 가지일 것이다! (마찬가지로 열매도 가지 혹은 꽃으로부터 떨어진다면 더 이상 나무와는 관계 없다.)

노드는 정말 나의 데이터를 설정하고, 부모와 왼쪽, 오른쪽 노드를 가리키는것이 전부이기 때문에 한번에 코드를 올린다.

public class Node<T> {
    private T element;
    private Node<T> parent;
    private Node<T> left;
    private Node<T> right;

    Node(T element){
        this.element = element;
        this.parent  = null;
        this.left    = null;
        this. right  = null;
    }

    Node(T element, Node<T> left, Node<T> right){
        this.element = element;
        this.parent  = null;
        this.left    = left;
        this.right   = right;
    }

    Node<T> setParent(Node<T> parent){
        this.parent = parent;
        return this;
    }

    T getElement(){ return this.element;    }
    Node<T> setElement(T element){ this.element = element; return this; }
    Node<T> getLeft(){ return this.left;    }
    Node<T> setLeft(Node<T> left){ this.left = left; return this; }
    Node<T> getRight(){ return this.right;  }
    Node<T> setRight(Node<T> right){ this.right = right; return this; }
    Node<T> getParent(){ return this.parent;}
}

<T>는 제네릭 형태인데, 쉽게 말하면 이 노드는 T형태의 데이터를 갖겠다는 뜻이다. 이 T는  String, int, float 등 아무 객체타입이 될 수 있다.

---

Tree 구현!

자 이제 Tree를 구현 해보자! 트리의 생성자는 다음과 같다.

public class Tree<T> {
    private Node<T> root;
    private int size;
    public Tree(){
        this(null);
    }

    public Tree(Node<T> root){
        this.root = root;
        if(root != null)
            size = 1;
    }
}

나무를 아직 안심었을 수도 있고, 나무를 심었을 수도 있기 때문에 두 가지로 나누었다.

여기에 root, 그리고 트리의 왼쪽, 오른쪽 노드를 설정하는 코드는 다음과 같다.

    ...
    public int size(){ return this.size; }
    public Node<T> getRoot(){ return this.root;  }

    public Tree<T> setRoot(T element){
        if(root == null)
            size = 1;
        this.root = new Node(element);
        return this;
    }

    public Tree<T> setRoot(Node<T> element){
        if(root == null)
            size = 1;
        this.root = element;
        return this;
    }

    public Node<T> addLeft(Node<T> parent, Node<T> child){
        if(parent.getLeft() != null){
            System.out.println("Already have left");
            return null;
        }
        size++;
        parent.setLeft(child);
        return parent;
    }

    public Node<T> addRight(Node<T> parent, Node<T> child){
        if(parent.getRight() != null){
            System.out.println("Already have right");
            return null;
        }
        size++;
        parent.setRight(child);
        return parent;
    }

    public Node<T> removeLeft(Node<T> parent){
        Node<T> target = parent.getLeft();
        if(target != null)
            size--;
        parent.setLeft(null);
        return target;
    }

    public Node<T> removeRight(Node<T> parent){
        Node<T> target = parent.getRight();
        if(target != null)
            size--;
        parent.setRight(null);
        return target;
    }
    ...

해당 코드를 보면 root를 설정하거나 획득하는 것을 볼 수 있다.

보면 알겠지만, 트리에서 각 노드들에 대한 왼쪽, 오른쪽 노드를 설정하는 것에 깊게 관여하지 않는다. Node에 기본적으로 왼쪽, 오른쪽을 설정하는 코드가 포함되어 있기 때문에, 노드가 잘 할것이라 믿고 노드에게 준다. 다만, 트리는 이미 자식 노드가 설정되어 있을 때 덮어씌우면 안되기 때문에, 해당 경우에 한해서만 "Already have left!"와 같은 말을 출력해준다.

이제 트리의 꽃인 순회이다. 순회는 크게 3가지 방향이 있다.

height가 1인 full binary tree를 떠올려 보면 다음 표의 왼쪽과 같은 그림이다.

이진 바이너리 트리

이 트리를 더 확장해보면 아마 오른쪽과 같이 확장 될 것이다. 트리의 모양이 삼각형과 비슷하지 않은가?

자! 삼각형을 한붓 그리기로 그려봐라. 이 때, 각 꼭짓점은 full binary tree의 각 노드를 가리킨다고 하자. 그러면 우리는 이렇게 그릴수 밖에 없다. A-B-C, B-A-C, C-B-A. (각각의 가지수가 더 있지만, 여기까지만 표현하겠다. 그 이유는 다음줄에서 바로 나온다!)

트리의 순회도 똑같다. 부모-왼쪽-오른쪽(부모-오른쪽-왼쪽), 왼쪽-부모-오른쪽(오른쪽-부모-왼쪽), 왼쪽-오른쪽-부모(오른쪽-왼쪽-부모)로 순회할 수 있다. (통상적으로 오른쪽-부모-왼쪽 혹은 오른쪽-왼쪽-부모 의 오른쪽 먼저보다 왼쪽을 먼저 순회한다.)

각각의 순회 방법에 있어서 현재 내 노드(부모)를 기준으로 이름이 붙여지는데, 각각 전위순회, 중위순회, 후위순회라고 부른다(preorder, inorder, postorder).

순회를 할 때 연결된 모든 노드를 순회해야 하며, 이를 재귀를 이용하여 쉽게 나타낼 수 있다.

Full Binary Tree

다시 사진을 보면서 생각해보자! 설명은 preorder만 하고, 나머지 inorder, postorder는 직접 생각해보길 바란다. 원리는 같다.

순회를 A로부터 시작한다고 하자. 그러면 A를 돌고, 왼쪽자식 B, 오른쪽자식 I를 돌아야 한다. 그런데 이 때, B를 순회할 때 또 다시 (부모)-(왼쪽자식)-(오른쪽자식)을 돌아야 하는 상황이 발생하고, B-C-F를 돌게 된다. 마찬가지로 C를 확인할 때 또 다시 C-D-E순으로 돌게 된다. 이후 왼쪽자식이 더 이상 돌 게 없으니, B는 F를 확인하게 된다.

즉, (나)-(왼쪽자식)-(오른쪽자식)을 먼저 돌 때 A-B-C-D-E-F-G-H-I ... 순으로 순회해야하는 것을 알 수 있다.

---

이제 순회 코드!

 

    ...
    /* traverse */
    public void preorder(Node<T> node){
        System.out.println(node.getElement());
        if(node.getLeft() != null){
            preorder(node.getLeft());
        }
        if(node.getRight() != null){
            preorder(node.getRight());
        }
    }

    public void inorder(Node<T> node){
        /* Try it! */
    }

    public void postorder(Node<T> node){
        /* Try it! */
    }
    ...

---

실행 코드

트리를 구현할 수 있기 때문에 이제 각 노드에 대해 값이 잘 들어갔는지 확인 하는 코드는 작성하지 않았다.

따라서 최종 실행코드와 결과는 다음과 같다. 노드의 요소를 설정하는 값은 본 글에서 사용한 트리와 같게 했다.

    public static void main(String[] args){
        Tree<String> tree = new Tree(new Node("A"));
        //root node
        Node<String> root = tree.getRoot();
        tree.addLeft(root, new Node("B"));
        tree.addRight(root, new Node("I"));

        tree.addLeft(root.getLeft(), new Node("C"));
        tree.addRight(root.getLeft(), new Node("F"));

        tree.addLeft(root.getRight(), new Node("J"));
        tree.addRight(root.getRight(), new Node("M"));

        System.out.println("====preorder====");
        tree.preorder(root);
        System.out.println("\n==== inorder====");
        tree.inorder(root);
        System.out.println("\n===postorder====");
        tree.postorder(root);
        System.out.println("\ntree size: " + tree.size());

        System.out.println("====remove root.right.left====");
        tree.removeLeft(root.getRight());
        tree.preorder(root);
        System.out.println("\ntree size: " + tree.size());
    }

실행 결과

다음 글에서는 그래프 구현 방법을 다룰 예정이다.

끝!