Index: uspace/lib/cpp/include/internal/rbtree.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree.hpp	(revision 6175b782364b40d67045a40efbb0ec9c120459ff)
+++ uspace/lib/cpp/include/internal/rbtree.hpp	(revision 73e37919d3d5ea5c01c91e4a2a133b3c37252b19)
@@ -41,5 +41,5 @@
         class KeyComp, class Alloc, class Size,
         class Iterator, class ConstIterator,
-        class Policy
+        class Policy, class Node
     >
     class rbtree
@@ -53,11 +53,11 @@
             using key_extract    = KeyExtractor;
 
-            using iterator             = Iterator;
-            using const_iterator       = ConstIterator;
+            using iterator       = Iterator;
+            using const_iterator = ConstIterator;
 
             using reverse_iterator       = std::reverse_iterator<iterator>;
             using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
-            using node_type = rbtree_node<value_type>;
+            using node_type = Node;
 
             rbtree(const key_compare& kcmp = key_compare{})
@@ -100,5 +100,5 @@
             bool empty() const noexcept
             {
-                return size_;
+                return size_ == 0U;
             }
 
@@ -202,5 +202,8 @@
 
                 node = delete_node(node);
-                return iterator{const_cast<node_type*>(node), node == nullptr};
+                if (!node)
+                    return iterator{find_largest_(), true};
+                else
+                    return iterator{const_cast<node_type*>(node), false};
             }
 
@@ -322,7 +325,7 @@
                     parent = current;
                     if (key_compare_(key, key_extractor_(current->value)))
-                        current = current->left;
+                        current = current->left();
                     else if (key_compare_(key_extractor_(current->value), key))
-                        current = current->right;
+                        current = current->right();
                     else
                         return current;
@@ -337,19 +340,43 @@
                 if (!node)
                     return nullptr;
+                if (auto tmp = node->get_node_for_deletion(); tmp != nullptr)
+                {
+                    /**
+                     * This will kick in multi containers,
+                     * we popped one node from a list of nodes
+                     * with equivalent keys and we can delete it
+                     * and return the original as it is still
+                     * in place.
+                     */
+                    delete tmp;
+
+                    return node;
+                }
 
                 --size_;
 
+                if (node == root_)
+                {
+                    delete node;
+                    root_ = nullptr;
+
+                    return nullptr;
+                }
+
                 auto succ = node->successor();
-                if (node->left && node->right)
+                if (node->left() && node->right())
                 {
                     node->swap(succ);
-
-                    // Succ has at most one child.
-                    delete_node(succ);
-
-                    return node;
-                }
-
-                auto child = node->right ? node->right : node->left;
+                    if (succ && !succ->parent())
+                        root_ = succ;
+
+                    // Node now has at most one child.
+                    // Also: If succ was nullptr, the swap
+                    //       didn't do anything and we can
+                    //       safely delete node.
+                    return delete_node(node);
+                }
+
+                auto child = node->right() ? node->right() : node->left();
                 if (!child)
                 {
@@ -362,9 +389,9 @@
                 {
                     // Replace with the child.
-                    child->parent = node->parent;
+                    child->parent(node->parent());
                     if (node->is_left_child())
-                        child->parent->left = child;
+                        child->parent()->left(child);
                     else if (node->is_right_child())
-                        child->parent->right = child;
+                        child->parent()->right(child);
 
                     // Repair if needed.
@@ -380,23 +407,5 @@
             void insert_node(node_type* node, node_type* parent)
             {
-                if (!node)
-                    return;
-
-                ++size_;
-                if (!parent)
-                {
-                    node->color = rbcolor::black;
-                    root_ = node;
-                }
-                else
-                {
-                    if (keys_comp(get_key(node->value), parent->value))
-                        parent->add_left_child(node);
-                    else
-                        parent->add_right_child(node);
-
-                    repair_after_insert_(node);
-                    update_root_(node);
-                }
+                Policy::insert(*this, node, parent);
             }
 
@@ -413,7 +422,7 @@
                 {
                     if (key_compare_(key, key_extractor_(current->value)))
-                        current = current->left;
+                        current = current->left();
                     else if (key_compare_(key_extractor_(current->value), key))
-                        current = current->right;
+                        current = current->right();
                     else
                         return current;
@@ -445,6 +454,6 @@
 
                 root_ = const_cast<node_type*>(node);
-                while (root_->parent)
-                    root_ = root_->parent;
+                while (root_->parent())
+                    root_ = root_->parent();
             }
 
Index: uspace/lib/cpp/include/internal/rbtree_iterators.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree_iterators.hpp	(revision 6175b782364b40d67045a40efbb0ec9c120459ff)
+++ uspace/lib/cpp/include/internal/rbtree_iterators.hpp	(revision 73e37919d3d5ea5c01c91e4a2a133b3c37252b19)
@@ -45,5 +45,5 @@
      */
 
-    template<class Value, class Reference, class Pointer, class Size>
+    template<class Value, class Reference, class Pointer, class Size, class Node>
     class rbtree_iterator
     {
@@ -57,5 +57,7 @@
             using iterator_category = bidirectional_iterator_tag;
 
-            rbtree_iterator(rbtree_node<value_type>* current = nullptr, bool end = true)
+            using node_type = Node;
+
+            rbtree_iterator(node_type* current = nullptr, bool end = true)
                 : current_{current}, end_{end}
             { /* DUMMY BODY */ }
@@ -78,34 +80,9 @@
                 if (current_)
                 {
-                    auto bckp = current_;
-                    if (current_->right)
-                        current_ = current_->right->find_smallest();
+                    auto next = current_->successor();
+                    if (next)
+                        current_ = next;
                     else
-                    {
-                        while (!current_->is_left_child())
-                        {
-                            current_ = current_->parent;
-
-                            if (!current_ || !current_->parent)
-                            {
-                                /**
-                                 * We've gone back to root without
-                                 * being a left child, which means we
-                                 * were the last node.
-                                 */
-                                end_ = true;
-                                current_ = bckp;
-
-                                return *this;
-                            }
-                        }
-
-                        /**
-                         * Now we are a left child,
-                         * so the next node we have to visit
-                         * is our parent.
-                         */
-                        current_ = current_->parent;
-                    }
+                        end_ = true;
                 }
 
@@ -132,22 +109,8 @@
                 if (current_)
                 {
-                    if (current_->left)
-                        current_ = current_->left->find_largest();
-                    else if (current_->parent)
-                    {
-                        while (current_->is_left_child())
-                            current_ = current_->parent;
-
-                        /**
-                         * We know parent exists here
-                         * because we went up from the
-                         * left and stopped being left
-                         * child (if at any point we happened
-                         * to become root then this branch
-                         * wouldn't happen).
-                         */
-                        current_ = current_->parent;
-                    }
-                    else // We are root without a left child.
+                    auto next = current_->predecessor();
+                    if (next)
+                        current_ = next;
+                    else
                         end_ = true;
                 }
@@ -164,10 +127,10 @@
             }
 
-            const rbtree_node<value_type>* node() const
+            const node_type* node() const
             {
                 return current_;
             }
 
-            rbtree_node<value_type>* node()
+            node_type* node()
             {
                 return current_;
@@ -180,5 +143,5 @@
 
         private:
-            rbtree_node<value_type>* current_;
+            node_type* current_;
             bool end_;
 
@@ -197,24 +160,24 @@
     };
 
-    template<class Val, class Ref, class Ptr, class Sz>
-    bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
-                    const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
+    template<class Val, class Ref, class Ptr, class Sz, class N>
+    bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs,
+                    const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs)
     {
         return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
     }
 
-    template<class Val, class Ref, class Ptr, class Sz>
-    bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
-                    const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
+    template<class Val, class Ref, class Ptr, class Sz, class N>
+    bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs,
+                    const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs)
     {
         return !(lhs == rhs);
     }
 
-    template<class Value, class ConstReference, class ConstPointer, class Size>
+    template<class Value, class ConstReference, class ConstPointer, class Size, class Node>
     class rbtree_const_iterator
     {
         using non_const_iterator_type = rbtree_iterator<
             Value, get_non_const_ref_t<ConstReference>,
-            get_non_const_ptr_t<ConstPointer>, Size
+            get_non_const_ptr_t<ConstPointer>, Size, Node
         >;
 
@@ -228,5 +191,7 @@
             using iterator_category = bidirectional_iterator_tag;
 
-            rbtree_const_iterator(const rbtree_node<value_type>* current = nullptr, bool end = true)
+            using node_type = Node;
+
+            rbtree_const_iterator(const node_type* current = nullptr, bool end = true)
                 : current_{current}, end_{end}
             { /* DUMMY BODY */ }
@@ -261,34 +226,9 @@
                 if (current_)
                 {
-                    auto bckp = current_;
-                    if (current_->right)
-                        current_ = current_->right->find_smallest();
+                    auto next = current_->successor();
+                    if (next)
+                        current_ = next;
                     else
-                    {
-                        while (!current_->is_left_child())
-                        {
-                            current_ = current_->parent;
-
-                            if (!current_->parent)
-                            {
-                                /**
-                                 * We've gone back to root without
-                                 * being a left child, which means we
-                                 * were the last node.
-                                 */
-                                end_ = true;
-                                current_ = bckp;
-
-                                return *this;
-                            }
-                        }
-
-                        /**
-                         * Now we are a left child,
-                         * so the next node we have to visit
-                         * is our parent.
-                         */
-                        current_ = current_->parent;
-                    }
+                        end_ = true;
                 }
 
@@ -315,23 +255,9 @@
                 if (current_)
                 {
-                    if (current_->left)
-                        current_ = current_->left->find_largest();
-                    else if (current_->parent)
-                    {
-                        while (current_->is_left_child())
-                            current_ = current_->parent;
-
-                        /**
-                         * We know parent exists here
-                         * because we went up from the
-                         * left and stopped being left
-                         * child (if at any point we happened
-                         * to become root then this branch
-                         * wouldn't happen).
-                         */
-                        current_ = current_->parent;
-                    }
-                    else // We are root without a left child.
-                        current_ = nullptr;
+                    auto next = current_->predecessor();
+                    if (next)
+                        current_ = next;
+                    else
+                        end_ = true;
                 }
 
@@ -347,5 +273,5 @@
             }
 
-            const rbtree_node<value_type>* node() const
+            const node_type* node() const
             {
                 return current_;
@@ -358,5 +284,5 @@
 
         private:
-            const rbtree_node<value_type>* current_;
+            const node_type* current_;
             bool end_;
 
@@ -375,42 +301,42 @@
     };
 
-    template<class Val, class CRef, class CPtr, class Sz>
-    bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz>& lhs,
-                    const rbtree_const_iterator<Val, CRef, CPtr, Sz>& rhs)
+    template<class Val, class CRef, class CPtr, class Sz, class N>
+    bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs,
+                    const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs)
     {
         return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
     }
 
-    template<class Val, class CRef, class CPtr, class Sz>
-    bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz>& lhs,
-                    const rbtree_const_iterator<Val, CRef, CPtr, Sz>& rhs)
+    template<class Val, class CRef, class CPtr, class Sz, class N>
+    bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs,
+                    const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs)
     {
         return !(lhs == rhs);
     }
 
-    template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz>
-    bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
-                    const rbtree_const_iterator<Val, CRef, CPtr, Sz>& rhs)
+    template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz, class N>
+    bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs,
+                    const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs)
     {
         return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
     }
 
-    template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz>
-    bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
-                    const rbtree_const_iterator<Val, CRef, CPtr, Sz>& rhs)
+    template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz, class N>
+    bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz, N>& lhs,
+                    const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& rhs)
     {
         return !(lhs == rhs);
     }
 
-    template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz>
-    bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz>& lhs,
-                    const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
+    template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz, class N>
+    bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs,
+                    const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs)
     {
         return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
     }
 
-    template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz>
-    bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz>& lhs,
-                    const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
+    template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz, class N>
+    bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz, N>& lhs,
+                    const rbtree_iterator<Val, Ref, Ptr, Sz, N>& rhs)
     {
         return !(lhs == rhs);
Index: uspace/lib/cpp/include/internal/rbtree_node.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree_node.hpp	(revision 6175b782364b40d67045a40efbb0ec9c120459ff)
+++ uspace/lib/cpp/include/internal/rbtree_node.hpp	(revision 73e37919d3d5ea5c01c91e4a2a133b3c37252b19)
@@ -30,4 +30,5 @@
 #define LIBCPP_INTERNAL_RBTREE_NODE
 
+#include <cassert>
 #include <utility>
 
@@ -39,36 +40,23 @@
     };
 
