김석진

김석진

꾸준히 공부하는 개발자입니다.
블로그 포스트 글에서 잘못된 부분이나 수정했으면 하는 부분, 적극적으로 댓글 남겨주신다면 감사하겠습니다.

JAVA 자료구조 2(Data Structure)

업데이트:
9 분 소요

Step 4 : 비선형구조

트리(Tree)

java 쓰레드 상태 트리란 위에도 가볍게 언급한, 하나의 루트 노드와 0개 이상의 자식노드로 이루어진 자료구조입니다. 주로 계층적 관계( Hierarchical Relationship )를 표현하는 자료구조입니다. 트리관련 용어를 살펴보겠습니다.

  • Node (노드): A,B,C와 같은 요소입니다.
  • Root Node (루트노드): 최상위 노드 즉 A노드입니다.
  • Edge (간선) : 노드와 노드를 연결한 선입니다.
  • Terminal node, Leaf Node (단말노드) : 자식 노드가 없는 E, F, C, D와 같은 노드입니다.
  • Internal Node(내부노드) : 단말 노드가 아닌 A, B와 같은 노드입니다.
  • Degree(차수) : 자식 노드의 수를 말합니다.
  • Preorder Traversal( 전위 순회 ) : Root -> 좌 -> 우 순으로 Tree를 탐색하는 방법입니다.
  • Inorder Traversal( 중위 순회 ) : 좌 -> root -> 우 순으로 Tree를 탐색하는 방법입니다.
  • Postorder Traversal ( 후위 순회 ) : 좌 -> 우 -> root순으로 tree를 탐색합니다.

Tree의 자료구조를 표현하는 방법은 배열과 LinkedList로 표현할 수 있습니다.

이진 트리( Binary Tree )

java 쓰레드 상태 각 노드가 최대 두 개의 자식을 갖는 Tree입니다. 꼭 자식 노드가 다 차지 않아도 됩니다.

완전 이진 트리 ( Complete Binary Tree )

java 쓰레드 상태 마지막 레벨을 제외한 모든 노드는 채워져 있어야 하며 마지막 레벨은 왼쪽부터 채워져 있는 Binary Tree를 말합니다.

정 이진트리 ( Full Binary Tree )

java 쓰레드 상태 모든 노드가 0개 또는 2개의 자식 노드를 갖는 이진트리입니다.

포화 이진트리 ( Perfect Binary Tree )

java 쓰레드 상태 모든 레벨의 노드가 꽉 차있는 이진트리입니다.

이진 탐색 트리 ( Binary Search Tree )

java 쓰레드 상태

중복된 값이 없으면서 왼쪽 자식 노드 값 < root 노드 < 오른쪽 자식 노드 값을 만족하는 이진트리입니다. root 노드 하위 왼쪽 노드 집합들은 root 노드 값보다 작아야 하며 우측 집합은 커야 합니다.


Tree구조로 할 수 있는 것은 다양합니다. 언급하지는 않았지만, Expression Tree와 같은 형태로 들어온 데이터를 구성할 수도 있고 새로운 형식의 데이터를 만들어 담을 수도 있습니다. 이제 Tree를 어떻게 구성하는지 알아보겠습니다.

ex) 수식 트리 Expression Tree
수식을 tree형태로 분리한 tree
7 + 4 * 2 -1 를 나타낸 트리는 아래와 같습니다.

java 쓰레드 상태

Linked List로 Tree 구현

트리는 원하는 방식으로 원하는 모양으로 무궁무진하게 만들 수 있습니다. 단순한 이진 트리를 구현해보겠습니다.

  • getValue() : 노드에 저장된 데이터 return
  • setLeftNode() : 왼쪽 노드 세팅
  • setRightNode() : 우측 노드 세팅
  • getLetNode(): 좌측 노드 데이터 return
  • getRightNode(): 우측 노드 데이터 return
  • inOrderTraversal() : 중위 순회 왼쪽 node -> root node -> 오른쪽 node
  • preOrderTraversal() : root node -> 왼쪽 node -> 오른쪽 node
  • postOrderTraversal() : 왼쪽 node -> 오른쪽 node -> root node
public class TreeWithLinkedList<T> {
    private T value;
    private TreeWithLinkedList<T> leftNode;
    private TreeWithLinkedList<T> rightNode;
   
    public TreeWithLinkedList( T value ) {
        this.value = value;
    }
    
    /**
     * left -> root -> right
     */
    public void inOrderTraversal() {
        if( leftNode != null ) leftNode.inOrderTraversal();
        System.out.println(value.toString());
        if( rightNode != null ) rightNode.inOrderTraversal();
    }
    
