NHN Academy - 2024.09.06(Fri)

Module 18: Thread

지금까지 구현한 코드들은 안보고 작성할 수 있어야 함!

 

자료구조 

- 선형 : 배열 / 리스트(Array, Linked...)

- 비선형 : 트리 / 그래프

- 파일 : 정렬 / 비정렬(Heap)

 

데이터베이스 : 주제가 같은 데이터들을 모아둔 것

 

root - usr / hi / opt / cmnt

 

운영체제 분류 3가지

1. Unix                2. Linux              3. Window

 

트리 Tree

비선형 자료구조

root가 꼭 필요 / 반드시 1개

 

Equality selection : 힙 Heap

인덱스 트리( = 펜윅 트리 ) : B-Tree

 

어떻게 순회하는 것이 트리의 데이터를 빨리 읽어 들이나?( = 처음부터 데이터를 저장할 때, 정렬되어 있는 트리를 만들 수 있다! )

1. 깊이 우선 순회

2. 너비 우선 순회

 

삽입 가장빠른 자료구조 = Linked-List

Scan 가장빠른 자료구조 = 배열

이진 균형 트리 가 성능이 더 좋더라!

 

B+ Tree

- 인덱스를 기본 3 ~ 4로 설정

- 바이너리 트리와 개념적으로 비슷 → key 값으로 정렬 / childern 노드가 여러개

- 각 노드가를 디스크에 저장

- 데이터는 leaf 노드에만 O → 나머지 노드는 leaf 노드로 가기 위한 index를 가짐

- 각 노드에 sibling(형제)으로 가는 포인터가 O

 

B* Tree

- 균형을 유지하기 위한 연산에서 노드의 생성과 부가적인 연산을 최소화하기 위해 등장

- 자식 노드 : 최소 M/2개의 데이터만 가짐(B- Tree) → M*2/3개 데이터 가짐

- 노드가 가득 찼을 때 분열 X, 형제 노드로 재배치

 

B- Tree

- 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종

- 이진 트리의 확장

- 1개의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조

 

Balanced Tree

- O(log n) 시간에 insert와 find를 할 수 O

- Red-Black Tree

 

이진 탐색 트리의 원리

 : 1번 확인 시, 원소의 개수가 절반씩 줄어듬 → 완전 이진 트리는 탐색 시간 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도를 가짐

 : 찾는 값이 부모 노드보다 작을 경우 왼쪽, 찾는 값이 부모 노드보다 클 경우 오른쪽 으로 나가면서 방문

 

이진 탐색 트리 예제 - 탐색

항상 부모 노드가 왼쪽 자식보다는 크고, 오른쪽 자식보다는 작다

이진 탐색 트리 예제 - 삭제

 - 자식이 없는 경우 : 삭제할 노드의 자식이 없는 경우 단순히 제거

 - 자식이 하나만 존재하는 경우 : 삭제할 노드의 자리에 자식 노드를 추가

 - 자식이 둘 다 존재하는 경우 : 그 다음 삭제할 노드의 자리에 자기 다음으로 큰 노드를 추가

 

트리를 어떻게 읽을까?

1. 순회 방법 : 왼 - 루트 - 오

2. Pre Order : 루트 - 왼 - 오

3. Post Order : 왼 - 오 - 루트

 

AST  Abstract Syntax Tree    =   추상 구문 트리

 

Iterator

: 자바의 컬렉션(Collection)에 저장되어 있는 요소들을 순회하는 인터페이스

: Iterator<T> iterator = Collection.iterator();

 

✮ Iterable vs Iterator

- iterable 객체  - 반복 가능한 객체  - 대표적인 타입 : list, dict, set, str, bytes, tuple, range  - for문(반복문), range, enumerate 에서 iterable한 타입과     iterable한 타입을 확인하는 방법 O

iterator 객체  - 값을 차례대로 꺼낼 수 있는 객체  - iterable 객체를 내장함수, iterable 객체의 메소드로 객체 생성 O  - 파이썬 내장함수 iter()로 iterator 객체를 만들기 O  - REPL을 실행 O

 

 

BinaryTree.java ( BinaryTree implements Iterable )

import java.util.Iterator;
import java.util.Stack;

class Node { // 꼭 static 으로 만들 것!
    int key;
    Node left;
    Node right;

    public Node(int key) {
        this.key = key;
        left = right = null; // 이렇게 적어도 동작 O
    }
}

public class BinaryTree implements Iterable<Integer> {
    Node root;

    public BinaryTree() {
        this.root = null;
    }

    public Node getRootNode() {
        return this.root;
    }

    public void add(int key) {
        root = addNode(root, key);
    }
    private Node addNode(Node root, int key) {
        if(root == null) {
            root = new Node(key);
            return root;
        }
        if(key < root.key) {
            root.left = addNode(root.left, key);
        }
        else if(key > root.key) {
            root.right = addNode(root.right, key);
        }
        return root;
    }
    @Override
    public Iterator<Integer> iterator() {
        return new InOrderIterator(root);
    }
    private class InOrderIterator implements Iterator<Integer> {
        private Stack<Node> stack = new Stack<>();
        private Node currentNode;
        
        public InOrderIterator(Node root) {
            currentNode = root;
            pushLeftNodes(currentNode);
        }
        private void pushLeftNodes(Node node) {
            while(node != null) {
                stack.push(node);
                node = node.left;                
            }
        }

        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        @Override
        public Integer next() {
            // if(hasNext()) {
            //     throw new java.util.NoSuchElementException();
            // }
            Node node = stack.pop();
            pushLeftNodes(node.right);
            return node.key;
        }
    }

    public void InOrder(Node node) {
        if(node != null) {
            InOrder(node.left);
            System.out.println(node.key);
            InOrder(node.right);
        }
    }
    public void PreOrder(Node node) {
        if(node != null) {
            System.out.println(node.key);
            InOrder(node.left);
            InOrder(node.right);
        }
    }
    public void PostOrder(Node node) {
        if(node != null) {
            InOrder(node.left);
            InOrder(node.right);
            System.out.println(node.key);
        }
    }
}

Test.java 로 실행하기

public class Test {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.add(4123);
        tree.add(321);
        tree.add(435);
        tree.add(243);
        tree.add(333);
        tree.add(11);
        tree.add(1213);
        tree.add(142);

        // tree.InOrder(tree.getRootNode());
        // System.out.println();
        // tree.PreOrder(tree.getRootNode());
        // System.out.println();
        // tree.PostOrder(tree.getRootNode());

        for(Integer i : tree) {
            System.out.print(i + " ");
        }
    }
}

 

Collection

: 자바에서 제공하는 자료구조들의 인터페이스

: List, ArrayList, Stack, Quque, LinkedList 등이 이를 상속받음

: 컬렉션 인터페이스를 상속받는 클래스들에 대해 Iterator 인터페이스 사용이 가능 O

 

✮ Set vs List

Set  - 순서없고 중복이 존재할 수 없는 자료구조  - 인덱스를 사용 X  - 인덱스 매개변수 X  - EX> 집합에 빗대어 생각하면 좋을만한 자료구조 장점  - 빠른 검색 속도를 가짐  - 인덱스가 따로 존재하지 않기 때문에 iterator를 사용  - Iterator는 자바 기준으로 hasNext(), next(), remove()함수를     사용해, 어떤 컬렉션이라도 동일한 방식으로 접근하여 그 항목들에     접근할 수 있는 방법을 제공하는 것 (자바의 특징 - 다형성)

List  - 순서와 중복이 허용되는 자료구조  - 내부적으로 인덱스를 가지고 있을 수도 O  - elements 데이터 : 다음 데이터 순서가 있다는 게 중요한 자료구조 주요 기능  - 처음, 끝, 중간에 엘리먼트를 추가/삭제하는 기능  - 엘리먼트들이 리스트에 저장되어있을 때     우리가 새로운 데이터를 처음, 중간, 끝에 추가/삭제를 할 수 있으며,     그 과정에서 빈 공간이 생겼을 때에 하나씩 밀리면서 채움  - 리스트에 데이터가 있는지를 체크하는 기능  - 리스트의 모든 데이터에 접근할 수 있는 기능 장점  - 가변적인 배열, 배열이 자동으로 늘어남  - 비어있는 데이터가 없다. 단점  - 원하는 데이터가 뒤쪽에 위치하는 경우, 속도의 문제가 있을 수 O     WHY? 순회를 하기 때문에

 

---