40 template<
typename Key,
42 typename Compare = less<Key> >
75 void delete_children_recursive()
79 left->delete_children_recursive();
85 right->delete_children_recursive();
127 root->delete_children_recursive();
136 return ( root ==
NULL );
142 return ( root ==
NULL ? 0 : root->sleft + root->sright + 1 );
150 assert( it !=
NULL );
159 assert( it !=
NULL );
178 nn =
new node(key,data);
180 throw std::bad_alloc();
184 nn = create_new_node(key, data, root);
197 assert( compare(new_key, item->key) );
200 rotate_backward(item);
206 assert ( root !=
NULL );
215 assert ( item !=
NULL );
216 assert ( root !=
NULL );
218 bool goto_left = ( item->left !=
NULL );
219 bool goto_right = ( item->right !=
NULL );
220 if ( goto_left && goto_right )
222 goto_right = ( compare( item->right->key, item->left->key ) );
223 goto_left = ! goto_right;
227 swap_with_father( item->right );
233 swap_with_father( item->left );
238 for (node* n = item, *f = n->father; f !=
NULL; n = f, f = n->father)
246 assert( f->right == n );
252 if ( item->father->left == item )
254 assert( item->father->sleft == 0 );
255 item->father->left =
NULL;
259 assert( item->father->right == item );
260 assert( item->father->sright == 0 );
261 item->father->right =
NULL;
266 assert( item == root );
276 node* create_new_node(
282 assert( subproblem !=
NULL );
284 if ( subproblem->sleft == 0 )
286 assert( subproblem->left ==
NULL );
288 node* nn =
new node(key,data);
289 subproblem->left = nn;
290 subproblem->sleft = 1;
291 nn->father = subproblem;
294 if ( subproblem->sright == 0 )
296 assert( subproblem->right ==
NULL );
298 node* nn =
new node(key,data);
299 subproblem->right = nn;
300 subproblem->sright = 1;
301 nn->father = subproblem;
304 assert( subproblem->left !=
NULL );
305 assert( subproblem->right !=
NULL );
307 if ( subproblem->sleft <= subproblem->sright )
309 subproblem->sleft += 1;
310 return create_new_node(key, data, subproblem->left);
313 subproblem->sright += 1;
314 return create_new_node(key, data, subproblem->right);
318 void swap_with_father(
322 int n1_sleft = n1->sleft;
323 int n1_sright = n1->sright;
324 node* n1_left = n1->left;
325 node* n1_right = n1->right;
326 node* n1_father = n1->father;
327 assert( n1_father !=
NULL );
328 assert( n1_father->left == n1 || n1_father->right == n1 );
330 if ( root == n1_father )
333 if ( n1_father->left == n1 )
335 n1->left = n1_father;
336 n1->right = n1_father->right;
340 assert( n1_father->right == n1 );
342 n1->left = n1_father->left;
343 n1->right = n1_father;
345 n1_father->left = n1_left;
346 n1_father->right = n1_right;
348 n1->sleft = n1_father->sleft;
349 n1->sright = n1_father->sright;
350 n1_father->sleft = n1_sleft;
351 n1_father->sright = n1_sright;
353 n1->father = n1_father->father;
354 n1_father->father = n1;
357 n1->left-> father = n1;
359 n1->right->father = n1;
360 if ( n1_father->left )
361 n1_father->left->father = n1_father;
362 if ( n1_father->right )
363 n1_father->right->father = n1_father;
366 if ( n1->father->left == n1_father )
367 n1->father->left = n1;
368 if ( n1->father->right == n1_father )
369 n1->father->right = n1;
373 void rotate_backward(
377 assert( item !=
NULL );
381 if ( ! compare( item->father->key, item->key ) )
383 swap_with_father( item );
384 rotate_backward( item );
pqueue_item insert(const Key &key, const Data &data)
void decrease_key(pqueue_item item, const Key &new_key)
const Key & get_key(pqueue_item it) const
const Data & get_data(pqueue_item it) const