[176] | 1 | /* -*- C++ -*- */ |
---|
| 2 | |
---|
| 3 | #ifndef _TREAP_H_ |
---|
| 4 | #define _TREAP_H_ |
---|
| 5 | |
---|
| 6 | #include <assert.h> |
---|
| 7 | #include <stdlib.h> |
---|
| 8 | #include <limits.h> |
---|
| 9 | |
---|
| 10 | |
---|
| 11 | // A Cartesian tree. |
---|
| 12 | // adapted from treap code by Bobby Blumofe |
---|
| 13 | |
---|
| 14 | |
---|
| 15 | template <class KEY, class VALUE> |
---|
| 16 | class Treap { |
---|
| 17 | |
---|
| 18 | public: |
---|
| 19 | |
---|
| 20 | class Node { // A node in the treap. |
---|
| 21 | friend class Treap; |
---|
| 22 | unsigned int priority; // The priority. |
---|
| 23 | KEY key; // The key. |
---|
| 24 | VALUE value; // The value. |
---|
| 25 | Node* parent; // Pointer to parent. |
---|
| 26 | Node* left; // Pointer to left child. |
---|
| 27 | Node* right; // Pointer to right child. |
---|
| 28 | |
---|
| 29 | public: |
---|
| 30 | // Construct node. |
---|
| 31 | Node (void) : left (NULL), right (NULL) {} |
---|
| 32 | |
---|
| 33 | Node (unsigned int priority_, KEY key_, VALUE value_, Node* parent_) |
---|
| 34 | : priority (priority_), key (key_), value (value_), |
---|
| 35 | parent (parent_), left (NULL), right (NULL) {} |
---|
| 36 | KEY getKey (void) const { return key; } |
---|
| 37 | VALUE getValue (void) const { return value; } |
---|
| 38 | }; |
---|
| 39 | |
---|
| 40 | // Construct an empty treap. |
---|
| 41 | Treap (void); |
---|
| 42 | |
---|
| 43 | // Destructor. |
---|
| 44 | ~Treap (void); |
---|
| 45 | |
---|
| 46 | // Return value of key or 0 if not found. |
---|
| 47 | // Return a matching node (or NULL if not found). |
---|
| 48 | Node * lookup (KEY key) const { |
---|
| 49 | return lookup_ (key); |
---|
| 50 | } |
---|
| 51 | |
---|
| 52 | // Return a matching node (or NULL if not found). |
---|
| 53 | Node * lookupGreater (KEY key) const { |
---|
| 54 | return lookupGreater_ (key); |
---|
| 55 | } |
---|
| 56 | |
---|
| 57 | // Set the given key to have the given value. |
---|
| 58 | void insert (Node * n, KEY key, VALUE value, unsigned int priority); |
---|
| 59 | |
---|
| 60 | // Remove entry with given key. |
---|
| 61 | // Remove entry. |
---|
| 62 | Node * remove (Node * node) { |
---|
| 63 | #if 0 |
---|
| 64 | // Search for node with given key. |
---|
| 65 | Node* node = lookup_ (key); |
---|
| 66 | #endif |
---|
| 67 | |
---|
| 68 | // If not found, then do nothing. |
---|
| 69 | if (!node) |
---|
| 70 | return NULL; |
---|
| 71 | |
---|
| 72 | // While node is not a leaf... |
---|
| 73 | while (node->left || node->right) { |
---|
| 74 | |
---|
| 75 | // If left child only, rotate right. |
---|
| 76 | if (!node->right) |
---|
| 77 | rotateRight (node); |
---|
| 78 | |
---|
| 79 | // If right child only, rotate left. |
---|
| 80 | else if (!node->left) |
---|
| 81 | rotateLeft (node); |
---|
| 82 | |
---|
| 83 | // If both children, |
---|
| 84 | else { |
---|
| 85 | if (node->left->priority < node->right->priority) |
---|
| 86 | rotateRight (node); |
---|
| 87 | else |
---|
| 88 | rotateLeft (node); |
---|
| 89 | } |
---|
| 90 | } |
---|
| 91 | |
---|
| 92 | // Clip off node. |
---|
| 93 | Node* parent = node->parent; |
---|
| 94 | if (!parent) { |
---|
| 95 | assert (root == node); |
---|
| 96 | root = 0; |
---|
| 97 | } |
---|
| 98 | else { |
---|
| 99 | if (parent->left == node) |
---|
| 100 | parent->left = 0; |
---|
| 101 | else |
---|
| 102 | parent->right = 0; |
---|
| 103 | } |
---|
| 104 | |
---|
| 105 | // Check treap properties. |
---|
| 106 | // assert (heapProperty (root, INT_MIN)); |
---|
| 107 | // assert (bstProperty (root, INT_MIN, INT_MAX)); |
---|
| 108 | |
---|
| 109 | #if 0 |
---|
| 110 | delete node; |
---|
| 111 | return NULL; |
---|
| 112 | #else |
---|
| 113 | // Return the removed node. |
---|
| 114 | |
---|
| 115 | return node; |
---|
| 116 | #endif |
---|
| 117 | } |
---|
| 118 | |
---|
| 119 | |
---|
| 120 | void print (void) const { reallyPrint (root); cout << endl; } |
---|
| 121 | |
---|
| 122 | void reallyPrint (Node * node) const { |
---|
| 123 | if (node == NULL) return; |
---|
| 124 | reallyPrint (node->left); |
---|
| 125 | cout << "[" << node->key << "] "; |
---|
| 126 | reallyPrint (node->right); |
---|
| 127 | } |
---|
| 128 | |
---|
| 129 | |
---|
| 130 | |
---|
| 131 | private: |
---|
| 132 | |
---|
| 133 | Node* root; // Pointer to root node of treap. |
---|
| 134 | |
---|
| 135 | // Disable copy and assignment. |
---|
| 136 | Treap (const Treap& treap) {} |
---|
| 137 | Treap& operator= (const Treap& treap) { return *this; } |
---|
| 138 | |
---|
| 139 | // Check treap properties. |
---|
| 140 | int heapProperty (Node* node, int lbound) const; |
---|
| 141 | int bstProperty (Node* node, int lbound, int ubound) const; |
---|
| 142 | |
---|
| 143 | // Delete treap rooted at given node. |
---|
| 144 | void deleteTreap (Node* node); |
---|
| 145 | |
---|
| 146 | // Return node with given key or NULL if not found. |
---|
| 147 | Node* lookup_ (KEY key) const; |
---|
| 148 | Node* lookupGreater_ (KEY key) const; |
---|
| 149 | Node* lookupGeq (KEY key, Node * root) const; |
---|
| 150 | |
---|
| 151 | // Perform rotations. |
---|
| 152 | void rotateLeft (Node* node); |
---|
| 153 | void rotateRight (Node* node); |
---|
| 154 | }; |
---|
| 155 | |
---|
| 156 | |
---|
| 157 | // Construct an empty treap. |
---|
| 158 | template <class KEY, class VALUE> |
---|
| 159 | Treap<KEY,VALUE>::Treap (void) |
---|
| 160 | : root (0) |
---|
| 161 | { |
---|
| 162 | } |
---|
| 163 | |
---|
| 164 | // Destructor. |
---|
| 165 | template <class KEY, class VALUE> |
---|
| 166 | Treap<KEY,VALUE>::~Treap (void) |
---|
| 167 | { |
---|
| 168 | deleteTreap (root); |
---|
| 169 | } |
---|
| 170 | |
---|
| 171 | // Delete treap rooted at given node. |
---|
| 172 | template <class KEY, class VALUE> |
---|
| 173 | void Treap<KEY,VALUE>::deleteTreap (Node* node) |
---|
| 174 | { |
---|
| 175 | // If empty, nothing to do. |
---|
| 176 | if (!node) |
---|
| 177 | return; |
---|
| 178 | |
---|
| 179 | // Delete left and right subtreaps. |
---|
| 180 | deleteTreap (node->left); |
---|
| 181 | deleteTreap (node->right); |
---|
| 182 | |
---|
| 183 | // Delete root node. |
---|
| 184 | delete node; |
---|
| 185 | } |
---|
| 186 | |
---|
| 187 | // Test heap property in subtreap rooted at node. |
---|
| 188 | template <class KEY, class VALUE> |
---|
| 189 | int Treap<KEY,VALUE>::heapProperty (Node* node, int lbound) const |
---|
| 190 | { |
---|
| 191 | // Empty treap satisfies. |
---|
| 192 | if (!node) |
---|
| 193 | return 1; |
---|
| 194 | |
---|
| 195 | // Check priority. |
---|
| 196 | if (node->priority < lbound) |
---|
| 197 | return 0; |
---|
| 198 | |
---|
| 199 | // Check left subtreap. |
---|
| 200 | if (!heapProperty (node->left, node->priority)) |
---|
| 201 | return 0; |
---|
| 202 | |
---|
| 203 | // Check right subtreap. |
---|
| 204 | if (!heapProperty (node->right, node->priority)) |
---|
| 205 | return 0; |
---|
| 206 | |
---|
| 207 | // All tests passed. |
---|
| 208 | return 1; |
---|
| 209 | } |
---|
| 210 | |
---|
| 211 | // Test bst property in subtreap rooted at node. |
---|
| 212 | template <class KEY, class VALUE> |
---|
| 213 | int Treap<KEY,VALUE>::bstProperty (Node* node, int lbound, int ubound) const |
---|
| 214 | { |
---|
| 215 | // Empty treap satisfies. |
---|
| 216 | if (!node) |
---|
| 217 | return 1; |
---|
| 218 | |
---|
| 219 | // Check key in range. |
---|
| 220 | if (node->key < lbound || node->key > ubound) |
---|
| 221 | return 0; |
---|
| 222 | |
---|
| 223 | // Check left subtreap. |
---|
| 224 | if (!bstProperty (node->left, lbound, node->key)) |
---|
| 225 | return 0; |
---|
| 226 | |
---|
| 227 | // Check right subtreap. |
---|
| 228 | if (!bstProperty (node->right, node->key, ubound)) |
---|
| 229 | return 0; |
---|
| 230 | |
---|
| 231 | // All tests passed. |
---|
| 232 | return 1; |
---|
| 233 | } |
---|
| 234 | |
---|
| 235 | // Perform a left rotation. |
---|
| 236 | template <class KEY, class VALUE> |
---|
| 237 | void Treap<KEY,VALUE>::rotateLeft (Node* node) |
---|
| 238 | { |
---|
| 239 | // Get right child. |
---|
| 240 | Node* right = node->right; |
---|
| 241 | assert (right); |
---|
| 242 | |
---|
| 243 | // Give node right's left child. |
---|
| 244 | node->right = right->left; |
---|
| 245 | |
---|
| 246 | // Adjust parent pointers. |
---|
| 247 | if (right->left) |
---|
| 248 | right->left->parent = node; |
---|
| 249 | right->parent = node->parent; |
---|
| 250 | |
---|
| 251 | // If node is root, change root. |
---|
| 252 | if (!node->parent) { |
---|
| 253 | assert (root == node); |
---|
| 254 | root = right; |
---|
| 255 | } |
---|
| 256 | |
---|
| 257 | // Link node parent to right. |
---|
| 258 | else { |
---|
| 259 | if (node->parent->left == node) |
---|
| 260 | node->parent->left = right; |
---|
| 261 | else |
---|
| 262 | node->parent->right = right; |
---|
| 263 | } |
---|
| 264 | |
---|
| 265 | // Put node to left of right. |
---|
| 266 | right->left = node; |
---|
| 267 | node->parent = right; |
---|
| 268 | } |
---|
| 269 | |
---|
| 270 | // Perform a right rotation. |
---|
| 271 | template <class KEY, class VALUE> |
---|
| 272 | void Treap<KEY,VALUE>::rotateRight (Node* node) |
---|
| 273 | { |
---|
| 274 | // Get left child. |
---|
| 275 | Node* left = node->left; |
---|
| 276 | assert (left); |
---|
| 277 | |
---|
| 278 | // Give node left's right child. |
---|
| 279 | node->left = left->right; |
---|
| 280 | |
---|
| 281 | // Adjust parent pointers. |
---|
| 282 | if (left->right) |
---|
| 283 | left->right->parent = node; |
---|
| 284 | left->parent = node->parent; |
---|
| 285 | |
---|
| 286 | // If node is root, change root. |
---|
| 287 | if (!node->parent) { |
---|
| 288 | assert (root == node); |
---|
| 289 | root = left; |
---|
| 290 | } |
---|
| 291 | |
---|
| 292 | // Link node parent to left. |
---|
| 293 | else { |
---|
| 294 | if (node->parent->left == node) |
---|
| 295 | node->parent->left = left; |
---|
| 296 | else |
---|
| 297 | node->parent->right = left; |
---|
| 298 | } |
---|
| 299 | |
---|
| 300 | // Put node to right of left. |
---|
| 301 | left->right = node; |
---|
| 302 | node->parent = left; |
---|
| 303 | } |
---|
| 304 | |
---|
| 305 | // Return node with given key or 0 if not found. |
---|
| 306 | template <class KEY, class VALUE> |
---|
| 307 | Treap<KEY,VALUE>::Node* Treap<KEY,VALUE>::lookup_ (KEY key) const |
---|
| 308 | { |
---|
| 309 | // Start at the root. |
---|
| 310 | Node* node = root; |
---|
| 311 | |
---|
| 312 | // While subtreap rooted at node not empty... |
---|
| 313 | while (node) { |
---|
| 314 | |
---|
| 315 | // If found, then return value. |
---|
| 316 | if (key == node->key) |
---|
| 317 | return node; |
---|
| 318 | |
---|
| 319 | // Otherwise, search left or right subtreap. |
---|
| 320 | else if (key < node->key) |
---|
| 321 | node = node->left; |
---|
| 322 | else |
---|
| 323 | node = node->right; |
---|
| 324 | } |
---|
| 325 | |
---|
| 326 | // Return. |
---|
| 327 | return node; |
---|
| 328 | } |
---|
| 329 | |
---|
| 330 | |
---|
| 331 | template <class KEY, class VALUE> |
---|
| 332 | Treap<KEY,VALUE>::Node* Treap<KEY,VALUE>::lookupGreater_ (KEY key) const |
---|
| 333 | { |
---|
| 334 | return lookupGeq (key, root); |
---|
| 335 | } |
---|
| 336 | |
---|
| 337 | |
---|
| 338 | // Return node with greater or equal key or 0 if not found. |
---|
| 339 | template <class KEY, class VALUE> |
---|
| 340 | Treap<KEY,VALUE>::Node* Treap<KEY,VALUE>::lookupGeq (KEY key, Node * rt) const |
---|
| 341 | { |
---|
| 342 | Node * bestSoFar = NULL; |
---|
| 343 | |
---|
| 344 | // Start at the root. |
---|
| 345 | Node* node = rt; |
---|
| 346 | |
---|
| 347 | // While subtreap rooted at node not empty... |
---|
| 348 | while (node) { |
---|
| 349 | |
---|
| 350 | // If exact match found, then return value. |
---|
| 351 | if (key == node->key) |
---|
| 352 | return node; |
---|
| 353 | |
---|
| 354 | // Move right -- this node is too small. |
---|
| 355 | if (node->key < key) |
---|
| 356 | node = node->right; |
---|
| 357 | |
---|
| 358 | // Otherwise, this one's pretty good; |
---|
| 359 | // look for a better match. |
---|
| 360 | else { |
---|
| 361 | if ((bestSoFar == NULL) || (bestSoFar->key > node->key)) |
---|
| 362 | bestSoFar = node; |
---|
| 363 | node = node->left; |
---|
| 364 | } |
---|
| 365 | } |
---|
| 366 | |
---|
| 367 | // Return. |
---|
| 368 | return bestSoFar; |
---|
| 369 | } |
---|
| 370 | |
---|
| 371 | |
---|
| 372 | // Set the given key to have the given value. |
---|
| 373 | template <class KEY, class VALUE> |
---|
| 374 | void Treap<KEY,VALUE>::insert (Treap<KEY,VALUE>::Node * n, KEY key, VALUE value, unsigned int priority) |
---|
| 375 | { |
---|
| 376 | |
---|
| 377 | // print(); |
---|
| 378 | |
---|
| 379 | // 0 is not a valid value. |
---|
| 380 | assert (value != 0); |
---|
| 381 | |
---|
| 382 | // Start at the root. |
---|
| 383 | Node* parent = 0; |
---|
| 384 | Node* node = root; |
---|
| 385 | |
---|
| 386 | |
---|
| 387 | // While subtreap rooted at node not empty... |
---|
| 388 | while (node) { |
---|
| 389 | |
---|
| 390 | #if 0 |
---|
| 391 | // If found, then update value and done. |
---|
| 392 | if (key == node->key) { |
---|
| 393 | node->value = value; |
---|
| 394 | return; |
---|
| 395 | } |
---|
| 396 | #endif |
---|
| 397 | |
---|
| 398 | // Otherwise, search left or right subtreap. |
---|
| 399 | parent = node; |
---|
| 400 | |
---|
| 401 | |
---|
| 402 | if (key < node->key) |
---|
| 403 | node = node->left; |
---|
| 404 | else |
---|
| 405 | node = node->right; |
---|
| 406 | } |
---|
| 407 | |
---|
| 408 | |
---|
| 409 | // Not found, so create new node. |
---|
| 410 | // EDB was |
---|
| 411 | // node = new Node (lrand48(), key, value, parent); |
---|
| 412 | node = new (n) Node (priority, key, value, parent); |
---|
| 413 | // node = new Node (priority, key, value, parent); |
---|
| 414 | |
---|
| 415 | // If the treap was empty, then new node is root. |
---|
| 416 | if (!parent) |
---|
| 417 | root = node; |
---|
| 418 | |
---|
| 419 | // Otherwise, add node as left or right child. |
---|
| 420 | else if (key < parent->key) |
---|
| 421 | parent->left = node; |
---|
| 422 | else |
---|
| 423 | parent->right = node; |
---|
| 424 | |
---|
| 425 | // While heap property not satisfied... |
---|
| 426 | while (parent && parent->priority > node->priority) { |
---|
| 427 | |
---|
| 428 | // Perform rotation. |
---|
| 429 | if (parent->left == node) |
---|
| 430 | rotateRight (parent); |
---|
| 431 | else |
---|
| 432 | rotateLeft (parent); |
---|
| 433 | |
---|
| 434 | // Move up. |
---|
| 435 | parent = node->parent; |
---|
| 436 | } |
---|
| 437 | |
---|
| 438 | // print(); |
---|
| 439 | |
---|
| 440 | // Check treap properties. |
---|
| 441 | // assert (heapProperty (root, INT_MIN)); |
---|
| 442 | // assert (bstProperty (root, INT_MIN, INT_MAX)); |
---|
| 443 | } |
---|
| 444 | |
---|
| 445 | |
---|
| 446 | |
---|
| 447 | #endif // _TREAP_H_ |
---|