소오설 소오설

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..

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를 생성..

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..

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의 장점을 충분히 뛰..