-    template<class T>
-    struct rbtree_node
+    template<class Node>
+    struct rbtree_utils
     {
-        T value;
-        rbcolor color;
-
-        rbtree_node* parent;
-        rbtree_node* left;
-        rbtree_node* right;
-
-        template<class... Args>
-        rbtree_node(Args&&... args)
-            : value{forward<Args>(args)...}, color{rbcolor::red},
-              parent{}, left{}, right{}
-        { /* DUMMY BODY */ }
-
-        rbtree_node* grandparent() const
-        {
-            if (parent)
-                return parent->parent;
+        static Node* grandparent(Node* node)
+        {
+            if (node && node->parent())
+                return node->parent->parent();
             else
                 return nullptr;
         }
 
-        rbtree_node* brother() const
-        {
-            if (parent)
-            {
-                if (this == parent->left)
-                    return parent->right;
-                else
-                    return parent->left;
+        static Node* brother(Node* node)
+        {
+            if (node && node->parent())
+            {
+                if (node == node->parent->left())
+                    return node->parent->right();
+                else
+                    return node->parent->left();
             }
             else
@@ -76,12 +64,13 @@
         }
 
-        rbtree_node* uncle() const
-        {
-            if (grandparent())
-            {
-                if (parent == grandparent()->left)
-                    return grandparent()->right;
-                else
-                    return grandparent()->left;
+        static Node* uncle(Node* node)
+        {
+            auto gp = grandparent(node);
+            if (gp)
+            {
+                if (node->parent() == gp->left())
+                    return gp->right();
+                else
+                    return gp->left();
             }
             else
@@ -89,115 +78,559 @@
         }
 
-        bool is_left_child() const
-        {
-            if (parent)
-                return parent->left == this;
+        static bool is_left_child(const Node* node)
+        {
+            if (!node)
+                return false;
+
+            if (node->parent())
+                return node->parent()->left() == node;
             else
                 return false;
         }
 
-        bool is_right_child() const
-        {
-            if (parent)
-                return parent->right == this;
+        static bool is_right_child(const Node* node)
+        {
+            if (!node)
+                return false;
+
+            if (node->parent())
+                return node->parent()->right() == node;
             else
                 return false;
         }
 
-        void rotate_left()
-        {
-            // TODO:
-        }
-
-        void rotate_right()
-        {
-            // TODO:
-        }
-
-        rbtree_node* find_smallest()
-        {
-            auto res = this;
-            while (res->left)
-                res = res->left;
-
-            return res;
-        }
-
-        const rbtree_node* find_smallest() const
-        {
-            auto res = this;
-            while (res->left)
-                res = res->left;
-
-            return res;
-        }
-
-        rbtree_node* find_largest()
-        {
-            auto res = this;
-            while (res->right)
-                res = res->right;
-
-            return res;
-        }
-
-        const rbtree_node* find_largest() const
-        {
-            auto res = this;
-            while (res->right)
-                res = res->right;
-
-            return res;
-        }
-
-        rbtree_node* successor() const
-        {
-            if (right)
-                return right->find_smallest();
+        static void rotate_left(Node* node)
+        {
+            // TODO: implement
+        }
+
+        static void rotate_right(Node* node)
+        {
+            // TODO: implement
+        }
+
+        static Node* find_smallest(Node* node)
+        {
+            return const_cast<Node*>(find_smallest(const_cast<const Node*>(node)));
+        }
+
+        static const Node* find_smallest(const Node* node)
+        {
+            if (!node)
+                return nullptr;
+
+            while (node->left())
+                node = node->left();
+
+            return node;
+        }
+
+        static Node* find_largest(Node* node)
+        {
+            return const_cast<Node*>(find_largest(const_cast<const Node*>(node)));
+        }
+
+        static const Node* find_largest(const Node* node)
+        {
+            if (!node)
+                return nullptr;
+
+            while (node->right())
+                node = node->right();
+
+            return node;
+        }
+
+        static Node* successor(Node* node)
+        {
+            return const_cast<Node*>(successor(const_cast<const Node*>(node)));
+        }
+
+        static const Node* successor(const Node* node)
+        {
+            if (!node)
+                return nullptr;
+
+            if (node->right())
+                return find_smallest(node->right());
             else
             {
-                auto current = this;
-                while (!current->is_left_child())
-                    current = current->parent;
-
-                return current->parent;
-            }
-        }
-
-        void add_left_child(rbtree_node* node)
-        {
-            if (left)
+                while (node && !is_left_child(node))
+                    node = node->parent();
+
+                if (node)
+                    return node->parent();
+                else
+                    return node;
+            }
+        }
+
+        static Node* predecessor(Node* node)
+        {
+            return const_cast<Node*>(predecessor(const_cast<const Node*>(node)));
+        }
+
+        static const Node* predecessor(const Node* node)
+        {
+            if (!node)
+                return nullptr;
+
+            if (node->left())
+                return find_largest(node->left());
+            else
+            {
+                while (node && is_left_child(node))
+                    node = node->parent();
+
+                if (node)
+                    return node->parent();
+                else
+                    return node;
+            }
+        }
+
+        static void add_left_child(Node* node, Node* child)
+        {
+            if (!node || !child)
                 return;
 
-            left = node;
-            node->parent = this;
-        }
-
-        void add_right_child(rbtree_node* node)
-        {
-            if (right)
+            node->left(child);
+            child->parent(node);
+        }
+
+        static void add_right_child(Node* node, Node* child)
+        {
+            if (!node || !child)
                 return;
 
-            right = node;
-            node->parent = this;
-        }
-
-        void swap(rbtree_node* other)
-        {
-            std::swap(value, other->value);
-        }
-
-        void unlink()
-        {
-            if (is_left_child())
-                parent->left = nullptr;
-            else if (is_right_child())
-                parent->right = nullptr;
-        }
-
-        ~rbtree_node()
-        {
-            // TODO: delete recursively or iteratively?
-        }
+            node->right(child);
+            child->parent(node);
+        }
+
+        static void swap(Node* node1, Node* node2)
+        {
+            if (!node1 || !node2)
+                return;
+
+            auto parent1 = node1->parent();
+            auto left1 = node1->left();
+            auto right1 = node1->right();
+            auto is_right1 = is_right_child(node1);
+
+            auto parent2 = node2->parent();
+            auto left2 = node2->left();
+            auto right2 = node2->right();
+            auto is_right2 = is_right_child(node2);
+
+            assimilate(node1, parent2, left2, right2, is_right2);
+            assimilate(node2, parent1, left1, right1, is_right1);
+        }
+
+        static void assimilate(
+            Node* node, Node* p, Node* l, Node* r, bool is_r
+        )
+        {
+            if (!node)
+                return;
+
+            node->parent(p);
+            if (node->parent())
+            {
+                if (is_r)
+                    node->parent()->right(node);
+                else
+                    node->parent()->left(node);
+            }
+
+            node->left(l);
+            if (node->left())
+                node->left()->parent(node);
+
+            node->right(r);
+            if (node->right())
+                node->right()->parent(node);
+        }
+    };
+
+    template<class T>
+    struct rbtree_single_node
+    {
+        using utils = rbtree_utils<rbtree_single_node<T>>;
+
+        public:
+            T value;
+            rbcolor color;
+
+            template<class... Args>
+            rbtree_single_node(Args&&... args)
+                : value{forward<Args>(args)...}, color{rbcolor::red},
+                  parent_{}, left_{}, right_{}
+            { /* DUMMY BODY */ }
+
+            rbtree_single_node* parent() const
+            {
+                return parent_;
+            }
+
+            void parent(rbtree_single_node* node)
+            {
+                parent_ = node;
+            }
+
+            rbtree_single_node* left() const
+            {
+                return left_;
+            }
+
+            void left(rbtree_single_node* node)
+            {
+                left_ = node;
+            }
+
+            rbtree_single_node* right() const
+            {
+                return right_;
+            }
+
+            void right(rbtree_single_node* node)
+            {
+                right_ = node;
+            }
+
+            rbtree_single_node* grandparent()
+            {
+                return utils::grandparent(this);
+            }
+
+            rbtree_single_node* brother()
+            {
+                return utils::brother(this);
+            }
+
+            rbtree_single_node* uncle()
+            {
+                return utils::uncle(this);
+            }
+
+            bool is_left_child() const
+            {
+                return utils::is_left_child(this);
+            }
+
+            bool is_right_child() const
+            {
+                return utils::is_right_child(this);
+            }
+
+            void rotate_left()
+            {
+                utils::rotate_left(this);
+            }
+
+            void rotate_right()
+            {
+                utils::rotate_right(this);
+            }
+
+            rbtree_single_node* find_smallest()
+            {
+                return utils::find_smallest(this);
+            }
+
+            const rbtree_single_node* find_smallest() const
+            {
+                return utils::find_smallest(this);
+            }
+
+            rbtree_single_node* find_largest()
+            {
+                return utils::find_largest(this);
+            }
+
+            const rbtree_single_node* find_largest() const
+            {
+                return utils::find_largest(this);
+            }
+
+            rbtree_single_node* successor()
+            {
+                return utils::successor(this);
+            }
+
+            const rbtree_single_node* successor() const
+            {
+                return utils::successor(this);
+            }
+
+            rbtree_single_node* predecessor()
+            {
+                return utils::predecessor(this);
+            }
+
+            const rbtree_single_node* predecessor() const
+            {
+                return utils::predecessor(this);
+            }
+
+            void add_left_child(rbtree_single_node* node)
+            {
+                utils::add_left_child(this, node);
+            }
+
+            void add_right_child(rbtree_single_node* node)
+            {
+                utils::add_right_child(this, node);
+            }
+
+            void swap(rbtree_single_node* other)
+            {
+                utils::swap(this, other);
+            }
+
+            void unlink()
+            {
+                if (is_left_child())
+                    parent_->left_ = nullptr;
+                else if (is_right_child())
+                    parent_->right_ = nullptr;
+            }
+
+            rbtree_single_node* get_node_for_deletion()
+            {
+                return nullptr;
+            }
+
+            ~rbtree_single_node()
+            {
+                parent_ = nullptr;
+                if (left_)
+                    delete left_;
+                if (right_)
+                    delete right_;
+            }
+
+        private:
+            rbtree_single_node* parent_;
+            rbtree_single_node* left_;
+            rbtree_single_node* right_;
+    };
+
+    template<class T>
+    struct rbtree_multi_node
+    {
+        using utils = rbtree_utils<rbtree_multi_node<T>>;
+
+        public:
+            T value;
+            rbcolor color;
+
+            template<class... Args>
+            rbtree_multi_node(Args&&... args)
+                : value{forward<Args>(args)...}, color{rbcolor::red},
+                  parent_{}, left_{}, right_{}, next_{}, first_{this}
+            { /* DUMMY BODY */ }
+
+            rbtree_multi_node* parent() const
+            {
+                return parent_;
+            }
+
+            void parent(rbtree_multi_node* node)
+            {
+                parent_ = node;
+
+                auto tmp = first_;
+                while (tmp)
+                {
+                    tmp->parent_ = node;
+                    tmp = tmp->next_;
+                }
+            }
+
+            rbtree_multi_node* left() const
+            {
+                return left_;
+            }
+
+            void left(rbtree_multi_node* node)
+            {
+                left_ = node;
+
+                auto tmp = first_;
+                while (tmp)
+                {
+                    tmp->left_ = node;
+                    tmp = tmp->next_;
+                }
+            }
+
+            rbtree_multi_node* right() const
+            {
+                return right_;
+            }
+
+            void right(rbtree_multi_node* node)
+            {
+                right_ = node;
+
+                auto tmp = first_;
+                while (tmp)
+                {
+                    tmp->right_ = node;
+                    tmp = tmp->next_;
+                }
+            }
+
+            rbtree_multi_node* grandparent()
+            {
+                return utils::grandparent(this);
+            }
+
+            rbtree_multi_node* brother()
+            {
+                return utils::brother(this);
+            }
+
+            rbtree_multi_node* uncle()
+            {
+                return utils::uncle(this);
+            }
+
+            bool is_left_child() const
+            {
+                return utils::is_left_child(this);
+            }
+
+            bool is_right_child()
+            {
+                return utils::is_right_child(this);
+            }
+
+            void rotate_left()
+            {
+                utils::rotate_left(this);
+            }
+
+            void rotate_right()
+            {
+                utils::rotate_right(this);
+            }
+
+            rbtree_multi_node* find_smallest()
+            {
+                return utils::find_smallest(this);
+            }
+
+            const rbtree_multi_node* find_smallest() const
+            {
+                return utils::find_smallest(this);
+            }
+
+            rbtree_multi_node* find_largest()
+            {
+                return utils::find_largest(this);
+            }
+
+            const rbtree_multi_node* find_largest() const
+            {
+                return utils::find_largest(this);
+            }
+
+            rbtree_multi_node* successor()
+            {
+                return const_cast<
+                    rbtree_multi_node*
+                >(const_cast<const rbtree_multi_node*>(this)->successor());
+            }
+
+            const rbtree_multi_node* successor() const
+            {
+                if (next_)
+                    return next_;
+                else
+                    return utils::successor(this);
+            }
+
+            rbtree_multi_node* predecessor()
+            {
+                return const_cast<
+                    rbtree_multi_node*
+                >(const_cast<const rbtree_multi_node*>(this)->predecessor());
+            }
+
+            const rbtree_multi_node* predecessor() const
+            {
+                return utils::predecessor(this);
+            }
+
+            void add_left_child(rbtree_multi_node* node)
+            {
+                utils::add_left_child(this, node);
+            }
+
+            void add_right_child(rbtree_multi_node* node)
+            {
+                utils::add_right_child(this, node);
+            }
+
+            void swap(rbtree_multi_node* other)
+            {
+                utils::swap(this, other);
+            }
+
+            rbtree_multi_node<T>* get_node_for_deletion()
+            {
+                if (next_)
+                {
+                    auto tmp = next_;
+                    while (tmp && tmp->next_ != this)
+                        tmp = tmp->next_;
+
+                    return tmp; // This will get deleted.
+                }
+                else
+                    return nullptr;
+            }
+
+            void unlink()
+            {
+                if (is_left_child())
+                    parent->left_ = nullptr;
+                else if (is_right_child())
+                    parent->right_ = nullptr;
+            }
+
+            void add(rbtree_multi_node* node)
+            {
+                if (next_)
+                    next_->add(node);
+                else
+                {
+                    next_ = node;
+                    next_->first_ = first_;
+                    next_->parent_ = parent_;
+                    next_->left_ = left_;
+                    next_->right_ = right_;
+                }
+            }
+
+            ~rbtree_multi_node()
+            {
+                parent_ = nullptr;
+                if (left_)
+                    delete left_;
+                if (right)
+                    delete right_;
+
+                // TODO: delete the list
+            }
+
+        private:
+            rbtree_multi_node* parent_;
+            rbtree_multi_node* left_;
+            rbtree_multi_node* right_;
+
+            rbtree_multi_node* next_;
+            rbtree_multi_node* first_;
     };
 }
Index: uspace/lib/cpp/include/internal/rbtree_policies.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree_policies.hpp	(revision 6175b782364b40d67045a40efbb0ec9c120459ff)
+++ uspace/lib/cpp/include/internal/rbtree_policies.hpp	(revision 73e37919d3d5ea5c01c91e4a2a133b3c37252b19)
@@ -59,9 +59,10 @@
         static typename Tree::iterator lower_bound(const Tree& tree, const Key& key)
         {
-            using iterator = typename Tree::iterator;
+            using iterator  = typename Tree::iterator;
+            using node_type = typename Tree::node_type;
 
             auto it = lower_bound_const(tree, key);
 
-            return iterator{it.node(), it.end()};
+            return iterator{const_cast<node_type*>(it.node()), it.end()};
         }
 
@@ -101,9 +102,10 @@
         static typename Tree::iterator upper_bound(const Tree& tree, const Key& key)
         {
-            using iterator = typename Tree::iterator;
+            using iterator  = typename Tree::iterator;
+            using node_type = typename Tree::node_type;
 
             auto it = upper_bound_const(tree, key);
 
-            return iterator{it.node(), it.end()};
+            return iterator{const_cast<node_type*>(it.node()), it.end()};
         }
 
@@ -113,18 +115,14 @@
             /**
              * If key isn't in the tree, we get it's
-             * successor or tree.end(). If key is
-             * in the tree, we get it.
-             * In the first case, the successor is also
-             * the upper bound, so we just return it,
-             * otherwise (as long as it != end()) we
-             * increment.
+             * predecessor or tree.end(). If key is
+             * in the tree, we get it. So unless it
+             * is equal to end(), we can increment it
+             * to get the upper bound.
              */
             auto it = lower_bound_const(tree, key);
             if (it == tree.end())
                 return it;
-            else if (tree.keys_equal(key, *it))
+            else
                 return ++it;
-            else
-                return it;
         }
 
@@ -176,7 +174,6 @@
 
             auto node = new node_type{move(val)};
-            tree.insert_node(node, parent);
-
-            return make_pair(iterator{node, false}, true);
+
+            return insert(tree, node, parent);
         }
 
@@ -194,7 +191,6 @@
 
             auto node = new node_type{val};
-            tree.insert_node(node, parent);
-
-            return make_pair(iterator{node, false}, true);
+
+            return insert(tree, node, parent);
         }
 
@@ -212,5 +208,37 @@
 
             auto node = new node_type{forward<Value>(val)};
-            tree.insert_node(node, parent);
+
+            return insert(tree, node, parent);
+        }
+
+        template<class Tree>
+        static pair<
+            typename Tree::iterator, bool
+        > insert(
+            Tree& tree, typename Tree::node_type* node,
+            typename Tree::node_type* parent
+        )
+        {
+            using iterator  = typename Tree::iterator;
+
+            if (!node)
+                return make_pair(tree.end(), false);
+
+            ++tree.size_;
+            if (!parent)
+            {
+                node->color = rbcolor::black;
+                tree.root_ = node;
+            }
+            else
+            {
+                if (tree.keys_comp(tree.get_key(node->value), parent->value))
+                    parent->add_left_child(node);
+                else
+                    parent->add_right_child(node);
+
+                tree.repair_after_insert_(node);
+                tree.update_root_(node);
+            }
 
             return make_pair(iterator{node, false}, true);
@@ -308,10 +336,8 @@
             /**
              * If key isn't in the tree, we get it's
-             * successor or tree.end(). If key is
-             * in the tree, we get it.
-             * In the first case, the successor is also
-             * the upper bound, so we just return it,
-             * otherwise (as long as it != end()) we
-             * increment.
+             * predecessor or tree.end(). If key is
+             * in the tree, we get it. So unless it
+             * is equal to end(), we keep incrementing
+             * until we get to the next key.
              */
             auto it = lower_bound(tree, key);
@@ -320,5 +346,5 @@
             else if (tree.keys_equal(tree.get_key(*it), key))
             {
-                while (tree.keys_equal(tree.get_key(*it), key))
+                while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
                     ++it;
 
@@ -384,10 +410,39 @@
 
         template<class Tree>
-        static typename Tree::iterator insert(Tree& tree, typename Tree::node_type* node)
-        {
-            using iterator  = typename Tree::iterator;
+        static typename Tree::iterator insert(
+            Tree& tree, typename Tree::node_type* node,
+            typename Tree::node_type* = nullptr
+        )
+        {
+            using iterator  = typename Tree::iterator;
+
+            if (!node)
+                return tree.end();
 
             auto parent = tree.find_parent_for_insertion(tree.get_key(node->value));
-            tree.insert_node(node, parent);
+
+            ++tree.size_;
+            if (!parent)
+            {
+                node->color = rbcolor::black;
+                tree.root_ = node;
+            }
+            else
+            {
+                if (tree.keys_comp(tree.get_key(node->value), parent->value))
+                    parent->add_left_child(node);
+                else if (tree.keys_comp(tree.get_key(parent->value), node->value))
+                    parent->add_right_child(node);
+                else
+                {
+                    parent->add(node); // List of nodes with equivalent keys.
+                    tree.update_root_(parent);
+
+                    return iterator{node, false};
+                }
+
+                tree.repair_after_insert_(node);
+                tree.update_root_(node);
+            }
 
             return iterator{node, false};