[코드스테이츠] 05_15_TIL : 알고리즘/자료구조 _ Tree / Graph

Today I Lean

알고리즘/자료구조 _ Tree / Graph

 

 

또 다른 구조를 배우다 보니 또 헷갈리지만..

앞으로 나아가다보면 이것또한 이해할 날이 올거라고 생각한다.

 

 

 

배운 것

# Tree

1. Tree 란?

• 단방향 그래프의 한 구조
• 하나의 뿌리로부터 가지가 사방으로 뻗은 형태
• 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
• 하나의 데이터 아래에 여러개의 데이터가 존재할 수 있는 비 선형 구조
• 아래로만 뻗어나가기 대문에 사이클이 없음

 

2. Tree의 구조와 특징

- 구조와 특징
 : 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 각각의 노드(Node)를 연결
 → 자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(Leaf Lode) 라고 함

 

 

- 깊이 (Depth)

 : 루트로부터 하위 계층의 특정 노드까지의 깊이 표현 가능

 → 루트노드는 0, 한 칸씩 아래로 내려갈수록 1씩 더해짐

 

 

- 레벨 (Levle)

 : 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현 가능 

 → 같은 레벨에 나란히 있는 노드를 형제노드 라고 함

 

 

- 높이 (Height)

 : 리프노드를 기준으로 루트까지의 높이를 표현

 → 자식노드중 하나는 자식이 있고, 하나는 리프노드 일때, 부모노드는 자식노드의 가장 높은 height+1의 값을 가짐

 

 

- 서브 트리 (Sub Tree)

 : 큰 트리의 내부에 트리구조를 갖춘 작은 트리를 지칭

 

 

- 용어

* 노드 (Node) : 트리구조를 이루는 모든 개별 데이터

* 루트 (Root) : 트리 구조의 시작점이 되는 노드

