diff --git a/src/radix.h b/src/radix.h
--- a/src/radix.h
+++ b/src/radix.h
@@ -14,6 +14,7 @@
 #include <atomic>
 #include <cstdint>
 #include <memory>
+#include <type_traits>
 
 /**
  * This is a radix tree storing values identified by a unique key.
@@ -43,7 +44,8 @@
     static const int MASK = (1 << BITS) - 1;
     static const size_t CHILD_PER_LEVEL = 1 << BITS;
 
-    typedef decltype(std::declval<T &>().getId()) K;
+    typedef typename std::remove_reference<decltype(
+        std::declval<T &>().getId())>::type K;
     static const size_t KEY_BITS = 8 * sizeof(K);
     static const uint32_t TOP_LEVEL = (KEY_BITS - 1) / BITS;
 
@@ -59,13 +61,15 @@
      * Insert a value into the tree.
      * Returns true if the value was inserted, false if it was already present.
      */
-    bool insert(T *value) { return insert(value->getId(), value); }
+    bool insert(const RCUPtr<T> &value) {
+        return insert(value->getId(), value);
+    }
 
     /**
      * Get the value corresponding to a key.
-     * Returns the value if found, null if not.
+     * Returns the value if found, nullptr if not.
      */
-    T *get(const K &key) {
+    RCUPtr<T> get(const K &key) {
         uint32_t level = TOP_LEVEL;
 
         RCULock lock;
@@ -79,23 +83,23 @@
         T *leaf = e.getLeaf();
         if (leaf == nullptr || leaf->getId() != key) {
             // We failed to find the proper element.
-            return nullptr;
+            return RCUPtr<T>();
         }
 
         // The leaf is non-null and the keys match. We have our guy.
-        return leaf;
+        return RCUPtr<T>::copy(leaf);
     }
 
-    const T *get(const K &key) const {
-        return const_cast<RadixTree *>(this)->get(key);
+    RCUPtr<const T> get(const K &key) const {
+        T const *ptr = const_cast<RadixTree *>(this)->get(key).release();
+        return RCUPtr<const T>::acquire(ptr);
     }
 
     /**
      * Remove an element from the tree.
-     * Returns true if the element was removed from the tree, false if the
-     * element wasn't found in the tree.
+     * Returns the removed element, or nullptr if there isn't one.
      */
-    bool remove(const K &key) {
+    RCUPtr<T> remove(const K &key) {
         uint32_t level = TOP_LEVEL;
 
         RCULock lock;
@@ -113,12 +117,12 @@
         T *leaf = e.getLeaf();
         if (leaf == nullptr || leaf->getId() != key) {
             // We failed to find the proper element.
-            return false;
+            return RCUPtr<T>();
         }
 
         // We have the proper element, try to delete it.
         if (eptr->compare_exchange_strong(e, RadixElement())) {
-            return true;
+            return RCUPtr<T>::acquire(leaf);
         }
 
         // The element was replaced, either by a subtree or another element.
@@ -127,11 +131,11 @@
         }
 
         // The element in the slot is not the one we are looking for.
-        return false;
+        return RCUPtr<T>();
     }
 
 private:
-    bool insert(const K &key, T *value) {
+    bool insert(const K &key, RCUPtr<T> value) {
         uint32_t level = TOP_LEVEL;
 
         RCULock lock;
@@ -149,7 +153,9 @@
 
             // If the slot is empty, try to insert right there.
             if (e.getLeaf() == nullptr) {
-                if (eptr->compare_exchange_strong(e, RadixElement(value))) {
+                if (eptr->compare_exchange_strong(e,
+                                                  RadixElement(value.get()))) {
+                    value.release();
                     return true;
                 }
 
diff --git a/src/test/radix_tests.cpp b/src/test/radix_tests.cpp
--- a/src/test/radix_tests.cpp
+++ b/src/test/radix_tests.cpp
@@ -18,56 +18,58 @@
 
     TestElement(K keyIn) : key(keyIn) {}
     const K &getId() const { return key; }
+
+    IMPLEMENT_RCU_REFCOUNT(uint32_t);
 };
 
 template <typename K> void testInsert() {
     typedef TestElement<K> E;
     RadixTree<E> mytree;
 
-    E zero(0);
-    E one(1);
-    E two(2);
-    E three(3);
+    auto zero = RCUPtr<E>::make(0);
+    auto one = RCUPtr<E>::make(1);
+    auto two = RCUPtr<E>::make(2);
+    auto three = RCUPtr<E>::make(3);
 
     // Inserting a new element into the tree returns true.
-    BOOST_CHECK(mytree.insert(&one));
+    BOOST_CHECK(mytree.insert(one));
 
     // Inserting an element already in the tree returns false.
-    BOOST_CHECK(!mytree.insert(&one));
+    BOOST_CHECK(!mytree.insert(one));
 
     // Let's insert more elements and check behavior stays consistent.
-    BOOST_CHECK(mytree.insert(&zero));
-    BOOST_CHECK(!mytree.insert(&one));
-    BOOST_CHECK(mytree.insert(&two));
-    BOOST_CHECK(mytree.insert(&three));
-    BOOST_CHECK(!mytree.insert(&zero));
-    BOOST_CHECK(!mytree.insert(&one));
-    BOOST_CHECK(!mytree.insert(&two));
-    BOOST_CHECK(!mytree.insert(&three));
+    BOOST_CHECK(mytree.insert(zero));
+    BOOST_CHECK(!mytree.insert(one));
+    BOOST_CHECK(mytree.insert(two));
+    BOOST_CHECK(mytree.insert(three));
+    BOOST_CHECK(!mytree.insert(zero));
+    BOOST_CHECK(!mytree.insert(one));
+    BOOST_CHECK(!mytree.insert(two));
+    BOOST_CHECK(!mytree.insert(three));
 
     // Check extreme values.
     typedef typename std::make_signed<K>::type SK;
-    E maxsigned(std::numeric_limits<SK>::max());
-    E minsigned(std::numeric_limits<SK>::min());
+    auto maxsigned = RCUPtr<E>::make(std::numeric_limits<SK>::max());
+    auto minsigned = RCUPtr<E>::make(std::numeric_limits<SK>::min());
     typedef typename std::make_unsigned<K>::type UK;
-    E minusone(std::numeric_limits<UK>::max());
-    E minustwo(std::numeric_limits<UK>::max() - 1);
+    auto minusone = RCUPtr<E>::make(std::numeric_limits<UK>::max());
+    auto minustwo = RCUPtr<E>::make(std::numeric_limits<UK>::max() - 1);
 
     // Insert them into the tree.
-    BOOST_CHECK(mytree.insert(&maxsigned));
-    BOOST_CHECK(mytree.insert(&minsigned));
-    BOOST_CHECK(mytree.insert(&minusone));
-    BOOST_CHECK(mytree.insert(&minustwo));
+    BOOST_CHECK(mytree.insert(maxsigned));
+    BOOST_CHECK(mytree.insert(minsigned));
+    BOOST_CHECK(mytree.insert(minusone));
+    BOOST_CHECK(mytree.insert(minustwo));
 
     // All elements are now in the tree.
-    BOOST_CHECK(!mytree.insert(&zero));
-    BOOST_CHECK(!mytree.insert(&one));
-    BOOST_CHECK(!mytree.insert(&two));
-    BOOST_CHECK(!mytree.insert(&three));
-    BOOST_CHECK(!mytree.insert(&maxsigned));
-    BOOST_CHECK(!mytree.insert(&minsigned));
-    BOOST_CHECK(!mytree.insert(&minusone));
-    BOOST_CHECK(!mytree.insert(&minustwo));
+    BOOST_CHECK(!mytree.insert(zero));
+    BOOST_CHECK(!mytree.insert(one));
+    BOOST_CHECK(!mytree.insert(two));
+    BOOST_CHECK(!mytree.insert(three));
+    BOOST_CHECK(!mytree.insert(maxsigned));
+    BOOST_CHECK(!mytree.insert(minsigned));
+    BOOST_CHECK(!mytree.insert(minusone));
+    BOOST_CHECK(!mytree.insert(minustwo));
 }
 
 BOOST_AUTO_TEST_CASE(insert_test) {
@@ -81,34 +83,34 @@
     typedef TestElement<K> E;
     RadixTree<E> mytree;
 
-    E zero(0);
-    E one(1);
-    E two(2);
-    E three(3);
+    auto zero = RCUPtr<E>::make(0);
+    auto one = RCUPtr<E>::make(1);
+    auto two = RCUPtr<E>::make(2);
+    auto three = RCUPtr<E>::make(3);
 
     // There are no elements in the tree so far.
     BOOST_CHECK_EQUAL(mytree.get(1), nullptr);
 
     // Insert an element into the tree and check it is there.
-    BOOST_CHECK(mytree.insert(&one));
-    BOOST_CHECK_EQUAL(mytree.get(1), &one);
+    BOOST_CHECK(mytree.insert(one));
+    BOOST_CHECK_EQUAL(mytree.get(1), one);
 
     // Let's insert more elements and check they are recovered properly.
     BOOST_CHECK_EQUAL(mytree.get(0), nullptr);
-    BOOST_CHECK(mytree.insert(&zero));
-    BOOST_CHECK_EQUAL(mytree.get(0), &zero);
-    BOOST_CHECK_EQUAL(mytree.get(1), &one);
+    BOOST_CHECK(mytree.insert(zero));
+    BOOST_CHECK_EQUAL(mytree.get(0), zero);
+    BOOST_CHECK_EQUAL(mytree.get(1), one);
 
     // More elements.
     BOOST_CHECK_EQUAL(mytree.get(2), nullptr);
     BOOST_CHECK_EQUAL(mytree.get(3), nullptr);
-    BOOST_CHECK(mytree.insert(&two));
-    BOOST_CHECK(mytree.insert(&three));
+    BOOST_CHECK(mytree.insert(two));
+    BOOST_CHECK(mytree.insert(three));
 
-    BOOST_CHECK_EQUAL(mytree.get(0), &zero);
-    BOOST_CHECK_EQUAL(mytree.get(1), &one);
-    BOOST_CHECK_EQUAL(mytree.get(2), &two);
-    BOOST_CHECK_EQUAL(mytree.get(3), &three);
+    BOOST_CHECK_EQUAL(mytree.get(0), zero);
+    BOOST_CHECK_EQUAL(mytree.get(1), one);
+    BOOST_CHECK_EQUAL(mytree.get(2), two);
+    BOOST_CHECK_EQUAL(mytree.get(3), three);
 
     // Check extreme values.
     typedef typename std::make_signed<K>::type SK;
@@ -117,10 +119,10 @@
     typedef typename std::make_unsigned<K>::type UK;
     K maxuk = std::numeric_limits<UK>::max();
 
-    E maxsigned(maxsk);
-    E minsigned(minsk);
-    E minusone(maxuk);
-    E minustwo(maxuk - 1);
+    auto maxsigned = RCUPtr<E>::make(maxsk);
+    auto minsigned = RCUPtr<E>::make(minsk);
+    auto minusone = RCUPtr<E>::make(maxuk);
+    auto minustwo = RCUPtr<E>::make(maxuk - 1);
 
     // Check that they are not in the tree.
     BOOST_CHECK_EQUAL(mytree.get(maxsk), nullptr);
@@ -129,20 +131,20 @@
     BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), nullptr);
 
     // Insert into the tree.
-    BOOST_CHECK(mytree.insert(&maxsigned));
-    BOOST_CHECK(mytree.insert(&minsigned));
-    BOOST_CHECK(mytree.insert(&minusone));
-    BOOST_CHECK(mytree.insert(&minustwo));
+    BOOST_CHECK(mytree.insert(maxsigned));
+    BOOST_CHECK(mytree.insert(minsigned));
+    BOOST_CHECK(mytree.insert(minusone));
+    BOOST_CHECK(mytree.insert(minustwo));
 
     // And now they all are in the tree.
-    BOOST_CHECK_EQUAL(mytree.get(0), &zero);
-    BOOST_CHECK_EQUAL(mytree.get(1), &one);
-    BOOST_CHECK_EQUAL(mytree.get(2), &two);
-    BOOST_CHECK_EQUAL(mytree.get(3), &three);
-    BOOST_CHECK_EQUAL(mytree.get(maxsk), &maxsigned);
-    BOOST_CHECK_EQUAL(mytree.get(minsk), &minsigned);
-    BOOST_CHECK_EQUAL(mytree.get(maxuk), &minusone);
-    BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), &minustwo);
+    BOOST_CHECK_EQUAL(mytree.get(0), zero);
+    BOOST_CHECK_EQUAL(mytree.get(1), one);
+    BOOST_CHECK_EQUAL(mytree.get(2), two);
+    BOOST_CHECK_EQUAL(mytree.get(3), three);
+    BOOST_CHECK_EQUAL(mytree.get(maxsk), maxsigned);
+    BOOST_CHECK_EQUAL(mytree.get(minsk), minsigned);
+    BOOST_CHECK_EQUAL(mytree.get(maxuk), minusone);
+    BOOST_CHECK_EQUAL(mytree.get(maxuk - 1), minustwo);
 }
 
 BOOST_AUTO_TEST_CASE(get_test) {
@@ -156,24 +158,24 @@
     typedef TestElement<K> E;
     RadixTree<E> mytree;
 
-    E zero(0);
-    E one(1);
-    E two(2);
-    E three(3);
+    auto zero = RCUPtr<E>::make(0);
+    auto one = RCUPtr<E>::make(1);
+    auto two = RCUPtr<E>::make(2);
+    auto three = RCUPtr<E>::make(3);
 
     // Removing an element that isn't in the tree returns false.
     BOOST_CHECK(!mytree.remove(1));
 
     // Insert an element into the tree and check you can remove it.
-    BOOST_CHECK(mytree.insert(&one));
+    BOOST_CHECK(mytree.insert(one));
     BOOST_CHECK(mytree.remove(1));
     BOOST_CHECK_EQUAL(mytree.get(1), nullptr);
 
     // Insert several elements and remove them.
-    BOOST_CHECK(mytree.insert(&zero));
-    BOOST_CHECK(mytree.insert(&one));
-    BOOST_CHECK(mytree.insert(&two));
-    BOOST_CHECK(mytree.insert(&three));
+    BOOST_CHECK(mytree.insert(zero));
+    BOOST_CHECK(mytree.insert(one));
+    BOOST_CHECK(mytree.insert(two));
+    BOOST_CHECK(mytree.insert(three));
 
     BOOST_CHECK(mytree.remove(0));
     BOOST_CHECK(mytree.remove(1));
@@ -198,20 +200,20 @@
     typedef typename std::make_unsigned<K>::type UK;
     K maxuk = std::numeric_limits<UK>::max();
 
-    E maxsigned(maxsk);
-    E minsigned(minsk);
-    E minusone(maxuk);
-    E minustwo(maxuk - 1);
+    auto maxsigned = RCUPtr<E>::make(maxsk);
+    auto minsigned = RCUPtr<E>::make(minsk);
+    auto minusone = RCUPtr<E>::make(maxuk);
+    auto minustwo = RCUPtr<E>::make(maxuk - 1);
 
     // Insert them all.
-    BOOST_CHECK(mytree.insert(&zero));
-    BOOST_CHECK(mytree.insert(&one));
-    BOOST_CHECK(mytree.insert(&two));
-    BOOST_CHECK(mytree.insert(&three));
-    BOOST_CHECK(mytree.insert(&maxsigned));
-    BOOST_CHECK(mytree.insert(&minsigned));
-    BOOST_CHECK(mytree.insert(&minusone));
-    BOOST_CHECK(mytree.insert(&minustwo));
+    BOOST_CHECK(mytree.insert(zero));
+    BOOST_CHECK(mytree.insert(one));
+    BOOST_CHECK(mytree.insert(two));
+    BOOST_CHECK(mytree.insert(three));
+    BOOST_CHECK(mytree.insert(maxsigned));
+    BOOST_CHECK(mytree.insert(minsigned));
+    BOOST_CHECK(mytree.insert(minusone));
+    BOOST_CHECK(mytree.insert(minustwo));
 
     // Delete them all
     BOOST_CHECK(mytree.remove(0));
@@ -240,6 +242,70 @@
     testRemove<uint64_t>();
 }
 
+BOOST_AUTO_TEST_CASE(const_element_test) {
+    typedef const TestElement<uint64_t> C;
+    RadixTree<C> mytree;
+
+    BOOST_CHECK(mytree.insert(RCUPtr<C>::make(0)));
+    BOOST_CHECK(mytree.insert(RCUPtr<C>::make(1)));
+    BOOST_CHECK(mytree.insert(RCUPtr<C>::make(2)));
+    BOOST_CHECK(mytree.insert(RCUPtr<C>::make(3)));
+
+    BOOST_CHECK(!mytree.insert(RCUPtr<C>::make(0)));
+    BOOST_CHECK(!mytree.insert(RCUPtr<C>::make(1)));
+    BOOST_CHECK(!mytree.insert(RCUPtr<C>::make(2)));
+    BOOST_CHECK(!mytree.insert(RCUPtr<C>::make(3)));
+
+    BOOST_CHECK(mytree.get(0));
+    BOOST_CHECK(mytree.get(1));
+    BOOST_CHECK(mytree.get(2));
+    BOOST_CHECK(mytree.get(3));
+
+    BOOST_CHECK(mytree.remove(0));
+    BOOST_CHECK(mytree.remove(1));
+    BOOST_CHECK(mytree.remove(2));
+    BOOST_CHECK(mytree.remove(3));
+
+    BOOST_CHECK(!mytree.get(0));
+    BOOST_CHECK(!mytree.get(1));
+    BOOST_CHECK(!mytree.get(2));
+    BOOST_CHECK(!mytree.get(3));
+
+    BOOST_CHECK(!mytree.remove(0));
+    BOOST_CHECK(!mytree.remove(1));
+    BOOST_CHECK(!mytree.remove(2));
+    BOOST_CHECK(!mytree.remove(3));
+}
+
+void CheckConstTree(const RadixTree<TestElement<uint64_t>> &mytree,
+                    bool expected) {
+    BOOST_CHECK_EQUAL(!!mytree.get(0), expected);
+    BOOST_CHECK_EQUAL(!!mytree.get(1), expected);
+    BOOST_CHECK_EQUAL(!!mytree.get(2), expected);
+    BOOST_CHECK_EQUAL(!!mytree.get(3), expected);
+}
+
+BOOST_AUTO_TEST_CASE(const_tree_test) {
+    typedef TestElement<uint64_t> E;
+    RadixTree<E> mytree;
+
+    CheckConstTree(mytree, false);
+
+    BOOST_CHECK(mytree.insert(RCUPtr<E>::make(0)));
+    BOOST_CHECK(mytree.insert(RCUPtr<E>::make(1)));
+    BOOST_CHECK(mytree.insert(RCUPtr<E>::make(2)));
+    BOOST_CHECK(mytree.insert(RCUPtr<E>::make(3)));
+
+    CheckConstTree(mytree, true);
+
+    BOOST_CHECK(mytree.remove(0));
+    BOOST_CHECK(mytree.remove(1));
+    BOOST_CHECK(mytree.remove(2));
+    BOOST_CHECK(mytree.remove(3));
+
+    CheckConstTree(mytree, false);
+}
+
 #define THREADS 128
 #define ELEMENTS 65536
 
@@ -267,20 +333,19 @@
                     std::this_thread::yield();
                 }
 