    /**
     * root -> left -> right
     */
    public void preOrderTraversal() {
        System.out.println(value.toString());
        if( leftNode != null ) leftNode.preOrderTraversal();
        if( rightNode != null ) rightNode.preOrderTraversal();
    }

    /**
     * left -> right -> root
     */
    public void postOrderTraversal() {
        if( leftNode != null ) leftNode.postOrderTraversal();
         if( rightNode != null ) rightNode.postOrderTraversal();
        System.out.println(value.toString());
    }


    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public TreeWithLinkedList<T> getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(TreeWithLinkedList<T> leftNode) {
        this.leftNode = leftNode;
    }

    public TreeWithLinkedList<T> getRightNode() {
        return rightNode;
    }

    public void setRightNode(TreeWithLinkedList<T> rightNode) {
        this.rightNode = rightNode;
    }
}


TreeWithLinkedList<Integer> root = new TreeWithLinkedList<Integer>(1);
TreeWithLinkedList<Integer> rootLeft = new TreeWithLinkedList<Integer>(2);
TreeWithLinkedList<Integer> rootRight = new TreeWithLinkedList<Integer>(3);
TreeWithLinkedList<Integer> rootLeftLeft = new TreeWithLinkedList<Integer>(4);
TreeWithLinkedList<Integer> rootLeftRight = new TreeWithLinkedList<Integer>(5);

root.setLeftNode(rootLeft);
root.setRightNode(rootRight);
rootLeft.setLeftNode(rootLeftLeft);
rootLeft.setRightNode(rootLeftRight);

root.inOrderTraversal(); // 중위순회 left -> root -> right >> 4 2 5 1 3 
root.preOrderTraversal(); // 전위순회 root -> left -> right >> 1 2 4 5 3 
root.postOrderTraversal(); // 후위순회 left -> right -> root >> 4 5 2 3 1

배열로 Tree 구현

배열로 2진트리를 구성하려면 우선 배열의 크기를 정해야 하기 때문에 최종 데이터의 크기를 알아야 한다는 점, 왼쪽 노트의 위치, 우측 노드의 위치, 부모 위치 구하는 방법을 알아야합니다.

  • 왼쪽 자식의 index : ( 자기자신의 index ) * 2 +1
  • 오른쪽 자식의 index : 왼쪽 자식의 index + 1 = ( 자기자신의 index ) * 2 +2
  • 부모 index : ( 자기 자신의 index -1 ) / 2
  • 총 크기 : Perfect Binary Tree 크기 만큼 하기 위해, 최종 데이터의 크기를 꽉 찬 트리 size로 만든후 그 크기 * 2 배만큼의 크기가 필요합니다.
public class TreeWithArray<T> {
    private Object tree [];
    private int treeSize;
   
    public TreeWithArray( int arraySize ) {
       treeSize = 1;
        
        while (treeSize < arraySize) {
            treeSize <<= 1;
        }
        treeSize *= 2;
        tree = new Object[ treeSize ];
    }
    
    /**
     * left -> root -> right
     */
    public void inOrderTraversal( int checkIndex ) {
        if(  checkIndex < treeSize && tree[checkIndex] != null ) {
            int leftChildIndex = getLeftNodeIndex(checkIndex);
            int rightChildIndex =  getRightNodeIndex(checkIndex);
            inOrderTraversal( leftChildIndex );
            System.out.println(tree[checkIndex].toString());
            inOrderTraversal( rightChildIndex );
        } 
    }
    
    /**
     * root -> left -> right
     */
    public void preOrderTraversal( int checkIndex ) {
        if(  checkIndex < treeSize && tree[checkIndex] != null ) {
            int leftChildIndex = getLeftNodeIndex(checkIndex);
            int rightChildIndex =  getRightNodeIndex(checkIndex);
            System.out.println(tree[checkIndex].toString());
            preOrderTraversal( leftChildIndex );
            preOrderTraversal( rightChildIndex );
        } 
    }

    /**
     * left -> right -> root
     */
    public void postOrderTraversal( int checkIndex ) {
        if(  checkIndex < treeSize && tree[checkIndex] != null ) {
            int leftChildIndex = getLeftNodeIndex(checkIndex);
            int rightChildIndex =  getRightNodeIndex(checkIndex);
            postOrderTraversal( leftChildIndex );
            postOrderTraversal( rightChildIndex );
            System.out.println(tree[checkIndex].toString());
        } 
    }