* 부모 노드 (Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드

* 자식 노드 (Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드,

* 리프 (Leaf) : 트리 구조의 끝 지점, 자식노드가 없는 노드

 

 

 

 

3. Tree 구현

package Recursion.TreeGraph;
import java.util.*;

public class TreeEx {
    private String value;
    private ArrayList<TreeEx> children;

    public TreeEx() {	// 매개변수가 없는 생성자
        this.value = null;  // value를 null로 초기화
        this.children = null;   // children을 null로 초기화
    }
    public TreeEx(String data) {	// data라는 매개변수가 있는 생성자
        this.value = data;  // value를 data로 초기화
        this.children = null;   // children을 null로 초기화
    }

    public void setValue(String data) { // 현재 노드의 데이터 값을 설정하는 메서드
        this.value = data;  // 전달된 data를 현재노드의 value로 설정
    }

    public String getValue() {      // 현재 노드의 데이터를 반환
        return value;   // 현재노드의 value를 반환
    }

    // addChildNode(value): 입력받은 value를 Tree에 계층적으로 추가할 수 있어야 합니다.
    public void addChildNode(TreeEx node) { // 자식노드를 추가하는 메서드
        if(children == null) {  // children이 null인 경우
            children = new ArrayList<>();   // 새로운 ArratList 인스턴스를 생성해서 자식노드를 저장
        }
        children.add(node); // 전달된 node를 현재 노드의 children목록에 추가
    }

    // removeChildNode(node): 입력받은 node를 Tree에서 삭제할 수 있어야 합니다.
    public void removeChildNode(TreeEx node) {  // 자식노드를 제거하는 메서드
        String data = node.getValue();

        if(children != null) {
            for(int i = 0; i < children.size(); i++) {
                if(children.get(i).getValue().equals(data)) {
                    children.remove(i);
                    return;
                }
                if(children.get(i).children != null) children.get(i).removeChildNode(node);
            }
        }
    }


    // getChildrenNode(): 현재 트리에서 존재하는 children을 리턴합니다.
    public ArrayList<TreeEx> getChildrenNode() {    // 현재 노드의 자식 노드들을 담고 있는 ArrayList 객체를 반환하는 메서드
        return children;
    }


    // contains(value): 트리에 포함된 데이터를 찾을 수 있어야 합니다.
    public boolean contains(String data) {      //재귀를 사용하여 값을 검색합니다.
        if(value.equals(data)) return true; // 전달된 data 값이 현재 노드의 value와 일치하는지 확인, 일치하면 ture 반환

        boolean check;

        if(children != null) {  // children이 null이 아닌경우
            for(int i = 0; i < children.size(); i++) {  // 자식노드를 순회하면서
                check = children.get(i).contains(data, false);  // 각각에 대해 contains(data, false)메서드를 재귀적으로 호출
                                                                // check 변수를 false로 전달해 이전까지 검색된 결과가 없을을 나타냄
                if(check) return true;  // 만약 check가 ture일 경우 ture를 반환
            }
        }
        return false;   // 아닐경우 false 반환
    }

    public boolean contains(String data, boolean check) {      //재귀를 사용하여 값을 검색합니다.
        if(value.equals(data)) return true;

        if(children != null) {
            for(int i = 0; i < children.size(); i++) {
                check = children.get(i).contains(data, check);
            }
        }
        return check;
    }

}

 

 

 

 

4. 이진 탐색 트리 (Binary Search Tree)

- 이진 탐색 이란?

• 정렬된 데이터 중에서 특정 값을 찾기 위한 탐색 알고리즘
• 오름차순으로 정렬된 데이터를 같은 크기의 두 부분으로 나누고, 두 부분중 탐색이 필요한 부분만 탐색하도록 범위를 제한하는 알고리즘

 

- 이진 탐색 트리의 탐색 과정

• 전체 데이터 에서 중간(Root)에서 내가 찾는 값이 있는지 확인 (찾는 값 이라면 탐색 종료)
• 중간값이 찾는 값이 아닐 경우, 찾는 값이 중간값보다 큰지 작은지 확인
• 중간값보다 작을 경우, 데이터의 맨 앞부터 중간값 전까지의 범위를 탐색 범위로 잡고 왼쪽 서브트리 반복탐색
• 중간값보다 클 경우, 데이터의 맨 뒤부터 중간값 바로 뒤까지의 범위를 탐색 범위로 잡고 오른쪽 서브트리 반복탐색

 → 트리 안에 찾는 값이 있을 경우 무조건 트리의 높이(h) 이하의 탐색이 이뤄짐

 → 트리 안에 찾는 값이 없을 경우 최대 h만큼의 연산및 탐색이 진행됨

 

 

- 이진 탐색 트리의 종류와 특징

• 정 이진 트리 (Full Binary tree) : 각 노드가 0개/2개의 자속 노드를 가짐
• 포화 이진 트리 (Perfect Binary tree) : 정 이진트리 && 완전 이진트리 (모든 리프노드의 레벨이 같고, 모든 레벨이 가득 채워져 있음)
• 완전 이진 트리 (Complete Binary tree) : 마지막 레벨을 제외한 노드가 가득 차 있어야 함 (마지막레벨의 노드는 왼쪽이 채워져 있어야 함)

 

- 이진 탐색 트리에서 노드의 추가 / 삭재

 : 추가

 → 노드의 값이 현재 노드보다 작으면 왼쪽, 크면 오른쪽 서브 트리에 추가

 

 : 삭제

 → 리프노드 삭제 (그냥 삭제)

 → 자식 노드가 하나인 경우 (해당 노드의 부모 노드와 자식 노드를 연결)

 → 자식 노드가 두 개인 경우 (해당 노드를 대체할 자식노드를 찾고, 해당 노드와 자식노드 위치를 변경 후 재귀적 실행)

 

 

 

*****이진트리*****

- 이진 탐색 트리 (Binary Search Tree, BST)

 : 이진트리의 일종 (자식 노드가 최대 두개인 노드들로 구성된 트리)

 → 왼쪽 서브트리는 해당노드보다 작은 값 / 오른쪽 서브트리는 해당노드보다 큰 값

 

 

- 힙 (Heap)

 : 완전 이진트리의 일종

 → 각 노드의 값이 자식노드의 값보다 작거나 큰 특정 순서를 유지

 →  최소 힙 = 부모노드의 값 <= 자식노드의 값 /  최대 힙 = 부모노드의 값 >= 자식노드의 값

 

 

- 트라이 (Trie)

 : 문자열을 저장하고 검색하는데 특화된 트리구조

 → 각 노드가 여러 자식노드를 가질수 있음

 → 각 노드는 문자열의 한 문자를 저장

 → 문자열 검색, 자동 완성, IP 라우팅 등의 목적으로 사용됨

 

 

- 레드-블랙 트리

 : 이진 탐색 트리의 또 다른 확장

 → 노드에 색 부여, 특정 규칙을 만족하며 균형을 유지

 → 이 규칙 덕분에 탐색, 삽입, 삭제 연산의 시간 복잡도가 O(log N)을 유지

 

 

 

 

5. Binary Search Tree 구현

package Recursion.TreeGraph;

import java.util.ArrayList;

public class BinarySearchTreeEx {
    // 트리를 구성하는 노드 클래스입니다.
    public static class Node {
        private int data;
        private Node left;
        private Node right;

        /* 생성자 */
        public Node(int data) {
            this.setData(data);
            setLeft(null);
            setRight(null);
        }

        public int getData() {
            return data;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }

        public void setData(int data) {
            this.data = data;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }

    //이진 탐색 트리의 클래스입니다.
    public static class binarySearchTree {
        public Node root;

        public binarySearchTree(){
            root = null;
        }

        // tree에 value를 추가합니다.
        // insert(value): 입력받은 value를 Binary Search에 맞게 Tree에 계층적으로 추가할 수 있어야 합니다.

        public void insert(int data) {
            Node newNode = new Node(data); // 왼쪽, 오른쪽 자식 노드가 null 이며 data 의 값이 저장된 새 노드 생성
            if (root == null) {// 루트 노드가 없을때, 즉 트리가 비어있는 상태일 때,
                root = newNode;
                return;
            }
            if(root.data == data) return;   //중복일때 정지

            Node currentNode = root;
            Node parentNode = null;

            while (true) {
                parentNode = currentNode;

                if (data < currentNode.getData()) { // 해당 노드보다 작을 경우
                    currentNode = currentNode.getLeft();
                    if (currentNode == null) {
                        parentNode.setLeft(newNode);
                        return;
                    }else if(currentNode.data == newNode.data) return;
                } else { // 해당 노드보다 클 경우
                    currentNode = currentNode.getRight();
                    if (currentNode == null) {
                        parentNode.setRight(newNode);
                        return;
                    }else if(currentNode.data == newNode.data) return;
                }
            }
        }

        // tree의 value값을 탐색합니다.
        // contains(value): 트리에 포함된 데이터를 찾을 수 있어야 합니다.
        public boolean contains(int data) {
            Node currentNode = root;
            while (currentNode != null) {
                // 찾는 value값이 노드의 value와 일치한다면, true를 리턴합니다.
                if (currentNode.data == data) {
                    return true;
                }

                if (currentNode.data > data) {
                    // 찾는 value값이 노드의 value 보다 작다면, 현재 노드를 left로 변경후 다시 반복합니다.
                    currentNode = currentNode.left;
                }else {
                    // 찾는 value값이 노드의 value 보다 크다면, 현재 노드를 right로 변경후 다시 반복합니다.
                    currentNode = currentNode.right;
                }
            }
            return false;
        }

  /*
	트리의 순회에 대해 구현을 합니다.
  지금 만드려고 하는 이 순회 메서드는 단지 순회만 하는 것이 아닌, 함수를 매개변수로 받아 콜백 함수에 값을 적용시킨 것을 순회해야 합니다.
  전위 순회를 통해 어떻게 탐색하는지 이해를 한다면 중위와 후위 순회는 쉽게 다가올 것입니다.
	*/

        // 이진 탐색 트리를 전위 순회하는 메서드를 만듭니다.
        // preorder(root, depth, list): 전위 순회를 통해 트리의 모든 요소를 정렬하여 ArrayList 타입으로 반환합니다.
        public ArrayList<Integer> preorderTree(Node root, int depth, ArrayList<Integer> list) {
            if (root != null) { // root(현재 노드)가 null이 아닐때
                list.add(root.getData());   // list에 root 데이터 추가
                preorderTree(root.getLeft(), depth + 1, list);  // left노드의 깊이를 +1 하고, 재귀호출하여 list에 추가
                preorderTree(root.getRight(), depth + 1, list); // Right노드의 깊이를 +1 하고, 재귀호출하여 list에 추가
            }
            return list;
        }

        // inorder(root, depth, list): 중위 순회를 통해 트리의 모든 요소를 정렬하여 ArrayList 타입으로 반환합니다.
        public ArrayList<Integer> inorderTree(Node root, int depth, ArrayList<Integer> list) {
            if (root != null) {
                inorderTree(root.getLeft(), depth + 1, list);
                list.add(root.getData());
                inorderTree(root.getRight(), depth + 1, list);
            }
            return list;
        }

        // postorder(root, depth, list): 후위 순회를 통해 트리의 모든 요소를 정렬하여 ArrayList 타입으로 반환합니다.
        public ArrayList<Integer> postorderTree(Node root, int depth, ArrayList<Integer> list) {
            if (root != null) {
                postorderTree(root.getLeft(), depth + 1, list);
                postorderTree(root.getRight(), depth + 1, list);
                list.add(root.getData());
            }
            return list;
        }
    }

}

 

 

 

 

 

 

# Graph

1. Graph 란?

• 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료 구조
• 자료구조의 그래프는 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크망과 같은 모습을 가짐

 

2. Graph의 구조

- 구조

• 직접적인 관계 : 두 점 사이를 이어주는 선이 있음
• 간접적인 관계 : 몇 개의 점과 선에 걸쳐 이어짐
• 하나의 점 : 정점 (vertex)
• 하나의 선 : 간선 (edge)

 

3. Graph의 표현방식

- 인접 행렬

 : 두 정점을 이어주는 간선이 있다면 이 두 정점은 인접한다 라고 함

 → 두 정점이 이어져 있다면 1(ture), 이어져 있지 않다면 0 (false)

int[][] matrix = new int[][]{
	{0, 0, 1}, // A정점에서 이동 가능한 정점을 나타내는 행
	{1, 0, 1}, // B정점에서 이동 가능한 정점을 나타내는 행
	{1, 0, 0}. // C정점에서 이동 가능한 정점을 나타내는 행
}; 

A의 진출차수는 1개 A → C
[0][2] == 1

B의 진출차수는 2개 B → A, B → C
[1][0] == 1
[1][2] == 1

C의 진출차수는 1개 C → A
[2][0] == 1

 

- 인접 리스트

 : 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현

 → 각 정점마다 하나의 리스트를 가짐

 → 이 리스트는 자신과 인접한 다른 정점을 담고 있음

 → 메모리를 효율적으로 사용해야 할때 사용

(인접행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지함)

 

 

- 용어

• 정점 (vertex) : 노드(node)라고도 함, 데이터가 저장되는 그래프의 기본 원소
• 간선 (edge) : 정점 간의 관계를 나타냄 (정점을 이어주는 선)
• 인접 정접 (adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
• 관계 없음 : 간선으로 연결되지 못한 정점들의 관계
• 가중치 그래프 (weighted Graph) : 연결의 강도가 얼마나 되는지 적혀 있는 그래프 (추가적인 정보 파악 가능)
• 비가중치 그래프 (unweighted Graph) : 특정 정점 두개가 연결되어 있지만, 연결의 강도가 얼마나 되는지 적혀있지 않는 그래프(추가적인 정보를 파악 불가능)
• 무향(무방향) 그래프 (undirected Graph) : 양방향으로 오고갈 수 있는 그래프
• 단방향 그래프 (directed Graph) : 한쪽 방향으로만 갈 수 있는 그래프
• 진입차수 (in-degree) / 진출차수 (out-detree) : 한 정점에 진입하고 진출하는 간선의 수를 나타냄
• 자기 루프 (self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 (다른 정점을 거치지 않음)
• 사이클 (Cycle) : 한 정점에서 출발하여 다시 출발정점으로 돌아갈 수 있는 경우

 

 

 

4. Graph 구현

package Recursion.TreeGraph;

public class GraphEx {
    private int[][] graph;  //graph 라는 빈 2차원배열 생성


    // setGraph(size): 그래프에 size만큼의 버텍스를 추가해야 합니다.
    public void setGraph(int size) {
        graph = new int[size][size];    // graph 변수를 크기가 size인 2차원 정수 배열로 초기화

        for(int i = 0; i < size; i++) {
            for(int j = 0; j < size; j++) {
                graph[i][j] = 0;    // 정점 i와 정점 j가 연결되어있지 않음을 나타냄, 간선의 개수를 초기화
            }
        }
    }

    // getGraph(): 인접 행렬 정보가 담긴 배열을 반환합니다.
    public int[][] getGraph() {
        return graph;
    }

    // addEdge(from, to): fromVertex와 toVertex 사이의 간선을 추가합니다.
    public void addEdge(int from, int to) {
        if(from >= graph.length || to >= graph.length) return;
        graph[from][to] = 1;
    }

    // hasEdge(from, to): fromVertex와 toVertex 사이의 간선이 존재하는지 여부를 Boolean으로 반환해야 합니다.
    public boolean hasEdge(int from, int to) {
        if(from >= graph.length || to >= graph.length) return false;
        else if(graph[from][to] == 1) return true;
        else return false;
    }

    // removeEdge(from, to): fromVertex와 toVertex 사이의 간선을 삭제해야 합니다.
    public void removeEdge(int from, int to) {
        if(from >= graph.length || to >= graph.length) return;
        graph[from][to] = 0;
    }
}

 

 

5. 그래프 인접리스트(Graph Adjacency List) 구현

package Recursion.TreeGraph;

import java.util.ArrayList;

public class GraphAdjacencyListEx {
    private ArrayList<ArrayList<Integer>> graph;

    public GraphAdjacencyListEx() {
        graph = new ArrayList<>();
    }

    // TODO: 정점을 추가합니다.
    // 넘겨받은 size만큼 빈 ArrayList를 값으로 할당합니다.
    // setGraph(size): 그래프에 size 만큼의 버텍스를 추가해야 합니다.
    public void setGraph(int size){
        for(int i = 0; i < size; i++) {
            graph.add(new ArrayList<>());
        }
    }

    //그래프를 반환합니다.
    public ArrayList<ArrayList<Integer>> getGraph() {
        return graph;
    }

    // TODO: 간선을 추가합니다.
    // addEdge(fromVertex, toVertex): fromVertex와 toVertex 사이의 간선을 추가합니다.
    public void addEdge(int from, Integer to) {
        //from, to가 그래프의 크기보다 크거나, 음수일 경우 아무것도 추가하지 않습니다.
        if(from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return;
        //from, to가 정확하게 입력되었을 경우
        // - from의 인접 리스트에 to를 추가하고
        // - to의 인접 리스트에 from를 추가합니다.
        graph.get(from).add(to);
        graph.get(to).add(from);
    }

    // hasEdge(fromvertex, toVertex): fromVertex와 toVertex 사이의 간선이 존재하는지 여부를 Boolean으로 반환해야 합니다,
    public boolean hasEdge(int from, int to) {
        //from, to가 그래프의 크기보다 크거나, 음수일 경우 아무것도 추가하지 않습니다.
        if(from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return false;
            //ArrayList에서 제공하는 contains를 사용하여 boolean 타입의 값을 반환합니다.
        else return graph.get(from).contains(to);
    }

    // removeEdge(fromVertex, toVertex): fromVertex와 toVertex 사이의 간선을 삭제해야 합니다.
    public void removeEdge(int from, int to) {
        //from, to가 그래프의 크기보다 크거나, 음수일 경우 아무것도 제거하지 않습니다.
        if(from < 0 || to < 0 || from >= graph.size() || to >= graph.size()) return;
        //from의 인접 리스트가 to로 이어지는 간선이 존재하는 경우
        if(graph.get(from).contains(to)) {
            //from의 인접 리스트에서 to를 삭제합니다.
            graph.get(from).remove((Integer) to);
        }

        //to의 인접 리스트가 from으로 이어지는 간선이 존재하는 경우
        if(graph.get(to).contains(from)) {
            //to의 인접 리스트에서 from을 삭제합니다.
            graph.get(to).remove((Integer) from);
        }
    }
}

 

 

 

*****

1. 여러가지 트리구조

 

 

 

 

 

Tomorrow Chapter

# Tree Serach Algorithm

# Graph Search Algorithm

# 알아두면 좋은 자료구조

 

 

 

---

 

 

↓ 이전 글 ↓

[코드스테이츠] 05_12_TIL : 알고리즘/자료구조 _ Stack/Queue

 

↓ 코트스테이츠 부트캠프 관련 글 한번에 보기 ↓

'IT/코드스테이츠 부트캠프' 카테고리의 글 목록