-                std::unique_ptr<E> ptr = MakeUnique<E>(v);
-                if (mytree.insert(ptr.get())) {
+                auto ptr = RCUPtr<E>::make(v);
+                if (mytree.insert(ptr)) {
                     success++;
                     std::this_thread::yield();
                 }
 
                 if (mytree.remove(v)) {
                     success--;
-                    RCULock::synchronize();
+                    std::this_thread::yield();
                 }
 
-                if (mytree.insert(ptr.get())) {
+                if (mytree.insert(ptr)) {
                     success++;
-                    ptr.release();
                     std::this_thread::yield();
                 }
             }
@@ -300,10 +365,13 @@
         rand = next(rand);
         uint32_t v(rand >> 32);
         BOOST_CHECK_EQUAL(mytree.get(v)->getId(), v);
-        E e(v);
-        BOOST_CHECK(!mytree.insert(&e));
-        BOOST_CHECK(mytree.get(v) != &e);
+        auto ptr = RCUPtr<E>::make(v);
+        BOOST_CHECK(!mytree.insert(ptr));
+        BOOST_CHECK(mytree.get(v) != ptr);
     }
+
+    // Cleanup after ourselves.
+    RCULock::synchronize();
 }
 
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/test/rcu_tests.cpp b/src/test/rcu_tests.cpp
--- a/src/test/rcu_tests.cpp
+++ b/src/test/rcu_tests.cpp
@@ -135,6 +135,7 @@
 }
 
 BOOST_AUTO_TEST_CASE(cleanup_test) {
+    RCULock::synchronize();
     BOOST_CHECK(RCUTest::getCleanups().empty());
 
     bool isClean1 = false;