• API
• FAQ
• Tools
• Archive
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()) {
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.

Top