SHARE
TWEET

Treap

a guest May 23rd, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* Laborator 10 SD - Treapuri
  2.   * Autor: Andrei Parvu - andrei.parvu@cti.pub.ro
  3.   * Echipa SD, 2014
  4.   *
  5.   * Modificari: Mihai Neacsu - mihai.mneacsu@gmail.com
  6.   * Echipa SD, 2015
  7.   *
  8.   * Modificari: Gabriel Bercaru, 2018
  9.  */
  10.  
  11. using namespace std;
  12.  
  13. template <typename T> struct Treap {
  14.     T key;
  15.     int priority;
  16.     Treap<T> *left, *right;
  17.     bool nil;
  18.  
  19.     // Pentru a rezolva problema 3 trebuie ca fiecare nod sa retina numarul de
  20.     // noduri din subarborle sau
  21.     int nr_nodes;
  22.  
  23.     // Creaza un nod nil
  24.     Treap() : priority(-1), left(NULL), right(NULL), nil(true), nr_nodes(0) {}
  25.  
  26.     // Adaugam date, transformand un nod nil intr-un nod obisnuit
  27.     void addData(T key, int priority) {
  28.         this->nil = false;
  29.         this->key = key;
  30.         this->priority = priority;
  31.         this->nr_nodes = 1;
  32.         this->left = new Treap();
  33.         this->right = new Treap();
  34.     }
  35.  
  36.     // Stergem un nod obisnuit, transformandu-l intr-unul nil
  37.     void delData() {
  38.         this->key = 0;
  39.         this->nil = true;
  40.         this->priority = -1;
  41.         delete this->left;
  42.         delete this->right;
  43.         this->nr_nodes = 0;
  44.         delete this;
  45.     }
  46.  
  47.     bool isNil() {
  48.         return this->nil;
  49.     }
  50.  
  51.     bool find(T key) {
  52.         if (this->isNil()) {
  53.             return false;
  54.         }
  55.         // TODO 1.1: Completati functia de cautare
  56.         Treap<T> *current = this;
  57.         while (current != NULL && current->key != key) {
  58.             if (current->key > key) {
  59.                 current = current->left;
  60.             } else {
  61.                 current = current->right;
  62.             }
  63.         }
  64.         if (current != NULL) {
  65.             return true;
  66.         }
  67.         return false;
  68.     }
  69.  
  70.     /* Atat insert cat si erase au nevoie de o referinta catre un fatherPointer,
  71.        adica de pointerul left sau right din parinte care pointeaza catre obiectul
  72.        curent. De ce?
  73.        Sa presupunem ca avem urmatoarea configuratie:
  74.                      a
  75.                     / \
  76.                    b   c
  77.                       / \
  78.                      d   e
  79.  
  80.        si facem o rotatie dreapta in nodul c. Configuratia care rezulta este:
  81.                      a
  82.                     / \
  83.                    b   d
  84.                         \
  85.                          c
  86.                           \
  87.                            e
  88.  
  89.        Dupa cum se poat vedea pointerul right a lui a trebuie sa pointeze in urma
  90.        rotirii catre d. De aceea, o referinta a acelui pointer trebuie pasata catre
  91.        fiul care reprezinta acel pointer, pentru ca nodul a sa vada eventualele
  92.        inlocuiri ce pot aparea in urma unor rotiri.
  93.        Atentie! - desi s-ar putea sa spunem ca putem folosi pointerul this pentru
  94.        a rezolva problema de mai sus, acest lucru este gresit, deoarece this este un
  95.        pointer constant, asupra caruia nu se pot face asignari de forma this = ...
  96.      */
  97.  
  98.     void rotateRight(Treap<T> *&fatherPointer) {
  99.         // TODO 1.2: Completati rotirea dreapta
  100.  
  101.         // TODO 1.2: Recalculati dimensiunea subarborilor
  102.         Treap<T> *son = fatherPointer->left;
  103.         Treap<T> *rson = son->right;
  104.         if (rson != NULL) {
  105.             fatherPointer->left = rson;
  106.         }
  107.         son->right = fatherPointer;
  108.         fatherPointer = son;
  109.     }
  110.  
  111.     void rotateLeft(Treap<T> *&fatherPointer) {
  112.         // TODO 1.2: Completati rotirea stanga
  113.  
  114.         // TODO 1.2: Recalculati dimensiunea subarborilor
  115.         Treap<T> *son = fatherPointer->right;
  116.         Treap<T> *lson = son->left;
  117.         if (lson != NULL) {
  118.             fatherPointer->right = lson;
  119.         }
  120.         son->left = fatherPointer;
  121.         fatherPointer = son;
  122.     }
  123.  
  124.     void insert(Treap<T> *&fatherPointer, T key, int priority) {
  125.         if (fatherPointer->isNil()) {
  126.             fatherPointer->addData(key, priority);
  127.  
  128.             return ;
  129.         }
  130.  
  131.         Treap<T> *nonConstThis = this;
  132.         // TODO 1.3: Inserati recursiv in arbore
  133.         if (key < fatherPointer->key) {
  134.             insert(fatherPointer->left, key, priority);
  135.         } else {
  136.             insert(fatherPointer->right, key, priority);
  137.         }
  138.         nr_nodes++;
  139.  
  140.         // TODO 1.3: Faceti rotatiile corespunzatoare
  141.         if (fatherPointer->left->priority > fatherPointer->priority) {
  142.             rotateRight(fatherPointer);
  143.         } else if (fatherPointer->right->priority > fatherPointer->priority) {
  144.             rotateLeft(fatherPointer);
  145.         }
  146.     }
  147.  
  148.     void erase(Treap<T> *&fatherPointer, T key) {
  149.         if (fatherPointer->isNil()) {
  150.             return ;
  151.         }
  152.  
  153.         Treap<T> *nonConstThis = this;
  154.         nr_nodes--;
  155.  
  156.         // TODO 2: Stergti recursiv in arbore (pe subarborele corespunzator)
  157.         if (key < fatherPointer->key) {
  158.             erase(fatherPointer->left, key);
  159.         } else if (key > fatherPointer->key) {
  160.             erase(fatherPointer->right, key);
  161.         } else if (fatherPointer->left->isNil() && fatherPointer->right->isNil()) {
  162.             fatherPointer->delData();
  163.         } else {
  164.             // TODO 2: Rotiti si stergeti recursiv pentru a aduce nodul la baza arborelui
  165.             if (fatherPointer->left->priority > fatherPointer->right->priority) {
  166.                 rotateRight(fatherPointer);
  167.                 erase(fatherPointer->right, key);
  168.             } else {
  169.                 rotateLeft(fatherPointer);
  170.                 erase(fatherPointer->left, key);
  171.             }
  172.         }
  173.     }
  174.     void recInOrder(Treap<T> *current) {
  175.         if (!current->left->isNil()) {
  176.             recInOrder(current->left);
  177.         }
  178.         std::cout << current->key << ' ';
  179.         if (!current->right->isNil()) {
  180.             recInOrder(current->right);
  181.         }
  182.     }
  183.     void inOrder() {
  184.         if (this->isNil()) {
  185.             return;
  186.         }
  187.         // TODO 3: Afisati parcurgerea inordine a cheilor
  188.         recInOrder(this);
  189.         std::cout << '\n';
  190.     }
  191.     void recPreOrder(Treap<T> *current) {
  192.         std::cout << current->key << ' ';
  193.         if (!current->left->isNil()) {
  194.             recPreOrder(current->left);
  195.         }
  196.         if (!current->right->isNil()) {
  197.             recPreOrder(current->right);
  198.         }
  199.     }
  200.     void preOrder(int level = 0) {
  201.         if (this->isNil()) {
  202.             return ;
  203.         }
  204.  
  205.         for (int i = 0; i < level; i++) {
  206.             cout << ' ';
  207.         }
  208.  
  209.         // TODO 3: Afisati parcurgerea preordine a prioritatilor
  210.         recPreOrder(this);
  211.     }
  212.     T getKey(Treap<T> *current, int &k, bool &flag) {
  213.         if (!current->left->isNil() && flag == false) {
  214.             getKey(current->left, k, flag);
  215.         }
  216.         --k;
  217.         if (k == 0 && flag == false) {
  218.             flag = true;
  219.             return current->key;
  220.         }
  221.         if (!current->right->isNil() && flag == false) {
  222.             return getKey(current->right, k, flag);
  223.         }
  224.     }
  225.     T findK(int k) {
  226.         // TODO 3: Pe baza nr_nodes determinati cea de-a k cheie in ordinea sortarii
  227.         bool flag = false;
  228.         T key = getKey(this, k, flag);
  229.         return key;
  230.     }
  231. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top