Clasele 11-12 lecția 6 - 6 nov 2015
From Algopedia
Jump to navigationJump to search
Treap
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using std::pair;
class Treap {
public:
int value;
int priority; // Max-Heap
Treap* left;
Treap* right;
};
Treap* find(Treap* node, int value) {
if (node == NULL || node->value == value) {
return node;
} else if (node->value < value) {
return find(node->right, value);
} else { // if (value < node->value)
return find(node->left, value);
}
}
pair<Treap*, Treap*> split(Treap* node, int value) {
pair<Treap*, Treap*> answer;
if (node == NULL) {
answer.first = NULL;
answer.second = NULL;
} else if (node->value <= value) {
answer.first = new Treap;
answer.first->value = node->value;
answer.first->priority = node->priority;
answer.first->left = node->left;
pair<Treap*, Treap*> splitAnswer = split(node->right, value);
answer.first->right = splitAnswer.first;
answer.second = splitAnswer.second;
delete node;
} else { // value < node->value
answer.second = new Treap;
answer.second->value = node->value;
answer.second->priority = node->priority;
answer.second->right = node->right;
pair<Treap*, Treap*> splitAnswer = split(node->left, value);
answer.first = splitAnswer.first;
answer.second->left = splitAnswer.second;
delete node;
}
return answer;
}
Treap* join(Treap* first, Treap* second) {
if (first == NULL) {
return second;
} else if (second == NULL) {
return first;
} else if (second->priority < first->priority) {
first->right = join(first->right, second);
return first;
} else { // if (first->priority < second->priority)
second->left = join(first, second->left);
return second;
}
}
int myRandom() {
return (rand() << 15) ^ rand();
}
Treap* insert(Treap* node, int value, int priority = myRandom()) {
if (node == NULL || node->priority < priority) {
pair<Treap*, Treap*> splitAnswer = split(node, value);
Treap* answer = new Treap;
answer->value = value;
answer->priority = priority;
answer->left = splitAnswer.first;
answer->right = splitAnswer.second;
return answer;
} else if (node->value < value) {
node->right = insert(node->right, value, priority);
return node;
} else { // if (value <= node->value)
node->left = insert(node->left, value, priority);
return node;
}
}
Treap* erase(Treap* node, int value) {
if (node == NULL) {
return NULL;
} else if (node->value == value) {
Treap* answer = join(node->left, node->right);
delete node;
return answer;
} else if (node->value < value) {
node->right = erase(node->right, value);
return node;
} else { // if (value < node->value)
node->left = erase(node->left, value);
return node;
}
}
void dump(Treap* node, int depth = 0) {
if (node != NULL) {
dump(node->left, depth + 1);
printf("%12d ", node->priority);
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%d\n", node->value);
dump(node->right, depth + 1);
}
}
int main(void) {
srand(time(NULL));
Treap* arb = NULL;
arb = insert(arb, 5);
arb = insert(arb, 3);
arb = insert(arb, 6);
arb = insert(arb, 4);
arb = insert(arb, 9);
arb = insert(arb, 1);
arb = insert(arb, 7);
dump(arb);
printf("\n");
arb = erase(arb, 7);
dump(arb);
return 0;
}
Treap persistent
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using std::pair;
class Treap {
public:
int value;
int priority; // Max-Heap
Treap* left;
Treap* right;
};
Treap* duplicate(const Treap* node) {
Treap* answer = new Treap;
answer->value = node->value;
answer->priority = node->priority;
answer->left = node->left;
answer->right = node->right;
return answer;
}
Treap* find(Treap* node, int value) {
if (node == NULL || node->value == value) {
return node;
} else if (node->value < value) {
return find(node->right, value);
} else { // if (value < node->value)
return find(node->left, value);
}
}
pair<Treap*, Treap*> split(const Treap* node, int value) {
pair<Treap*, Treap*> answer;
if (node == NULL) {
answer.first = NULL;
answer.second = NULL;
} else if (node->value <= value) {
answer.first = new Treap;
answer.first->value = node->value;
answer.first->priority = node->priority;
answer.first->left = node->left;
pair<Treap*, Treap*> splitAnswer = split(node->right, value);
answer.first->right = splitAnswer.first;
answer.second = splitAnswer.second;
} else { // value < node->value
answer.second = new Treap;
answer.second->value = node->value;
answer.second->priority = node->priority;
answer.second->right = node->right;
pair<Treap*, Treap*> splitAnswer = split(node->left, value);
answer.first = splitAnswer.first;
answer.second->left = splitAnswer.second;
}
return answer;
}
Treap* join(Treap* first, Treap* second) {
if (first == NULL) {
return second;
} else if (second == NULL) {
return first;
} else if (second->priority < first->priority) {
Treap* newNode = duplicate(first);
newNode->right = join(first->right, second);
return newNode;
} else { // if (first->priority < second->priority)
Treap* newNode = duplicate(second);
newNode->left = join(first, second->left);
return newNode;
}
}
int myRandom() {
return (rand() << 15) ^ rand();
}
Treap* insert(Treap* node, int value, int priority = myRandom()) {
if (node == NULL || node->priority < priority) {
pair<Treap*, Treap*> splitAnswer = split(node, value);
Treap* answer = new Treap;
answer->value = value;
answer->priority = priority;
answer->left = splitAnswer.first;
answer->right = splitAnswer.second;
return answer;
} else if (node->value < value) {
Treap* newNode = duplicate(node);
newNode->right = insert(node->right, value, priority);
return newNode;
} else { // if (value <= node->value)
Treap* newNode = duplicate(node);
newNode->left = insert(node->left, value, priority);
return newNode;
}
}
Treap* erase(Treap* node, int value) {
if (node == NULL) {
return NULL;
} else if (node->value == value) {
Treap* answer = join(node->left, node->right);
return answer;
} else if (node->value < value) {
Treap* newNode = duplicate(node);
newNode->right = erase(node->right, value);
return newNode;
} else { // if (value < node->value)
Treap* newNode = duplicate(node);
newNode->left = erase(node->left, value);
return newNode;
}
}
void dump(Treap* node, int depth = 0) {
if (node != NULL) {
dump(node->left, depth + 1);
printf("%12d ", node->priority);
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%d\n", node->value);
dump(node->right, depth + 1);
}
}
int main(void) {
srand(time(NULL));
Treap* arb1 = NULL;
Treap* arb2 = insert(arb1, 5);
Treap* arb3 = insert(arb2, 3);
Treap* arb4 = insert(arb3, 6);
Treap* arb5 = insert(arb4, 4);
Treap* arb6 = insert(arb5, 9);
Treap* arb7 = insert(arb6, 1);
Treap* arb8 = insert(arb7, 7);
Treap* arb9 = erase(arb6, 4);
dump(arb1);
printf("\n");
dump(arb2);
printf("\n");
dump(arb3);
printf("\n");
dump(arb4);
printf("\n");
dump(arb5);
printf("\n");
dump(arb6);
printf("\n");
dump(arb7);
printf("\n");
dump(arb8);
printf("\n");
dump(arb9);
printf("\n");
return 0;
}
Temă
Pentru data viitoare veți avea de rezolvat următoarea problemă: