CS/자료구조
-
자료구조 - 해시테이블CS/자료구조 2021. 3. 8. 20:01
해시테이블 해시테이블 이란? Key, Value의 쌍으로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있다. 내부적으로 배열을 사용하여 데이터를 저장하고, 각각의 key값에 해시 함수를 적용해 배열의 유일한 인덱스를 생성한다. 이 인덱스를 활용해 값을 저장하거나 검색하게 된다. 해시 함수 저장할 데이터의 key를 고유한 인덱스로 변환하여 해시 테이블에 저장하기 위해 사용되는 함수. 대표적 해시 함수로는 아래 4가지가 있다. Division Method: 입력값을 테이블의 크기로 나누어 계산한다. Digit Fording: key의 문자열을 아스키 코드로 바꾸고 값을 합한 데이터를 주소로 사용한다. Multiplication Method: 특정한 값을 사용해 연산을 하여 주소로 사용한다..
-
자료구조 - BTreeCS/자료구조 2021. 2. 22. 19:28
B-Tree B-tree B의 의미는 balance를 의미한다. 군형잡힌 다진검색트리로 다음의 성질을 만족한다. (다진검색트리란 자식을 여러개 갖는 트리를 말한다.) 루트 제외 모든 노드는 최소 k/2 ~ k개의 키를 갖는다. 모든 리프노드는 같은 깊이를 갖는다. 디스크에 저장하는 cost를 최소화하여 데이터베이스에서 주로 사용된다. 최악의 경우 디스크 접근 횟수를 줄일 수 있다. B-tree의 삽입 삽입 후 오퍼플로우가 발생하면(키의 수가 k보다 많으면) 형제 노드(양 옆의 노드) 중 여유가 있는 노드가 있으면 남는 키를 형제 노드에게 삽입해 준다. 없으면 오버플로가 발생한 레코드를 둘로 분할하고 가운데 키를 부모 노드로 넘긴다. B-tree의 삭제 삭제 후 언더플로우가 발생하면(키의 수가 k/2보다 ..
-
자료구조 - 이진검색트리(ALV, RED-BLACK)CS/자료구조 2021. 2. 21. 20:10
Balanced Binary Search Tree AVL트리란? 균형잡힌 이진검색 트리이다. 오른쪽 서브트리와 왼쪽 서브트리의 높이 차를 1까지만 허용한다. 1보다 큰 경우 tree modification연산을 진행해여 재배열 한다. 트리의 높이는 항상 logn으로 연산에 대한 시간복잡도도 O(logn)이 된다. Red-Black Tree란? 균형잡힌 이진검색 트리이다. 트리의 모든 노드에 블랙 또는 레드 색을 칠하되 레드블랙 특성을 만족해야한다. 특성은 다음과 같다. 루트는 블랙이다. 모든 리프는 블랙이다. 레드 노드는 연속으로 올 수 없다. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다. 여기서 리프 노드는 일반적인 의미의 리프노드와 다르다. 모든 NIL포인터가..
-
자료구조 - 이진검색트리CS/자료구조 2021. 2. 20. 20:09
Binary Search Tree 이진검색트리 이진트리 이면서 각 노드에 하나의 키를 저장하고, 루트 노드에 대해 왼쪽 서브트리에 있는 키들은 루트의 키 보다 작거나 같고, 오른쪽 서브트리에 있는 키들은 루트의 키 보다 크거나 같다. 트리의 높이는 평균 logn으로 연산에 대한 시간 복잡도도 평균 O(logn)이다. 이진검색트리의 연산 Search: 키를 탐색한다. 시간복잡도는 O(h). h는 트리의 높이를 의미한다. Succesor: 노드 x의 Succesor란 x의 키보다 크면서 가장 작은키를 가진 노드를 탐색한다. 이때 모든 키들이 서로 다르다고 가정한다. 시간복잡도는 O(h). Predecessor: 노드 x의 Predecessor란 x의 키보다 작으면서 가장 큰 키를 가진 노드를 탐색한다. 이때..
-
자료구조 - 이진트리CS/자료구조 2021. 2. 18. 23:03
이진트리 트리 노드가 N개인 트리는 N - 1개의 링크를 가진다. 트리의 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의 두 노드간의 경로도 유일하다. 이진트리 각 노드는 최대 2개의 자식노드를 가진다. 종류 perfect binary tree 이진 트리의 모든 노드가 꽉 차있는 트리이다. 높이가 h인 perfect binary tree는 2^h - 1개의 노드를 가진다. full binary tree 이진 트리의 모든 노드가 0개 또는 2개의 자식을 갖는 트리이다. complete binary tree 이진 트리에서 노드가 왼쪽에서 오른쪽 순서로 순차적으로 존재하는 트리이다. 각 노드는 하나의 데이터 필드와 왼쪽 자식, 오른쪽 자식의 주소를 저장한다. 노드가 N개인 full, complete b..
-
자료구조 - HeapCS/자료구조 2021. 2. 18. 22:00
Heap Heap 완전 이진 트리이며 최대, 최소값만을 필요로 할 때 적합한 자료구조이다. 시간복잡도- 요소의 개수가 n개일때 삽입, 삭제시 트리의 높이 만큼 소요된다. insert: O(nlogn) delete: O(nlogn) 구현 with JAVA 최대힙 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 public class maxHeap{ private int[] heap; private int idx..
-
자료구조 - QueueCS/자료구조 2021. 2. 17. 21:38
Queue queue 자료구조 선입선출 알고리즘으로 먼저 들어온 데이터를 먼저 반환한다. 시간 복잡도 insert: O(1) delete: O(1) search: O(n) 구현 with JAVA 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 85 86 87 88 89 90 91 //큐를 만들기 위해 필요한 연결 노드 정보 ..
-
자료구조 - StackCS/자료구조 2021. 2. 17. 21:22
Stack stack 자료구조 후입선출 알고리즘으로 나중에 들어온 데이터를 먼저 반환한다. 시간 복잡도 insert: O(1) delete: O(1) search: O(n) 구현 with JAVA 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 public class Stack { private int top; private int size; private int[] arr; //생성자 public stack(int size) { top = -1; this.size = size; arr = new int[size]; } pu..