DataStructure
-
[ Open Data Structures ] - Array Queue - 1DataStructure 2021. 2. 27. 22:31
Array Queue : An Array-Based Queue FIFO ( First In First Out ) 자료구조인 Array Queue를 가볍게 만들어본다. Array Stack은 배열에 들어온 순서( Add(x) Operation )대로 다시 나갔다( Remove() Operation ). 가만 생각해보면 Array Stack을 FIFO Queue를 구현하는데 선택하는 것은 비효율적인 선택이라고 할 수 있다. 왜냐하면, 배열의 한쪽 끝에서 Add를 하면 Remove는 반드시 정반대에서 수행해야 하기 때문이다. 두 작업 중 하나는 반드시 배열의 머리에서 수행되어야만 한다면 다른 하나는 반드시 꼬리에서 수행되어야만 하고 이는 원소의 개수 n에 비례한 Running time을 요구하게 된다. Que..
-
[ Open Data Structures ] - Array Stack - 2DataStructure 2021. 2. 24. 16:23
Growing and Shrinking Resize() method는 꽤 직관적이다. 크기가 기존 mSize의 두 배인 새로운 배열(resizedArray)을 만들고 mSize개의 원소를 새로운 배열에 복사한다. 그리고 Array Stack class의 mArr가 resizedArray를 가리키게 만든다. Resize() 시간을 계산하는 것은 어렵지 않다. 2*mSize의 새로운 배열 resizedArray를 만들고 mSize개의 원소를 복사한다. 따라서, O(mSize)의 time을 요구한다. 전의 Running time을 계산할 땐 이 Resize()를 무시했다. 여기서는 Amortised analysis기법을 사용하여 분석해보기로 한다. 이것을 통해서 Add/Remove가 각각 수행될 비용을 계산하..
-
[ Open Data Structures ] - ArrayStack - 1DataStructure 2021. 2. 23. 21:09
Array Based List 이번 장에선 Array를 사용하여 정보를 저장하는 List와 Queue의 Interfece에 대해 공부할 것입니다. 후에 Interface의 공통된 Operation을 정리하는데 기본적으로 List interface는 다음과 같은 네 가지의 기능을 제공합니다. Get, Set, Add, Remove. 다음은 각각의 Data Structure의 각 Operation에 대한 Running time을 나타낸 표입니다. 단일 배열을 사용하여 정보를 저장하는 자료구조는 공통적인 장단점이 존재합니다. 1. 배열은 격납된 어떤 정보든 접근하는데에 상수시간만을 요구합니다. 덕분에 Get(i)와 Set(i, x)의 수행시간도 상수 시간 내에 해결을 할 수 있게 됩니다. 2. 배열은 Dyna..
-
[ Open Data Structures ] - Red-Black Tree - 5DataStructure 2021. 1. 28. 16:59
Deletion 삭제에 관한 내장 함수들은 비교적 구현하기가 어렵습니다. 천천히, 침착하게 Node를 삭제하며 마주치는 모든 상황을 따져가면서 공부합니다. 삭제에 관한 기본적이고 1차적인 과정은 Binary Search Tree에서 사용했던 Splice를 수행하는 것과 같습니다. 삭제하려는 node x의 Data를 node x의 Right subtree에서 가장 작은 Node u의 Data와 바꾼 후에, x의 데이터를 갖고 있는 노드 u를 삭제하는 것입니다. 물론, Binary Search Tree의 성질에 의해 x 의 Left Subtree에서 가장 큰 값을 x와 교환해도 큰 상관은 없지만 여기선 전자의 방법을 채택합니다. Splice(x)의 경우, 하나 또는 하나 이하의 Child node를 가진 N..
-
[ Open Data Structures ] - Red-Black Trees - 4DataStructure 2021. 1. 25. 23:10
Add operation Red-Black Tree(이하 RBT)가 기본적으로 지켜야 할 두 가지 Propertise인 Black-Height, No-Red-Edge에 이어 Left-Leaning의 성질을 추가했고 이에 따라 본격적인 Add Operation을 구현합니다. RBT를 구현하는 방법은 여러가지가 있으니 어떤 방법이 더 있는지 확인해보는 것이 좋겠습니다. RBT에서 Addition을 내장하기 위해서는 가장 먼저 일반적인 Binary Search Tree에서 수행했던 새로운 Leaf node를 추가하는 방식을 채택할 것입니다. 즉 새로운 node u에 데이터 x를 저장하고 Red라는 성질을 추가로 제공하는 것입니다. 하지만 이 글에서 사용하는 방법은 저장할 데이터를 받아 내부에서 Node를 생성..
-
[ Open Data Structures ] Red-Black Trees - 3DataStructure 2021. 1. 23. 16:53
2-4 Tree와 Red-Black Tree(이하 RBT)가 명백한 관계가 있음을 보였습니다. 추가로 Add/Remove Operation을 RBT에서도 효과적으로 수행할 수 있다는 사실도 확인했습니다. 이미, Binary Search Tree에서 새로운 Leaf node를 추가함으로써 Add operation을 구현할 수 있다는 점은 알고 있습니다. 따라서 2-4 Tree에서 보았던 5개의 Children node를 분할하는 Split method를 RBT에 적용하는 것이 핵심이 될 것입니다. 5개의 Children node를 가진 node는 RBT에서는 하나의 Black node를 가진 Red node와 red node하나, 총 두 개의 Red node를 Children node로 가지는 Black ..
-
[ Open Data Structures ] - Red-Black Trees - 2DataStructure 2021. 1. 22. 17:36
Red-Black Tree는 2-4Tree를 Binary Search Tree의 역할을 효율적으로 시뮬레이션하기 위해 탄생했습니다. 따라서, 2-4trees 와는 다르게 Children node가 두 개 뿐이며 각 Node가 Red(0) 또는 Black(1) 두 가지 색 중 하나를 갖는 Binary Search Tree라고 볼 수 있습니다. 이 점은 Figure b-1과 Figure b-2를 통해 개략적으로 이해할 수 있습니다. 다음과 같은 Property가 RBT를 논의함에 있어서 언제나 참인 것으로 받아들입니다. Property 2.1. Root node에서 시작하여 모든 Leaf node까지 이르는 경로 상의 검은색(Black coloured node)의 합은 같다. (Black-height) Pr..
-
[ Open Data Structures ] - Red-Black Trees - 1DataStructure 2021. 1. 22. 13:47
Red-Black Tree(이하 RBT)는 다방면으로 사용되는 자료구입니다. JAVA Collections Framework, C++ STL를 비롯한 많은 Library implementation에 등장하며 Linux OS system kernel에서도 찾아볼 수 있습니다. 이렇듯 이 자료구조가 사랑받는 이유엔 다음과 같은 이유가 있습니다. 1. n개의 값을 가지는 RBT는 높아봐야 2logn의 높이를 가진다. 2. Add/Remove Operation이 최악의 경우 O(logn)의 Running Time을 가진다. 3. Add/Remove Operation 중 수행되는 Rotation의 대략적인 수행 횟수는 상수[Constant]이다. 1, 2번의 특징은 Skiplist와 Treap의 장점을 충분히 뛰..