| 448 | |
| 449 | template <typename K, typename V> |
| 450 | void SplayTree<K, V>::remove(node *n) |
| 451 | { |
| 452 | if (n == nullptr) |
| 453 | return; |
| 454 | splay(n); |
| 455 | --node_count_; |
| 456 | sum = sum - n->second; |
| 457 | if (node_count_ == 0) |
| 458 | { |
| 459 | root_.release(); |
| 460 | return; |
| 461 | } |
| 462 | if (!n->left) |
| 463 | { |
| 464 | root_ = move(n->right); |
| 465 | root_->parent = nullptr; |
| 466 | return; |
| 467 | } |
| 468 | else if (!n->right) |
| 469 | { |
| 470 | root_ = move(n->left); |
| 471 | root_->parent = nullptr; |
| 472 | } |
| 473 | else |
| 474 | { |
| 475 | node *nxt = subtreeMin(n->right.get()); |
| 476 | splay(nxt); |
| 477 | root_->left = move(root_->left->left); |
| 478 | root_->left->parent = root_.get(); |
| 479 | } |
| 480 | root_->maintain(); |
| 481 | } |
| 482 | |
| 483 | template <typename K, typename V> |
| 484 | void SplayTree<K, V>::getDOT(std::ostream &o) |