31 template<
typename Key,
33 typename Compare = less<Key> >
66 void delete_children_recursive()
70 left->delete_children_recursive();
76 right->delete_children_recursive();
118 root->delete_children_recursive();
127 return ( root ==
NULL );
133 return ( root ==
NULL ? 0 : root->sleft + root->sright + 1 );
141 assert( it !=
NULL );
150 assert( it !=
NULL );
169 nn =
new node(key,data);
171 throw std::bad_alloc();
175 nn = create_new_node(key, data, root);
188 assert( compare(new_key, item->key) );
191 rotate_backward(item);
197 assert ( root !=
NULL );
206 assert ( item !=
NULL );
207 assert ( root !=
NULL );
209 bool goto_left = ( item->left !=
NULL );
210 bool goto_right = ( item->right !=
NULL );
211 if ( goto_left && goto_right )
213 goto_right = ( compare( item->right->key, item->left->key ) );
214 goto_left = ! goto_right;
218 swap_with_father( item->right );
224 swap_with_father( item->left );
229 for (node* n = item, *f = n->father; f !=
NULL; n = f, f = n->father)
237 assert( f->right == n );
243 if ( item->father->left == item )
245 assert( item->father->sleft == 0 );
246 item->father->left =
NULL;
250 assert( item->father->right == item );
251 assert( item->father->sright == 0 );
252 item->father->right =
NULL;
257 assert( item == root );
267 node* create_new_node(
273 assert( subproblem !=
NULL );
275 if ( subproblem->sleft == 0 )
277 assert( subproblem->left ==
NULL );
279 node* nn =
new node(key,data);
280 subproblem->left = nn;
281 subproblem->sleft = 1;
282 nn->father = subproblem;
285 if ( subproblem->sright == 0 )
287 assert( subproblem->right ==
NULL );
289 node* nn =
new node(key,data);
290 subproblem->right = nn;
291 subproblem->sright = 1;
292 nn->father = subproblem;
295 assert( subproblem->left !=
NULL );
296 assert( subproblem->right !=
NULL );
298 if ( subproblem->sleft <= subproblem->sright )
300 subproblem->sleft += 1;
301 return create_new_node(key, data, subproblem->left);
304 subproblem->sright += 1;
305 return create_new_node(key, data, subproblem->right);
309 void swap_with_father(
313 int n1_sleft = n1->sleft;
314 int n1_sright = n1->sright;
315 node* n1_left = n1->left;
316 node* n1_right = n1->right;
317 node* n1_father = n1->father;
318 assert( n1_father !=
NULL );
319 assert( n1_father->left == n1 || n1_father->right == n1 );
321 if ( root == n1_father )
324 if ( n1_father->left == n1 )
326 n1->left = n1_father;
327 n1->right = n1_father->right;
331 assert( n1_father->right == n1 );
333 n1->left = n1_father->left;
334 n1->right = n1_father;
336 n1_father->left = n1_left;
337 n1_father->right = n1_right;
339 n1->sleft = n1_father->sleft;
340 n1->sright = n1_father->sright;
341 n1_father->sleft = n1_sleft;
342 n1_father->sright = n1_sright;
344 n1->father = n1_father->father;
345 n1_father->father = n1;
348 n1->left-> father = n1;
350 n1->right->father = n1;
351 if ( n1_father->left )
352 n1_father->left->father = n1_father;
353 if ( n1_father->right )
354 n1_father->right->father = n1_father;
357 if ( n1->father->left == n1_father )
358 n1->father->left = n1;
359 if ( n1->father->right == n1_father )
360 n1->father->right = n1;
364 void rotate_backward(
368 assert( item !=
NULL );
372 if ( ! compare( item->father->key, item->key ) )
374 swap_with_father( item );
375 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