Tree 구조 코드로 구현해보기

안녕하세요! 

이번에는 지난번에 알아본 tree 구조를 어떻게 코드로 나타내는 것인지 알아보겠습니다. 두근두근

생각보다 굉장히 간단합니다. 저는 직접 노드와 노드를 잇는 간선까지 표현을 해서 직접 트리 모양을 그려내는 것인 줄 알았는데, 그건 아니고 각 노드에 연결된 노드 정보를 저장해주는 형식으로 구현이 되더라구요. 무슨 말인지 직접 코드로 보도록 하겠습니다.

Tree 구조를 코드로 표현하는 핵심은 Node class를 만들어 주는 것입니다. 데이터를 담고 있는 각 노드를 객체로 만들어 주는 것이죠! 

 

Node class는 굉장히 간단합니다.

 

public class Node {
    int value;
//최대 세개의 child node
    Node left;
    Node middle;
    Node right;
 
    public Node(int value) {
        this.value = value;
    }
 
}

 

위에는 child node가 최대 3개인 경우이지만, child node가 최대 2개인 경우라면 middle은 제외하고 left와 rigth만 만들면 됩니다.

 

field를 살펴보면 Node 객체의 value가 있고, childe 노드가 될 노드들 역시 필드로 들어와 있습니다. 그리고 constructor를 이용해 node instance 생성 시에 node의 value를 설정할 수 있습니다.

그리고 setter를 이용해 child node를 설정할 수 있습니다. 만약에 child node가 하나도 없는 leaf라면, left, middle, right node는 모두 null이 됩니다. left와 right node만 있다면 middle만 null이 되구요. 

 

그런다음 node를 생성한 후 알맞게 left와 rigth에 할당하여 parent-child 관계를 만들어 주면 됩니다.

 

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
 
        node1.left = node2;
        node1.middle = node3;
        node1.right = node4;
 
        node2.left = node5;
        node2.right = node6;
 
        node3.middle = node7;
 
        node4.left = node8;
        node4.right = node9;

 

Binary tree를 만들고 싶다면 어떻게 하면 될까요? Binary tree의 큰 특징이 무엇이 있었죠?

바로 child의 수가 최대 2개라는 점입니다. 그렇다면 위의 node class 에서 left, middle, right 이렇게 세개였던 child node field를 left와 right 두개만 만들면 됩니다!

 

public class Node {
    int value;
//최대 두개의 child node
    Node left;
    Node right;
 
    public Node(int value) {
        this.value = value;
    }
 
}

 

 

생각보다 간단하죠? 그렇다면 이제는, 효율적인 데이터 탐색을 위해 만들어진 Binary Search Tree(BST)는 어떻게 구현하는지 알아보겠습니다. 조금 복잡하다고 느낄 수 있지만 결국 핵심은 root의 왼쪽은 root보다 작은 데이터가, 오른쪽은 큰 데이터가 위치하도록 만들고, 중복된 데이터가 없도록 로직을 구성하는 것입니다

 

먼저, BST class를 만들어 줍니다. BST는 일반 tree와는 다르게 값의 크기에 따라 child node를 설정해주어야 합니다. 그렇기 때문에 BST class에는 child node를 넣는 method가 따로 필요합니다.

 

public class BST {
 
    Node root;
 
    public void insert(Node node){
        root = insertHelper(root, node);
    }
 
}

 

root node의 값과 추가하려는 node의 값을 비교할 수 있도록 insert() method를 만들어 주었습니다.

재귀를 사용할 것이기 때문에 insertHelper method를 또 구성해보도록 하겠습니다.

 

    private Node insertHelper(Node root, Node node){
        int data = node.value;
        if(root == null) { //root node가 null인 경우
            root = node;
            return root;
 
        } else if(node.value < root.value) { //root node보다 값이 작은 경우
            root.left = insertHelper(root.left, node);
 
        } else { //root node보다 값이 큰 경우
            root.right = insertHelper(root.right, node);
        }
        return root;
    }

 

코드를 한 번 읽어볼까요?

 

line#3 : root node가 null이라면, 아무 것도 없는 상태이기 때문에 추가하고자 하는 node를 바로 배정해주면 됩니다.

 

line#7 : root node보다 넣으려는 node의 값이 작다면, root node의 왼편에 추가해줍니다. (값을 계속해서 비교하며 자리를 찾아주어야 하기 때문에 root.left를 설정하는 부분(line#8)에서 재귀가 사용됩니다!)

 

line#10 : root node보다 넣으려는 node의 값이 크다면, root node의 오른편에 추가해줍니다. (마찬가지로 값을 계속해서 비교하며 자리를 찾아주어야 하기 때문에 root.right를 설정하는 부분(line#11)에서 재귀가 사용됩니다!)

 

눈으로 이해가 잘 되지 않는다면 재귀부분의 코드를 직접 작성하거나 도표를 그려 코드를 따라가보면 훨씬 도움이 됩니다.

 

그런 다음 아래와 같이 BST를 만들 수 있습니다!

 

        BST bst = new BST();
 
        Node node1 = new Node(8);
        Node node2 = new Node(6);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(1);
        Node node7 = new Node(7);
        Node node8 = new Node(9);
        Node node9 = new Node(2);
 
        bst.insert(node1);
        bst.insert(node2);
        bst.insert(node3);
        bst.insert(node4);
        bst.insert(node5);
        bst.insert(node6);
        bst.insert(node7);
        bst.insert(node8);
        bst.insert(node9);