Index: uspace/lib/cpp/include/internal/rbtree.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree.hpp	(revision 647b756ccd6a5c6ebdf8df6116ecbe4760f73368)
+++ uspace/lib/cpp/include/internal/rbtree.hpp	(revision 369f5dfce0b2ad0b154aaf89054eb64daa6cf4f8)
@@ -178,41 +178,17 @@
 
             template<class... Args>
-            pair<iterator, bool> emplace(Args&&... args)
-            {
-                auto ret = Policy::emplace(*this, forward<Args>(args)...);
-                if (!ret.second)
-                    return ret;
-                ++size_;
-
-                repair_after_insert_(ret.first.node());
-                update_root_(ret.first.node());
-
-                return ret;
-            }
-
-            pair<iterator, bool> insert(const value_type& val)
-            {
-                auto ret = Policy::insert(*this, val);
-                if (!ret.second)
-                    return ret;
-                ++size_;
-
-                repair_after_insert_(ret.first.node());
-                update_root_(ret.first.node());
-
-                return ret;
-            }
-
-            pair<iterator, bool> insert(value_type&& val)
-            {
-                auto ret = Policy::insert(*this, forward<value_type>(val));
-                if (!ret.second)
-                    return ret;
-                ++size_;
-
-                repair_after_insert_(ret.first.node());
-                update_root_(ret.first.node());
-
-                return ret;
+            auto emplace(Args&&... args)
+            {
+                return Policy::emplace(*this, forward<Args>(args)...);
+            }
+
+            auto insert(const value_type& val)
+            {
+                return Policy::insert(*this, val);
+            }
+
+            auto insert(value_type&& val)
+            {
+                return Policy::insert(*this, forward<value_type>(val));
             }
 
@@ -228,8 +204,7 @@
 
                 auto node = const_cast<node_type*>(it.node());
-                ++it;
-
-                delete_node(node);
-                return iterator{const_cast<node_type*>(it.node()), it.end()};
+
+                node = delete_node(node);
+                return iterator{const_cast<node_type*>(node), node == nullptr};
             }
 
@@ -320,4 +295,5 @@
                 auto it2 = other.begin();
 
+                // TODO: this doesn't compare values :/
                 while (keys_equal(*it1++, *it2++))
                 { /* DUMMY BODY */ }
@@ -358,19 +334,21 @@
             }
 
-            void delete_node(node_type* node)
-            {
+            node_type* delete_node(const node_type* n)
+            {
+                auto node = const_cast<node_type*>(n);
                 if (!node)
-                    return;
+                    return nullptr;
 
                 --size_;
 
+                auto succ = node->successor();
                 if (node->left && node->right)
                 {
-                    node->swap(node->successor());
-
-                    // Node now has at most one child.
-                    delete_node(node);
-
-                    return;
+                    node->swap(succ);
+
+                    // Succ has at most one child.
+                    delete_node(succ);
+
+                    return node;
                 }
 
@@ -379,6 +357,6 @@
                 {
                     // Simply remove the node.
+                    // TODO: repair here too?
                     node->unlink();
-
                     delete node;
                 }
@@ -389,5 +367,5 @@
                     if (node->is_left_child())
                         child->parent->left = child;
-                    else if (node->is_left_child())
+                    else if (node->is_right_child())
                         child->parent->right = child;
 
@@ -395,5 +373,9 @@
                     repair_after_erase_(node, child);
                     update_root_(child);
-                }
+
+                    delete node;
+                }
+
+                return succ;
             }