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

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

• ants - Ants (Varena).