Created
April 25, 2022 07:12
-
-
Save alexdremov/a34f6658d1af134e29ca66a7b19d551c to your computer and use it in GitHub Desktop.
Treap code | https://alexdremov.me/treap-algorithm-explained/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Node* find(Node* node, const T& key) { | |
if (node == nullptr) | |
return nullptr; | |
if (node->key == key) | |
return node; | |
return find(key >= node->key ? node->right : node->left, key); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Node* insert(Node* head, T key) { | |
auto split = split(head, key); | |
if (find(split.second, key) != nullptr) { | |
// Key exists already | |
// Merge back | |
return merge(split.first, split.second); | |
} | |
auto newNode = new Node(std::move(key), rand()); | |
return merge(split.first, merge(newNode, splitsplitted.second)); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Node* merge (Node *l, Node *r) { | |
if (!l) // left is empty | |
return r; | |
if (!r) // right is empty | |
return l; | |
if (l->prior > r->prior) { // l has the new head. | |
l->right = merge(l->right, r); | |
return l; | |
} else { // r has the new head. | |
r->left = merge(l, r->left); | |
return r; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
template<typename T> | |
struct Node { | |
T key; | |
size_t prior; | |
long long sum; | |
Node* left = nullptr, *right = nullptr; | |
Node(T key, size_t prior) : | |
key(std::move(key)), | |
prior(prior) { | |
} | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Node *remove(Node *head, const T &key) { | |
auto split = split(head, key); | |
if (split.second) { | |
auto secondSplit = split(split.second, key, | |
/*equalOnTheLeft=*/true); | |
// Key exists, so delete it and merge | |
auto everythingElse = secondSplit.second; | |
if (secondSplit.first == nullptr) { | |
// There's no element equal to key. Merge back. | |
return merge(split.first, everythingElse); | |
} | |
// We got node with key value in | |
// secondSplit.first | |
delete secondSplit.first; | |
size--; | |
return merge(split.first, everythingElse); | |
} | |
// Key is not presented. Merge back. | |
return merge(split.first, split.second); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
pair<Node *, Node *> split (Node *p, const T& key, | |
bool equalOnTheLeft=false) { | |
if (!p) // reached leaf | |
return {nullptr, nullptr}; | |
if (p->key < key || | |
(equalOnTheLeft && p->key == key)) { // splitting right | |
auto q = split(p->right, key, equalOnTheLeft); | |
// q.first has nodes of the right | |
// subtree that are less than key | |
p->right = q.first; | |
return {p, q.second}; | |
} else { // splitting left | |
auto q = split(p->left, key, equalOnTheLeft); | |
// q.second has nodes of the left | |
// subtree that are greater or equal | |
// to the key | |
p->left = q.second; | |
return {q.first, p}; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
template<typename T> | |
struct Node { | |
T key; | |
size_t prior; | |
Node* left = nullptr, *right = nullptr; | |
Node(T key, size_t prior) : | |
key(std::move(key)), | |
prior(prior) { | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment