Clasele 11-12 lecția 6 - 6 nov 2015

From Algopedia
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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ă: