이진검색트리 (Binary Search Tree) (정리중,,,,,,)

자료구조
posted by 귀염둥이채원 2019. 3. 4. 18:20

# 이진검색트리 (Binary Search Tree) 개념

- 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조

- 데이터는 정렬이 되어 있어야하며, 탐색 작업에 효율적

- 한 노드에 자식이 최대 2개까지만 존재할 수 있는 트리


1. 모든 노드의 키는 유일하다. 

  - 중복된 데이터를 갖는 노드가 없다는 뜻이다. 

  - 여기서 키의 의미는 노드 안에 들어 있는 데이터 값을 의미한다.


2. 왼쪽 서브 트리의 키들은 루트의  키보다 작다. 

  - 예를 들어 루트노드의 데이터가 5라고 하면, 왼쪽 서브트리에는 무조건 5보다 작은 값들만 존재해야 한다.


3. 오른쪽 서브 트리의 키들은 루트의 키보다 크다.  

  - 위와 같은 원리로 오른쪽에는 루트의 데이터 값보다 더 큰 값들만 존재한다.

4. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 

  - 순환적으로 정의되었다는 뜻이다.

  - 즉 왼쪽 서브트리로 내려가든, 오른쪽 서브트리로 내려가든 동일한 법칙이 적용된다는 뜻이다.


# 이진검색트리 (Binary Search Tree) 예시

- 전화번호부에서 전화번호를 찾거나 

- 서점에서 책을 찾거나 

- 지도에서 목적지를 찾는것


# 이진검색트리 (Binary Search Tree) 목적

- 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logn)으로 빠르지만 자료 입력, 삭제가 불가능합니다.

- 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 O(1)로 효율적이지만 

  탐색하는 데에는 O(n)의 계산복잡성이 발생합니다.

- 이진탐색트리 핵심 연산인 탐색, 삽입, 삭제의 계산복잡성은 모두 O(h) 입니다.


# 이진검색트리 (Binary Search Tree) 용어

successor: 삭제 대상 노드의 오른쪽 서브트리 가운데 최소값

redecessor: 삭제 대상 노드의 왼쪽 서브트리 가운데 최대값


# 시간복잡도 정리

삽입, 삭제, 탐색 모두 최선의 경우(트리의 균형이 잘 잡혀있는 경우, 즉, 왼쪽 오른쪽 자식이 잘 분배되어 있는 경우) O(logN)의 시간복잡도를 가지고, 최악의 경우 (자식 노드가 한쪽으로 쏠려 있는 경우) O(N)이다.

최악의 경우에는 경우에는 균형잡힌 이진 검색트리(balanced binary search tree)으로 사용하면 좋다.


# Binary Searh Tree의 3가지 순회방법

참고 강의: https://www.youtube.com/watch?v=QN1rZYX6QaA&index=2&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP

- Inorder (Left -> Root -> Right)

- Preorder (Root -> Left -> Right)

- Postorder (Left -> Right -> Root)


# 이진검색트리 (Binary Search Tree) 정리

- array와 비교시 tree는 add/remove 연산 속도가 빠르다.

- balanced binary search tree의 경우 insert/delete가 O(log N)이다. (자바에서 TreeMap으로 구현)


# 유투브 영상

https://www.youtube.com/watch?v=9ZZbA2iPjtM&t=3s

https://www.youtube.com/watch?v=9ZZbA2iPjtM&index=8&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP


# 참고사이트

★★https://kingpodo.tistory.com/29

★★http://ivis.kr/images/a/a5/2018_DS_ch09.pdf

★★https://songeunjung92.tistory.com/31

★★https://swalloow.tistory.com/35

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC

https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

https://wkdtjsgur100.github.io/binary-search-tree/

https://mattlee.tistory.com/30

https://kka7.tistory.com/78

'자료구조' 카테고리의 다른 글

큐(Queue) 개념 및 사용법 정리  (0) 2019.03.03
스택(stack) 개념 및 사용법 정리  (0) 2019.03.03
배열 리스트(ArrayList) 개념 및 사용법  (0) 2019.03.03
자바 배열 사용법 정리  (0) 2019.03.03

큐(Queue) 개념 및 사용법 정리

자료구조
posted by 귀염둥이채원 2019. 3. 3. 22:41

# 큐(Queue)란?

- 먼저 삽입된 데이터가 가장 먼저 제거되는 선입선출(FIFO - First In First Out) 형태의 자료구조


# 큐(Queue) API

* Object element(): 저장된 요소를 불러옴

* boolean offer(Object o ): Queue에 객체 저장 ( true:성공, false:실패) 반환

* Object peek(): 저장된 객체를 반환 / 없을경우 Null 을 반환

* Object poll(): 객체를 꺼내온다 / 꺼낸객체는 사라짐


# 큐(Queue) 클래스 사용법

LinkedList 클래스로 Queue를 인스턴스화하여 사용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    static Queue <Integer> q;
    public static void main(String[] args) {
        // queue는 LinkedList 클래스로 선언한다.
        q = new LinkedList<Integer>();
        
        // queue 초기화
        q.clear();
        
        // queue에 데이터 1 삽입
        q.add(1);
        
        // queue에 데이터 5 삽입
        q.add(5);
        
        // queue의 size 출력
        System.out.println("queue size: " +q.size());
        
        // queue에서 데이터 확인 및 제거
        System.out.println("data(pool): " +q.poll());
        
        // queue에서 데이터 확인
        System.out.println("data(peek): " +q.peek());
        
        // queue에서 데이터 확인 및 제거
        System.out.println("data(pool): " +q.poll());
        
        // queue에 데이터가 존재하는지 확인
        if (q.isEmpty()) {
            System.out.println("queue is empty");
        }
    }
}
 
/*********** 결과 ***************
queue size: 2
data(pool): 1
data(peek): 5
data(pool): 5
queue is empty
*/
cs


# 큐(Queue) 구현 - 배열 사용

# 문제

주어진 N(2<= N <=100)개의 수를 순서대로 Queue에 넣은 후 하나씩 꺼내 화면에 출력


# 입력

2

5

1 2 3 4 5 

5 

5 4 2 3 1


# 출력

#1 1 2 3 4 5 

#2 5 4 2 3 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.io.FileInputStream;
import java.util.Scanner;
 
class Main2 {
    static final int MAX_N = 100;
 
    static int front;
    static int rear;
    static int queue[] = new int[MAX_N];
 
    static void queueInit() {
        front = 0;
        rear = 0;
    }
 
    static boolean queueIsEmpty() {
        return (front == rear);
    }
 
    static boolean queueIsFull() {
        if ((front + 1) % MAX_N == rear) {
            return true;
        } else {
            return false;
        }
    }
 
    static boolean queueEnqueue(int value) {
        if (queueIsFull()) {
            System.out.print("queue is full!");
            return false;
        }
        queue[front] = value;
        front++;
        if (front >= MAX_N) {
            front = MAX_N;
        }
 
        return true;
    }
 
    static Integer queueDequeue() {
        if (queueIsEmpty()) {
            System.out.print("queue is empty!");
            return null;
        }
 
        Integer value = new Integer(queue[rear]);
 
        rear++;
        if (rear >= MAX_N) {
            rear = MAX_N;
        }
        return value;
    }
 
    public static void main(String arg[]) throws Exception {
        //System.setIn(new FileInputStream("c:\\boj\\sample.txt"));
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
 
        for (int test_case = 1; test_case <= T; test_case++) {
            int N = sc.nextInt();
 
            queueInit();
            for (int i = 0; i < N; i++) {
                int value = sc.nextInt();
                queueEnqueue(value);
            }
 
            System.out.print("#" + test_case + " ");
 
            while (!queueIsEmpty()) {
                Integer value = queueDequeue();
                if (value != null) {
                    System.out.print(value.intValue() + " ");
                }
            }
            System.out.println();
        }
        sc.close();
    }
}
cs


# 참고사이트

https://hyeonstorage.tistory.com/263

https://swalloow.tistory.com/32

https://gamjatwigim.tistory.com/72

'자료구조' 카테고리의 다른 글

이진검색트리 (Binary Search Tree) (정리중,,,,,,)  (0) 2019.03.04
스택(stack) 개념 및 사용법 정리  (0) 2019.03.03
배열 리스트(ArrayList) 개념 및 사용법  (0) 2019.03.03
자바 배열 사용법 정리  (0) 2019.03.03

스택(stack) 개념 및 사용법 정리

자료구조
posted by 귀염둥이채원 2019. 3. 3. 18:39

# 스택(stack)이란?

- 스택(Stack)은 사전적으로 '더미', '쌓아 올림' 이라는 의미

- 후입선출(LIFO - Last In First Out) 형태의 자료구조

  - 제일 마지막에 저장한 데이터를 제일 먼저 꺼내는 구조

  - 책을 바닥에 순서대로 쌓아 놓고, 다시 책을 꺼낼때 마지막에 쌓은 것부터 꺼내는 방식

- Stack 클래스는 LIFO 자료구조를 구현한 클래스로 JAVA에서 '컬렉션 프레임워크' 로 이미 제공

- 스택을 구현하는 방법은 배열과 연결 리스트가 있음


# 스택(stack) API

pop(추출)

 - 가장 최 상위에 위치한 자료를 추출한 후에 스택에서 제거한다

 - 이 작업은 O(1)의 복잡도를 가진다


push(삽입)

 - 스택의 최 상위에 새로운 자료를 삽입한다

 - 이 작업은 O(1)의 복잡도를 가진다


isEmpty

 - 스택이 empty 상태인지 확인한다


clear

 - 스택에 존재하는 모든 자료들을 삭제한다


peek

 - 가장 최 상위에 위치한 자료를 추출한다


pop 메소드와는 달리 스택에서 제거하지는 않는다.

 - 이 작업은 O(1)의 복잡도를 가진다



# 스택(stack) 클래스 사용법

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.Stack;
 
public class Main {
    static Stack <Integer> stack;
    
    public static void main(String[] args) {
        stack = new Stack <Integer>();
        
        // stack 초기화
        stack.clear();
        
        // stack에 데이터 1 삽입
        stack.add(1);
        
        // stack에 대이터 5 삽입
        stack.add(5);
        
        // stack의 size 출력
        System.out.println("stack size = " +stack.size());
        
        // stack에서 데이터 확인 및 제거
        System.out.println("data = " +stack.pop());
        
        // stack에서 데이터 확인
        System.out.println("data = " +stack.peek());
        
        // stack에서 데이터 확인 및 제거
        stack.pop();
 
        // stack에 데이터가 없는지 확인
        if (stack.isEmpty()) {
            System.out.println("stack is empty");
        }
    }
}
 
/********** 결과 **********
stack size = 2
data = 5
data = 1
stack is empty
*/
cs


# 스택(Stack) 구현 - 배열 사용

# 문제

N(2<= N <=100)개의 수를 순서대로 Stack에 넣은 후 하나씩 꺼내 화면에 출력


# 입력

2 // 테스트 케이스 수 

5 // 데이터 크기 

1 2 3 4 5 

5 

5 4 2 3 1


# 출력

#1 5 4 3 2 1 

#2 1 3 2 4 5


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.util.Scanner;
 
class Main {
    static final int MAX_N = 100;
 
    static int top;
    static int stack[] = new int[MAX_N];
 
    static void stackInit() {
        top = 0;
    }
 
    static boolean stackIsEmpty() {
        return (top == 0);
    }
 
    static boolean stackIsFull() {
        return (top == MAX_N);
    }
 
    static boolean stackPush(int value) {
        if (stackIsFull()) {
            System.out.println("stack overflow!");
            return false;
        }
        stack[top] = value;
        top++;
 
        return true;
    }
 
    static Integer stackPop() {
        if (top == 0) {
            System.out.println("stack is empty!");
            return null;
        }
 
        top--;
        Integer value = new Integer(stack[top]);
 
        return value;
    }
 
    public static void main(String arg[]) throws Exception {
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
 
        for (int test_case = 1; test_case <= T; test_case++) {
            int N = sc.nextInt();
 
            stackInit();
            for (int i = 0; i < N; i++) {
                int value = sc.nextInt();
                stackPush(value);
            }
 
            System.out.print("#" + test_case + " ");
 
            while (!stackIsEmpty()) {
                Integer value = stackPop();
                if (value != null) {
                    System.out.print(value.intValue() + " ");
                }
            }
            System.out.println();
        }
        sc.close();
    }
}
cs


# 참고사이트

https://hyeonstorage.tistory.com/262

https://gompangs.tistory.com/5

https://ehclub.co.kr/3059

https://songeunjung92.tistory.com/18

'자료구조' 카테고리의 다른 글

이진검색트리 (Binary Search Tree) (정리중,,,,,,)  (0) 2019.03.04
큐(Queue) 개념 및 사용법 정리  (0) 2019.03.03
배열 리스트(ArrayList) 개념 및 사용법  (0) 2019.03.03
자바 배열 사용법 정리  (0) 2019.03.03

배열 리스트(ArrayList) 개념 및 사용법

자료구조
posted by 귀염둥이채원 2019. 3. 3. 17:52

# 배열 리스트(ArrayList)

- 동적 할당이 가능한 리스트의 장점 + 인덱스 접근이 가능한 배열을 장점을 합친 자료구조


# 장점

- 인덱스로 데이터를 상수 시간만에 접근이 가능 

- 연결 리스트처럼 동적으로 크기를 늘릴수 있음


# 단점

- 인덱스를 가지고 있어 삽입/삭제 연산시 O(N)의 시간복잡도가 걸린다 (배열의 단점)


# ArrayList 샘플 소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.io.FileNotFoundException;
import java.util.ArrayList;
 
public class Main {
    static ArrayList <Integer> v;
    
    public static void main(String[] args) throws FileNotFoundException {
        v = new ArrayList <Integer> ();
        
        // ArrayList 초기화
        v.clear();
        
        // ArrayList에 데이터 1 삽입
        v.add(1);
        
        // ArrayList에 데이터 5 삽입
        v.add(5);
        
        // 첫번째 원소 출력
        System.out.println("v[0]: " +v.get(0));
        
        // 두번째 원소 출력
        System.out.println("v[1]: " +v.get(1));
        
        // ArrayList의 원소 개수 출력
        System.out.println("v.size: " +v.size());
    }
}
 
/********** 결과 **********
v[0]: 1
v[1]: 5
v.size: 2
*/
cs


'자료구조' 카테고리의 다른 글

이진검색트리 (Binary Search Tree) (정리중,,,,,,)  (0) 2019.03.04
큐(Queue) 개념 및 사용법 정리  (0) 2019.03.03
스택(stack) 개념 및 사용법 정리  (0) 2019.03.03
자바 배열 사용법 정리  (0) 2019.03.03

자바 배열 사용법 정리

자료구조
posted by 귀염둥이채원 2019. 3. 3. 17:42

자바 배열 사용법입니다.


장점: 상수시간 O(1)만에 해당 데이터를 찾을수 있어 빠르다.

단점: 인덱스 찾이 고정되어 있어 불필요한 공간을 생성


# 1차원 배열 예제

1
2
3
4
5
6
7
8
9
10
11
12
public class Main {
    static int arr[];
    public static void main(String[] args) throws FileNotFoundException {
        arr = new int[5];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 3;
        arr[3] = 4;
        arr[4] = 5;
        System.out.println("arr[2]: " +arr[2]);
    }
}
cs


# 2차원 배열 예제

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Main {
    static int arr[][];
    public static void main(String[] args) throws FileNotFoundException {
        arr = new int[3][2];
        arr[0][0] = 1;
        arr[0][1] = 2;
        arr[1][0] = 3;
        arr[1][1] = 4;
        arr[2][0] = 5;
        arr[2][1] = 6;
        System.out.println("arr[2][1]: " +arr[2][1]);
    }
}
cs


'자료구조' 카테고리의 다른 글

이진검색트리 (Binary Search Tree) (정리중,,,,,,)  (0) 2019.03.04
큐(Queue) 개념 및 사용법 정리  (0) 2019.03.03
스택(stack) 개념 및 사용법 정리  (0) 2019.03.03
배열 리스트(ArrayList) 개념 및 사용법  (0) 2019.03.03

티스토리툴바