    @SuppressWarnings("unchecked")
    public T getValue( int index ) {
        return (T)tree[index];
    }

    public void setValue( T value, int index ) {
        if( index >= treeSize ) {
            throw new IndexOutOfBoundsException("size를 확인하세요");
        }
        tree[index] = value;
    }

    @SuppressWarnings("unchecked")
    public T getLeftNode( int parentIndex ) {
        int childIndex = getLeftNodeIndex(parentIndex);
        if( childIndex >= treeSize ) {
            throw new IndexOutOfBoundsException("size를 확인하세요");
        }
        return (T)tree[childIndex];
    }

    public void setLeftNode( T leftNode, int parentIndex ) {
        int childIndex = getLeftNodeIndex( parentIndex );
        if( childIndex >= treeSize ) {
            throw new IndexOutOfBoundsException("size를 확인하세요");
        }
        tree[childIndex] = leftNode;
    }

    @SuppressWarnings("unchecked")
    public T getRightNode( int parentIndex ) {
        int childIndex =  getRightNodeIndex( parentIndex );
        if( childIndex >= treeSize ) {
            throw new IndexOutOfBoundsException("size를 확인하세요");
        }
        return (T)tree[childIndex];
    }

    public void setRightNode( T rightNode, int parentIndex) {
        int childIndex = getRightNodeIndex( parentIndex );
        if( childIndex >= treeSize ) {
            throw new IndexOutOfBoundsException("size를 확인하세요");
        }
        tree[childIndex] = rightNode;
    }
    
    public int getLeftNodeIndex( int parentIndex ) {
        return parentIndex*2 +1;
    }
    
    public int getRightNodeIndex( int parentIndex ) {
        return parentIndex*2 +2;
    }
}


TreeWithArray<Integer> tree = new TreeWithArray<Integer>(5);
tree.setValue(1, 1);
tree.setLeftNode(2, 1);
tree.setRightNode(3, 1);
tree.setLeftNode(4, tree.getLeftNodeIndex(1));
tree.setRightNode(5, tree.getLeftNodeIndex(1));

tree.inOrderTraversal(1); // 중위순회 left -> root -> right >> 4 2 5 1 3 
tree.preOrderTraversal(1); // 전위순회 root -> left -> right >> 1 2 4 5 3 
tree.postOrderTraversal(1); // 후위순회 left -> right -> root >> 4 5 2 3 1

그래프

java 쓰레드 상태

그래프란 위 그림에서 보는 것처럼 노드와 노드를 연결한 간선이 존재하는 자료구조입니다. 이전 자료구조를 공부하면서 봤었던 용어들입니다.

  • Vertex (정점) : 하나의 노드를 말합니다.
  • Edge (간선) : 정점을 연결하는 선입니다.
  • Adjacent vertex ( 인접정점 ) : 자기 자신 정점과 바로 연결된 정점을 말합니다.
  • Degree ( 차수 ) : 자기 자신과 연결된 간선의 개수를 말합니다.
  • Cycle : 한 정점에서 시작하여 자기자신으로 끝나는 경로를 말합니다.
  • 오일러 경로 : 그래프에 존재하는 모든 간선을 한 번만 통과하는 것 » 오일러 경로는 차수가 홀수인 정점이 2개일때 존재합니다.
  • 오일러 회로 : 오일러 경로 + 시작점과 끝점이 같은 경우 = 한 붓 그리기 » 차수가 홀수인 정점이 0개일때 오일러 회로가 존재합니다.

방향 그래프

그래프에 방향이 존재하여 G(A,B)는 G(B,A)는 다른 경우를 말합니다.

무방향 그래프

그래프에 방향이 존재하지 않아 양 방향으로 갈 수 있다. G(A,B)는 G(B,A)와 동일한 경우를 말합니다.

가중치 그래프(Weighted Graph)

간선에 비용이나 가중치가 할당된 그래프를 말합니다.

솔직히 업무에서 그래프를 다루거나 사용한 사례는 없어 잘 아는 자료구조는 아닙니다. 단지 백준 알고리즘 혹은 카카오 알고리즘을 풀어 볼 때 관련 내용 등장하면 사용 및 공부하기 위해 정리합니다. 그래프 자료구조를 구현하는 방법은 크게 두 가지가 존재합니다. 하나는 인접 리스트로 구현하는 방법과, 인접행렬로 구현하는 방법입니다.

java 쓰레드 상태

인접 리스트(Adjacency List)로 구현

내용은 간단합니다. 배열의 index는 자기 자신의 노드 위치를 말하며, 저장된 value는 해당 노드와 연결된 인접 노드를 가리킵니다. 추가로 두 노드 사이의 가중치를 저장하도록 양방향 그래프로 구현해보겠습니다.

  • push() : 데이터 삽입.
public class GraphArrayList {
    private ArrayList<ArrayList<int[]>> graph;
    
    // 정점의 개수로 초기화
    public GraphArrayList( int nodeSize ) {
        this.graph = new ArrayList<ArrayList<int[]>>();
        
        // 각각의 정점들 초기화
        for( int index=0; index < nodeSize; index++ ) {
            graph.add( new ArrayList<int[]>() );
        }
    }
    
    public void push( int orignalNode, int adjacentNode, int weight ) {
        pushOnly( orignalNode, adjacentNode, weight );
        pushOnly( adjacentNode, orignalNode, weight );
    }
    
    private void pushOnly( int orignalNode, int adjacentNode, int weight ) {
        int[] temp = { adjacentNode, weight };
        graph.get(orignalNode).add(temp);
    }
    
    public void print() {
        for (int index = 0; index < graph.size(); index++) {
            System.out.println("정점 " + index + "의 인접리스트");
            for (int indexInner = 0; indexInner < graph.get(index).size(); indexInner++) {
                int[] temp = graph.get(index).get(indexInner);
                System.out.print( temp[0]+"("+temp[1]+")" + " ");
            }
            System.out.println();
        }
    }
}

GraphArrayList graph = new GraphArrayList(4);
graph.push(0, 1, 2);
graph.push(1, 2, 7);
graph.push(2, 3, 1);

graph.print();

1
2
3
4
5
6
7
8
9

// 출력 
정점 0의 인접리스트
1(2) 
정점 1의 인접리스트
0(2) 2(7) 
정점 2의 인접리스트
1(7) 3(1) 
정점 3의 인접리스트
2(1)

인접 행렬(Adjacency Matrix)로 구현

구현 내용은 간단합니다. 2차원 배열에 index가 두 노드의 연결 여부 및 가중치를 나타냅니다. 아래 코드를 보면 이해가 될 것입니다.

public class GraphMatrix {
    private int[][] graph;

    public GraphMatrix( int nodeSize ) {
        graph = new int [nodeSize][nodeSize];
    }
    
    public void push( int orignalNode, int adjacentNode, int weight ) {
        graph[orignalNode][adjacentNode] = weight;
        graph[adjacentNode][orignalNode] = weight;
    }
    
    public void print() {
        for (int index = 0; index < graph.length; index++) {
            System.out.println("정점 " + index + "의 인접리스트");
            for (int indexInner = 0; indexInner < graph[index].length; indexInner++) {
                if( graph[index][indexInner] > 0) {
                    System.out.print( indexInner+"("+graph[index][indexInner]+")" + " ");
                }
            }
            System.out.println();
        }
    }
}

GraphMatrix graph = new GraphMatrix(4);
graph.push(0, 1, 2);
graph.push(1, 2, 7);
graph.push(2, 3, 1);

graph.print();

1
2
3
4
5
6
7
8
9

//출력 
정점 0의 인접리스트
1(2) 
정점 1의 인접리스트
0(2) 2(7) 
정점 2의 인접리스트
1(7) 3(1) 
정점 3의 인접리스트
2(1)


이런 그래프를 일반적으로 탐색하는 방법은 2가지입니다. 하나는 깊이우선탐색(DFS), 다른 하나는 너비 우선 탐색(BFS)입니다.

java 쓰레드 상태

깊이우선탐색( Depth First Search )

하나의 정점에서 시작하여 다음 인접 노드를 지속해서 확인하여 모든 노드를 탐색하는 방법입니다. 원리는 root노드를 정한 후 인접 노드를 stack에 집어넣고 stack을 순회하면서 호출된 적 있는지 확인 후 반복하는 일만 진행하면 됩니다.

너비우선탐색 ( Breadth First Search )

하나의 정점에서 시작하여 하나의 정점을 완벽히 탐색 후 다음 정점을 넘어가 모든 노드를 탐색하는 방법입니다. 원리는 간단합니다. root노드를 정한 후 root노드에 관련된 인접 노드를 que에 집어넣고 해당 que를 순회하면서 한 번 호출된 적 있는 노드인지 확인 후 que가 빌 때까지 지속하는 방법입니다.

public class GraphMatrix {
    private int[][] graph;
    private int nodeSize = 0;

    public GraphMatrix( int nodeSize ) {
        graph = new int [nodeSize][nodeSize];
        this.nodeSize = nodeSize;
    }
    
    public void push( int orignalNode, int adjacentNode, int weight ) {
        graph[orignalNode][adjacentNode] = weight;
        graph[adjacentNode][orignalNode] = weight;
    }
    
    public void bfs() {
        if( nodeSize == 0 ) {
            throw new IndexOutOfBoundsException(" 노드가 비어있습니다.");
        }
        int[] cache = new int[nodeSize];
        Queue<Integer> nodesQue = new LinkedList<>();
        bfsLoopChecking(0, cache, nodesQue);
    }
    
    public void dfs() {
        if( nodeSize == 0 ) {
            throw new IndexOutOfBoundsException(" 노드가 비어있습니다.");
        }
        int[] cache = new int[nodeSize];
        Stack<Integer> nodesStack = new Stack<Integer>();
        dfsLoopChecking(0, cache, nodesStack);
    }
    
    private void bfsLoopChecking( int orignalNode, int[] cache , Queue<Integer> nodesQue ) {
        nodesQue.add( orignalNode );
        while ( !nodesQue.isEmpty() ) {
            Integer nextNodes = nodesQue.poll();
            if( cache[nextNodes] == 0 ){
                cache[nextNodes] = 1;
                System.out.println( nextNodes + " 탐색하였습니다.");
                for( int childNode = 0; childNode <  graph[nextNodes].length; childNode++ ) {
                    if( graph[nextNodes][childNode] != 0 && cache[childNode] == 0 ) {
                        nodesQue.add(childNode);
                    }
                }
            }
        }
    }
    
    private void dfsLoopChecking( int orignalNode, int[] cache , Stack<Integer> nodesStack ) {
        nodesStack.add( orignalNode );
        while ( !nodesStack.isEmpty() ) {
            Integer nextNodes = nodesStack.pop();
            if( cache[nextNodes] == 0 ){
                cache[nextNodes] = 1;
                System.out.println( nextNodes + " 탐색하였습니다.");
                for( int childNode = graph[nextNodes].length -1; childNode > 0; childNode-- ) {
                    if( graph[nextNodes][childNode] != 0 && cache[childNode] == 0 ) {
                        nodesStack.add(childNode);
                    }
                }
            }
        }
    }
}


GraphMatrix graph = new GraphMatrix(5);
graph.push(0, 1, 2);
graph.push(0, 2, 6);
graph.push(0, 4, 6);
graph.push(1, 2, 7);
graph.push(2, 4, 7);
graph.push(2, 3, 1);
graph.push(3, 4, 5);

graph.bfs(); // 0 1 2 4 3
graph.dfs(); // 0 1 2 3 4

참고자료

– 윤성우의 열혈 자료구조 ( C언어 )
– 위키백과

카테고리:

업데이트:

댓글남기기

참고

Javascript ECMAScript6( ES6 - 이크마6 )

업데이트:
12 분 소요

최근 Node.js를 공부하면서 Front-End 개발에 높은 가능성과 흥미를 느끼게 되어 front-end 개발자가 되기 위한 첫 관문인 ES6 문법에 대해 한번 정리하는 게시물을 작성하고자 합니다. 주안점은 javascript 문법을 공부하는 포스트는 아니고 개인적으로 몰랐던 ...

JAVA 알고리즘 2 (Algorithm)

업데이트:
2 분 소요

분할 정복 ( Divide & Conquer ) 분할 정복 알고리즘은 유명한 알고리즘 패턴으로 각개 격파라는 표현을 사용할 수 있습니다. 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출로 이용해 계산하고, 각 부분의 답으로부터 전체의 해답을...

JAVA 알고리즘 1 (Algorithm)

업데이트:
3 분 소요

Step 1 : 알고리즘(Algorithm)란 무엇인가? 알고리즘은 어떠한 입력이 있다면 이 입력에 따라 명령을 명확하게 실행하고, 효과적으로 입력에 따른 결과물을 도출할 수 있다면 알고리즘으로 볼 수 있습니다. 즉 특정 원하는 결과를 도출하기 위해 처리하는 의사결정 과정의 코드...

JAVA 자료구조 1(Data Structure)

업데이트:
11 분 소요

Step 1 : 자료구조(Data Structure)란 무엇인가? 자료 구조란 현실 세계 및 추상적 세계에서의 Data들의 모임 또 이런 Data들의 관계 등 Data들의 집합을 의미합니다. 신중히 선택한 자료구조 혹은 설계된 자료구조는 더 효율적인 알고리즘을 사용할 수 있게 하며...