CS/Data Structure
-
[Data Structure] TrieCS/Data Structure 2021. 12. 29. 18:28
Binary Trie 특징 이진 탐색 트리 형태의 불균형 트리 자료구조이다. 완전 매칭과 부분 매칭에 효율적인 자료구조이다. 해시의 대체로 사용된다. 두 타입의 노드를 가진다. - Branch(link, interior, non-leaf) Node: 데이터 없이 자식 노드의 포인터만 저장 - Element(data, leaf) Node: 데이터 저장 시간복잡도: O(k), k=키의 최대 비트 수 Search(탐색) 탐색할 데이터를 K라고 할 때 i번째 레벨에서 K의 i번째 비트 = 0 → 왼쪽 서브 트리 이동 K의 i번째 비트 = 1 → 오른쪽 서브트리 이동 리프 노드에 저장된 데이터과 탐색할 데이터를 비교한다. Insertion(삽입) Insert 00001 Insert 10011 Insert 0010..
-
[Data Structure] T TreeCS/Data Structure 2021. 12. 28. 16:08
T Tree T 트리는 AVL 트리의 이진 탐색 특성 및 높이 균형과 B 트리의 업데이트와 저장 효율 장점을 모두 취한 MMDB(Main-Memory Database) 최적화 트리이다. Background AVL 트리의 공간 낭비와 잦은 회전 연산을 개선하기 위해 만들어짐 AVL 트리가 하나의 노드에 데이터 한 개만을 가지는 대신 T 트리는 하나의 노드가 n개의 데이터를 가질 수 있도록 개선한 구조임 장점 B 트리의 엔트리가 해당 레코드를 포함하는 데이터 페이지를 가리키고 있는데 반해 T 트리의 각각의 엔트리가 해당 레코드의 메모리 주소를 직접 포인팅하고 있기 때문에 T 트리 인덱스는 논리적 주소를 물리적 주소로 변환하는 작업 없이 원하는 레코드를 빠르게 접근할 수 있음. T 트리는 인덱스 노드에 키 값..
-
[Data Structure] 2-3 TreeCS/Data Structure 2021. 12. 28. 11:58
2-3 Tree 차수가 2 또는 3인 노드를 가지는 트리이다. 완전 균형 트리이다. 많이 쓰이진 않지만, B/B+ 트리, T 트리의 기본 구조이다. 2 Node 3 Node Search(탐색) 2 Node X = key → 탐색 종료 X key → 오른쪽 서브 트리 탐색 3 Node X = 왼쪽 key or 오른쪽 key → 탐색 종료 X 왼쪽 key and X 오른쪽 key → 오른쪽 서브 트리 탐색 Insertion(삽입) 2 Node에 삽입할 경우 2 노드는 3 노드가 되고 작은 데이터가 왼쪽 데이터, 큰 데이터가 오른쪽 데이터가 된다. 3 Node에 삽입할 ..
-
[Data Structure] Minimum Spanning TreeCS/Data Structure 2021. 10. 8. 09:03
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Spanning Tree 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree는 그래프의 최소 연결 부분 그래프이다. n개의 정점을 가지는 그래프의 최소 간선의 수는 n-1개이고, n-1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 된다. 이것이 Spanning Tree이다. Minimum Spanning Tree Spnning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 MST 구현 방법 Kruskal Algorithm 각 단계에서 사이클을 이루지 않는 최소 비용 ..
-
[Data Structure] HashCS/Data Structure 2021. 10. 8. 08:39
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Hash Table hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 가진다. hash function을 사용하여 저장할 데이터과 연관된 고유한 숫자(hashcode)를 만들어 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에 삽입, 삭제 연산 시 shift 연산의 추가적인 비용이 없도록 만들어진 구조이다. Hash Function 저장되는 값들의 key 값을 hash function을 통해 작은 범위의 값들로 바꿔준다. ..
-
[Data Structure] Red-Black TreeCS/Data Structure 2021. 10. 8. 08:00
Red-Black Tree Red-Black Tree는 이진 탐색 트리(Binary Search Tree)기반 트리 형식의 자료구조이다. 이진 탐색 트리는 저장, 삭제, 탐색 시 O(logN)의 시간 복잡도를 갖지만, 한 쪽으로 편향될 경우(최악의 경우) 시간 복잡도가 O(N)이 될 수 있다. 👉 이러한 단점을 보완하기 위해 스스로 높이 균형을 유지하는 Red-Black Tree가 고안됨. 특징 탐색, 삽입, 삭제에 대해 Binary Search Tree의 특성을 사용한다. 각 노드는 Red or Black 색상이 할당된다. Rotation과 Recoloring을 통해 균형을 유지한다. 탐색, 삽입, 삭제 시 O(logn)의 시간복잡도를 가진다. 삽입, 삭제 시 Red-Black Tree의 5가지 조건을..
-
[Data Structure] AVL TreeCS/Data Structure 2021. 10. 7. 14:16
AVL Tree 이진 탐색 트리(Binary Search Tree)기반 트리 형식의 자료구조 이진 탐색 트리가 평균 저장, 삭제, 탐색 시간 복잡도가 평균 O(logN)을 갖지만, 한 쪽으로 편향될 경우(최악의 경우) 시간 복잡도가 O(N)이 될 수 있다. 이러한 단점을 보완하기 위해 스스로 높이 균형을 유지하는 AVL 트리가 고안됨. 특징 AVL 트리는 이진 탐색 트리의 속성을 가진다. 왼쪽, 오른쪽 서브 트리의 높이 차이(Banlance Factor)가 최대 1이다. Balance Factor가 1보다 커지면 회전(rotation)을 통해 균형을 잡는다. AVL 트리의 높이(h)는 logN을 유지하기 때문에 삽입, 검색, 삭제의 시간 복잡도는 O(logN)이다. 회전(Rotation) 삽입, 삭제 시..
-
[Data Structure] HeapCS/Data Structure 2021. 10. 7. 13:20
이 포스팅은 세미나를 위해 https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure를 참고하여 작성하였습니다. Heap 완전 이진 트리(Complete Binary Tree) 기반 자료구조로 반정렬 상태(느슨한 정렬 상태)를 유지한다. 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리 형제 또는 사촌 노드 간의 우선순위는 정해진 것이 없음 힙은 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않음) 종류 최대 힙(Max Heap) key(부모 노드) ≥ key(자식 노드) 최소 힙(Min Heap) key(부모 노드) ≤ key(자식 노드) 시간 복잡도 Max(Mi..