DataStructure
-
[ Open Data Structures ] - ScapeGoat - 2DataStructure 2021. 1. 16. 14:14
ScapeGoat를 찾는데 있어서 사용했던 Lemma에 대한 증명으로 ScapeGoat는 마무리합니다. Lemma 1. ScapeGoat Tree안에 있는 임의의 Node u가 Figure 1.2[Depth = h]를 만족한다면 u부터 root node까지 이르는 경로 상에 Figure 1.1을 만족하는 어떤 node w는 반드시 존재한다. Proof ) 모순을 통해 증명하기 위해, 어떤 node u부터 root node까지의 경로 상의 모든 node w는 Figure 1이 아닌 다음과 같은 부등식을 만족한다고 해봅니다. 그리고 임의의 node u에서 root node까지의 경로를 다음과 같이 표기하기로 합니다. r은 root node임과 동시에 u_{0}이고 u_{h}는 node u 그 자체입니다. L..
-
[ Open Data Structures ] - ScapeGoat - 1DataStructure 2021. 1. 15. 21:41
Treap은 Node에 Priority를 통해 Heap성질을 활용하여 Tree의 Balancing을 노렸습니다. 이번엔 ScapeGoat라는 방법을 통해 Tree의 Balancing을 유도해보도록 합시다. ScapeGoat는 Partial-Rebuilding Operation을 통해 Balancing을 꾀합니다. 이 Operation이 수행되는 동안, SubTree는 완전히 분해됐다가 가장 Balanced 형태로 재결합하게 됩니다. The capegoat라는 말은 뭔가 일이 잘못되었을 때, 인간이 가장 먼저 하는 행동 중 하나가 책임을 물릴 대상을 물색하고 책임자가 선정되면 그 사람이 남은 일을 알아서 처리하도록 한다는 점에서 착안한 단어입니다. 어떤 점이 이런 성질과 닮았는지 확인하도록 해봅시다. 어떤..
-
[ Open Data Structures ] - Treap - 2DataStructure 2021. 1. 14. 11:09
전에 언급했던 것처럼 Random Binary Search Tree는 Unbalanced하며 Add/Remove 등의 Operation의 수행이 힘들다는 치명적인 단점(Tree가 한쪽으로 치우친다는 단점)이 있어서 Dynamic한 활용이 어렵다고 했습니다. 게다가 Sorted Set을 위한 Interface의 지원이 불가능합니다. 이를 해결하기 위한 다양한 방법 중에는 가장 쉽고 적용이 빠른 Treap이 있습니다. 기존의 Random Binary Search Tree(이하 RBST)의 각 Node는 Left/Right Subtree를 위한 Data값(혹은 Search Key)를 가지고 있었습니다. Treap을 위한 Treap node는 여기에 추가적으로 Prioriy를 나타내는 임의의 integer/fl..
-
[ Open Data Structures ] - Treap - 1DataStructure 2021. 1. 7. 16:50
집합 S = { A, B, C, D, E, F, G, H, I, j, K}를 오름차순으로 Binary Search Tree에 삽입한다면 아마도 오른쪽으로 치우친 불균형한 Tree를 형성할 것입니다. 만약, 집합 S가 알파벳이 아닌 오름차순으로 정렬된 거대한 실수집합이라면 어떤 값을 탐색하는 경우 최악의 경우가 발생할 수 있고 Performance에 악영향을 줄 가능성이 있습니다. 이를 보완하기 위해 도입된 다양한 방법 중 하나가 Random Binary Search Tree입니다. 예를들어, 집합 S = { (0, 13) }가 있을 때, S가 오름차순으로 정렬되어있다면 이를 순차적으로 Binary Search Tree에 Insertion Operation을 하여 Tree를 구성한다면 오른쪽으로 크게 치우..
-
[ Open Data Structure ] - An Unbalanced Binary Search Tree (불균형 이진탐색트리) - 3DataStructure 2020. 12. 29. 15:54
본격적으로 Binary Search Tree 중 Unbalanced Binary Search Tree를 살펴봅니다. Binary Search Tree의 Property는 Tree 내부의 어떤 데이터 x를 빠르게 특정해준다는 점에서 상당히 유용합니다. 그렇다면 바로 Tree 내부의 어떤 데이터 x를 찾는 코드를 살펴보도록 합니다. 그 전에 몇 가지 간단한 규칙부터 공부하는 편이 좋습니다. 여기서 x는 임의의 데이터를 가리키고 u는 임의의 node이며 u.x란 node u가 가진 데이터를 이릅니다. 1. 만약, x left로 진행합니다. 2. 만약, x> u.x라면 탐색 과정은 u->right로 진행합니다. 3. 만약, x == u.x라면 데이터 x를 가진 node u를 찾아..
-
[ Open Data Structure ] An Unbalanced Binary Search Tree - ( 불균형 이진탐색트리) - 2DataStructure 2020. 12. 26. 22:26
전에 첨부한 Figure 2.3의 Application Class의 Private엔 두 가지의 Member variable이 있었는데 하나는 Application을 다루기 위한 Integer type의 mCommand였으며 다른 하나는 An Unbalanced Binary Search Tree의 모든 Implementatios와 Root Node를 포함한 정보를 가진 데이터였습니다(Figure 3.1). BinaryTree는 BinaryTree의 Implemetations를 포함한 Class입니다. 이 Class 안에는 마침내 Binary Search Tree의 Root node의 정보가 다음과 같이 들어 있습니다. Figure 3.2에서처럼 Root node를 포인터로 선언했기 때문에 Class의 Co..
-
[Open Data Structure] - An Unbalanced Binary Search Tree (불균형 이진 탐색 트리) - 1DataStructure 2020. 12. 26. 21:17
그래프의 일종이며 기본적인 형태는 다음과 같습니다. 이는 Computer Science(CS)의 가장 기초를 이루는 구조 중 하나입니다. Tree라는 이름이 붙은 이유는 자료의 구조를 설명하기 위해 그림을 그리면 종종 나무와 나뭇가지를 닮은 구조를 얻을 수 있기 때문입니다. 수학적으로 이 구조를 정의하면 다음과 같습니다. A binary tree is a connected, undirected, finite graph with no cycles, and no vertex of degree greater than three. 각 Vertex(정점 또는 꼭지점)는 세 개 미만의 연결을 가지고 연결되어 있습니다. 또, Graph theory에서 Cycle이란 Simple Circuit이라고도 하는데 어떤 경로..