Skip to content

Instantly share code, notes, and snippets.

@JaHIY

JaHIY/scape_goat_tree.cpp

Created May 7, 2022 10:04
Show Gist options
  • Save JaHIY/023f6a7030538c1908ac5701eee33c36 to your computer and use it in GitHub Desktop.
Save JaHIY/023f6a7030538c1908ac5701eee33c36 to your computer and use it in GitHub Desktop.
Download ZIP
Yet another C++ implementation of ScapeGoat Tree
Raw
scape_goat_tree.cpp
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <utility>
using std::make_pair;
using std::pair;
#include <functional>
using std::function;
using std::ref;
using std::reference_wrapper;
template<typename KeyType, typename ValueType>
class ScapeGoatTree;
template<typename KeyType, typename ValueType>
class ScapeGoatTreeNode {
friend class ScapeGoatTree<KeyType, ValueType>;
public:
KeyType key;
ValueType value;
int physicalSize;
int logicalSize;
bool isExisted;
ScapeGoatTreeNode<KeyType, ValueType> * left;
ScapeGoatTreeNode<KeyType, ValueType> * right;
ScapeGoatTreeNode(const KeyType & k, const ValueType & v)
: key(k), value(v), physicalSize(1), logicalSize(1), isExisted(true),
left(nullptr), right(nullptr)
{}
};
template<typename KeyType, typename ValueType>
class ScapeGoatTree {
public:
ScapeGoatTreeNode<KeyType, ValueType> * root;
double alpha;
ScapeGoatTree()
: root(nullptr), alpha(0.7)
{}
void insert(const KeyType & key, const ValueType & value) {
auto [isInserted, insertedNodeWrapper] = insertHelper(this->root, key, value);
if (isInserted == true) {
this->root = &insertedNodeWrapper.get();
}
}
pair<bool, reference_wrapper<ScapeGoatTreeNode<KeyType, ValueType>>>
insertHelper(ScapeGoatTreeNode<KeyType, ValueType> *& node, const KeyType & key, const ValueType & value) {
if (node == nullptr) {
ScapeGoatTreeNode<KeyType, ValueType> * newNode = new ScapeGoatTreeNode(key, value);
return make_pair(true, ref(*newNode));
}
if (key == node->key) {
if (value != node->value) {
node->value = value;
}
node->isExisted = true;
return make_pair(false, ref(*node));
}
ScapeGoatTreeNode<KeyType, ValueType> ** nextNode;
if (key < node->key) {
nextNode = &node->left;
} else if (key > node->key) {
nextNode = &node->right;
}
auto [isInserted, insertedNodeWrapper] = insertHelper(*nextNode, key, value);
*nextNode = &insertedNodeWrapper.get();
if (isInserted == true) {
node->physicalSize += 1;
node->logicalSize += 1;
if (needRebuild(*node)) {
node = &rebuild(node);
}
update(*node);
}
return make_pair(isInserted, ref(*node));
}
bool needRebuild(const ScapeGoatTreeNode<KeyType, ValueType> & node) const {
int leftPhysicalSize = (node.left == nullptr) ? 0 : node.left->physicalSize;
int leftLogicalSize = (node.left == nullptr) ? 0 : node.left->logicalSize;
int rightPhysicalSize = (node.right == nullptr) ? 0 : node.right->physicalSize;
int rightLogicalSize = (node.right == nullptr) ? 0 : node.right->logicalSize;
return ((leftPhysicalSize > node.physicalSize * this->alpha) ||
(rightPhysicalSize > node.physicalSize * this->alpha) ||
(leftPhysicalSize + rightPhysicalSize - leftLogicalSize - rightLogicalSize > node.physicalSize * 0.3));
}
ScapeGoatTreeNode<KeyType, ValueType> & flatten(ScapeGoatTreeNode<KeyType, ValueType> *& node) {
ScapeGoatTreeNode<KeyType, ValueType> * rootNode = nullptr;
ScapeGoatTreeNode<KeyType, ValueType> * prevNode = nullptr;
inOrderTraversal(node,
[&rootNode, &prevNode] (ScapeGoatTreeNode<KeyType, ValueType> *& currNode) -> void {
if (currNode->isExisted == false) {
return;
}
currNode->left = nullptr;
if (prevNode == nullptr) {
rootNode = currNode;
} else {
prevNode->right = currNode;
}
prevNode = currNode;
},
[] (ScapeGoatTreeNode<KeyType, ValueType> *& currNode) -> void {
if (currNode->isExisted == false) {
ScapeGoatTreeNode<KeyType, ValueType> * p = currNode;
currNode = nullptr;
delete p;
}
});
return *rootNode;
}
void inOrderTraversal(ScapeGoatTreeNode<KeyType, ValueType> *& node,
function<void (ScapeGoatTreeNode<KeyType, ValueType> *&)> fn,
function<void (ScapeGoatTreeNode<KeyType, ValueType> *&)> afterFn) {
if (node == nullptr) {
return;
}
inOrderTraversal(node->left, fn, afterFn);
fn(node);
inOrderTraversal(node->right, fn, afterFn);
afterFn(node);
}
void update(ScapeGoatTreeNode<KeyType, ValueType> & node) {
int leftPhysicalSize = (node.left == nullptr) ? 0 : node.left->physicalSize;
int leftLogicalSize = (node.left == nullptr) ? 0 : node.left->logicalSize;
int rightPhysicalSize = (node.right == nullptr) ? 0 : node.right->physicalSize;
int rightLogicalSize = (node.right == nullptr) ? 0 : node.right->logicalSize;
node.physicalSize = node.isExisted + leftPhysicalSize + rightPhysicalSize;
node.logicalSize = node.isExisted + leftLogicalSize + rightLogicalSize;
}
ScapeGoatTreeNode<KeyType, ValueType> & build(ScapeGoatTreeNode<KeyType, ValueType> & node) {
if (node.right == nullptr) {
update(node);
return node;
}
ScapeGoatTreeNode<KeyType, ValueType> * prev = &node;
ScapeGoatTreeNode<KeyType, ValueType> * slow = &node;
ScapeGoatTreeNode<KeyType, ValueType> * fast = &node;
while (fast != nullptr && fast->right != nullptr) {
fast = fast->right->right;
prev = slow;
slow = slow->right;
}
prev->right = nullptr;
slow->left = &build(node);
if (slow->right != nullptr) {
slow->right = &build(*slow->right);
}
update(*slow);
return *slow;
}
ScapeGoatTreeNode<KeyType, ValueType> & rebuild(ScapeGoatTreeNode<KeyType, ValueType> *& node) {
ScapeGoatTreeNode<KeyType, ValueType> & n1 = flatten(node);
return build(n1);
}
void remove(const KeyType & key) {
auto [isRemoved, newRootNodeWrapper] = removeHelper(this->root, key);
if (isRemoved == true) {
this->root = &newRootNodeWrapper.get();
}
}
pair<bool, reference_wrapper<ScapeGoatTreeNode<KeyType, ValueType>>> removeHelper(ScapeGoatTreeNode<KeyType, ValueType> *& node, const KeyType & key) {
if (key == node->key) {
if (node->isExisted == true) {
node->isExisted = false;
node->logicalSize -= 1;
ScapeGoatTreeNode<KeyType, ValueType> * nodePtr = node;
if (needRebuild(*node)) {
nodePtr = &rebuild(node);
}
return make_pair(true, ref(*nodePtr));
}
return make_pair(false, ref(*node));
}
ScapeGoatTreeNode<KeyType, ValueType> ** nodePtrPtr = nullptr;
if (key < node->key) {
nodePtrPtr = &node->left;
} else {
nodePtrPtr = &node->right;
}
auto [isRemoved, newNodeWrapper] = removeHelper(*nodePtrPtr, key);
*nodePtrPtr = &newNodeWrapper.get();
if (isRemoved == true) {
node->logicalSize -= 1;
if (needRebuild(*node)) {
node = &rebuild(node);
}
update(*node);
}
return make_pair(isRemoved, ref(*node));
}
int getRank(const KeyType & x) const {
return getRankHelper(this->root, x);
}
int getRankHelper(ScapeGoatTreeNode<KeyType, ValueType> * node, const KeyType & x) const {
int ans = 1;
ScapeGoatTreeNode<KeyType, ValueType> * p = node;
while (p != nullptr) {
if (x <= p->key) {
p = p->left;
} else {
int leftLogicalSize = (p->left == nullptr) ? 0 : p->left->logicalSize;
ans += leftLogicalSize + p->isExisted;
p = p->right;
}
}
return ans;
}
ScapeGoatTreeNode<KeyType, ValueType> * findKth(int k) const {
return findKthHelper(this->root, k);
}
ScapeGoatTreeNode<KeyType, ValueType> * findKthHelper(ScapeGoatTreeNode<KeyType, ValueType> * node, int k) const {
ScapeGoatTreeNode<KeyType, ValueType> * p = node;
while (p != nullptr) {
int leftLogicalSize = (p->left == nullptr) ? 0 : p->left->logicalSize;
if (k == leftLogicalSize + p->isExisted) {
break;
} else if (k < leftLogicalSize + p->isExisted) {
p = p->left;
} else {
k -= leftLogicalSize + p->isExisted;
p = p->right;
}
}
return p;
}
ScapeGoatTreeNode<KeyType, ValueType> * find(const KeyType & x) const {
ScapeGoatTreeNode<KeyType, ValueType> * p = this->root;
while (p != nullptr) {
if (x == p->key) {
break;
} else if (x < p->key) {
p = p->left;
} else {
p = p->right;
}
}
return p;
}
ScapeGoatTreeNode<KeyType, ValueType> * findLess(const KeyType & x) const {
ScapeGoatTreeNode<KeyType, ValueType> * p = this->root;
ScapeGoatTreeNode<KeyType, ValueType> * prev = nullptr;
while (p != nullptr) {
if (x <= p->key) {
p = p->left;
} else {
prev = p;
p = p->right;
}
}
return prev;
}
ScapeGoatTreeNode<KeyType, ValueType> * findLessOrEqual(const KeyType & x) const {
ScapeGoatTreeNode<KeyType, ValueType> * p = this->root;
ScapeGoatTreeNode<KeyType, ValueType> * prev = nullptr;
while (p != nullptr) {
if (x == p->key) {
return p;
} else if (x < p->key) {
p = p->left;
} else {
prev = p;
p = p->right;
}
}
return prev;
}
ScapeGoatTreeNode<KeyType, ValueType> * findGreater(const KeyType & x) const {
ScapeGoatTreeNode<KeyType, ValueType> * p = this->root;
ScapeGoatTreeNode<KeyType, ValueType> * prev = nullptr;
while (p != nullptr) {
if (x < p->key) {
prev = p;
p = p->left;
} else {
p = p->right;
}
}
return prev;
}
ScapeGoatTreeNode<KeyType, ValueType> * findGreaterOrEqual(const KeyType & x) const {
ScapeGoatTreeNode<KeyType, ValueType> * p = this->root;
ScapeGoatTreeNode<KeyType, ValueType> * prev = nullptr;
while (p != nullptr) {
if (x == p->key) {
return p;
} else if (x < p->key) {
prev = p;
p = p->left;
} else {
p = p->right;
}
}
return prev;
}
ScapeGoatTreeNode<KeyType, ValueType> * findMin() const {
return findMinHelper(this->root);
}
ScapeGoatTreeNode<KeyType, ValueType> * findMinHelper(ScapeGoatTreeNode<KeyType, ValueType> * node) const {
ScapeGoatTreeNode<KeyType, ValueType> * p = node;
while (p != nullptr && p->left != nullptr) {
p = p->left;
}
return p;
}
ScapeGoatTreeNode<KeyType, ValueType> * findMax() const {
return findMaxHelper(this->root);
}
ScapeGoatTreeNode<KeyType, ValueType> * findMaxHelper(ScapeGoatTreeNode<KeyType, ValueType> * node) const {
ScapeGoatTreeNode<KeyType, ValueType> * p = node;
while (p != nullptr && p->right != nullptr) {
p = p->right;
}
return p;
}
ScapeGoatTreeNode<KeyType, ValueType> * getPredecessor(const KeyType & x) const {
return findLess(x);
}
ScapeGoatTreeNode<KeyType, ValueType> * getSuccessor(const KeyType & x) const {
return findGreater(x);
}
};
int main(void) {
/*
ScapeGoatTree<int, int> t;
t.insert(5,5);
t.insert(2,2);
t.insert(7,7);
t.insert(1,1);
t.insert(3,3);
t.insert(6,6);
t.insert(9,9);
t.insert(4,4);
t.insert(8,8);
t.insert(10,10);
t.remove(4);
t.inOrderTraversal(t.root, [] (ScapeGoatTreeNode<int, int> *& node) -> void { cout << node->key << endl; }, [] (ScapeGoatTreeNode<int, int> *& _) -> void {});
cout << "main: " << t.findGreater(9)->key << endl;
*/
int opt, num;
ScapeGoatTree<int, int> t;
cin >> num;
while (true) {
cin >> opt;
cin >> num;
switch (opt) {
case 1:
t.insert(num, num);
break;
case 2:
t.remove(num);
break;
case 3:
cout << t.getRank(num) << endl;
break;
case 4:
cout << t.findKth(num)->key << endl;
break;
case 5:
cout << t.getPredecessor(num)->key << endl;
break;
case 6:
cout << t.getSuccessor(num)->key << endl;
break;
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment