2
\$\begingroup\$

I know B-Trees are meant to be used for external memory, but I implement it to understand the algorithms involved in insertion and deletion. Also, I didn't use a vector because I was asked not to use it (I will probably reimplement this using vectors later).

namespace mds {
    template<typename T, typename Func = std::less<T>>
    class b_tree {

        struct BNode {
            unsigned size;
            bool leaf;
            T *keys;
            BNode** childs;


            BNode(bool is_leaf, unsigned degree)
                : size(0),
                leaf(is_leaf),
                keys(new T[2 * degree - 1]),
                childs(leaf ? nullptr : new BNode*[2 * degree]) { }
            ~BNode() {
                delete[] keys;
                delete[] childs;
            }

        };

        unsigned size;
        unsigned inner_degree;
        unsigned leaf_degree;
        BNode    *root;
        Func     cmp;

        template<typename Func>
        void in_order_recursive(const BNode *node, const Func& func) const {

            auto size   = node->size;
            auto keys   = node->keys;
            auto childs = node->childs;

            if (node->leaf) {
                std::for_each(keys, keys + size, func);
            }
            else {
                for (unsigned i = 0; i < node->size; ++i) {
                    in_order_recursive(childs[i], func);
                    func(keys[i]);
                }
                in_order_recursive(childs[node->size], func);
            }
        }

        void remove(BNode* node, const T& key) {

            auto n = node;
            while (!n->leaf) {
                auto i = search_index(n, key);
                if (equal(n, i, key)) {
                    return delete_internal(n, i);
                }
                auto child = n->childs[i];
                auto deg   = degree(child);
                if (child->size < deg) {
                    i = fill(n, i, deg);
                }
                n = n->childs[i];
            }
            auto i = search_index(n, key);
            if (equal(n, i, key)) {
                node_remove(n, i);
                --n->size;
                --size;
            }
        }

        void take_from_rigth(BNode *n, unsigned index) {
            auto left  = n->childs[index];
            auto rigth = n->childs[index + 1];

            left->keys[left->size] = std::move(n->keys[index]);
            n->keys[index]         = std::move(node_remove(rigth, 0));

            if (!left->leaf) {
                left->childs[left->size + 1] = rigth->childs[0];
                for (auto i = 0; i < rigth->size; ++i) {
                    rigth->childs[i] = rigth->childs[i + 1];
                }
            }
            ++left->size;
            --rigth->size;
        }

        void take_from_left(BNode *n, unsigned index) {
            auto left  = n->childs[index - 1];
            auto rigth = n->childs[index];

            node_insert_index(rigth, 0, std::move(n->keys[index - 1]));
            n->keys[index - 1] = std::move(left->keys[left->size - 1]);

            if (!rigth->leaf) {
                auto childs = rigth->childs;
                for (auto i = rigth->size + 1; i --> 0; ) {
                    childs[i + 1] = childs[i];
                }
                childs[0] = left->childs[left->size];
            }
            --left->size;
            ++rigth->size;
        }


        void split_child(BNode *n, unsigned index) {
            auto splited    = n->childs[index];
            auto deg        = degree(splited);
            auto new_child  = new BNode(splited->leaf, deg);
            new_child->size = deg - 1;
            splited->size   = deg - 1;

            for (unsigned i = 0, to = deg - 1; i < to; ++i) {
                new_child->keys[i] = std::move(splited->keys[i + deg]);
            }
            if (!splited->leaf) {
                for (unsigned i = 0; i < deg; ++i) {
                    new_child->childs[i] = splited->childs[i + deg];
                }
            }

            for (unsigned i = n->size; i > index; --i) {
                n->childs[i + 1] = n->childs[i];
            }
            n->childs[index + 1] = new_child;
            node_insert_index(n, index, std::move(splited->keys[deg - 1]));
            ++n->size;
        }

        template<typename TT>
        void node_insert_index(BNode *n, unsigned index, TT&& key) {
            auto i    = n->size;
            auto keys = n->keys;
            while (i --> index) {
                keys[i + 1] = std::move(keys[i]);
            }
            keys[index] = std::forward<TT>(key);
        }

        std::pair<BNode*, unsigned> search(BNode* n, const T& key) const {
            auto i = search_index(n, key);
            while (!equal(n, i, key)) {
                if (n->leaf) {
                    return std::make_pair(nullptr, 0);
                }
                n = n->childs[i];
                i = search_index(n, key);
            }
            return std::make_pair(n, i);
        }

        bool equal(const BNode *n, unsigned index, const T& key) const {
            return index < n->size
                && !cmp(n->keys[index], key)
                && !cmp(key, n->keys[index]);
        }

        unsigned search_index(const BNode* n, const T& key) const {
            int begin = 0;
            int end   = n->size - 1;
            auto keys = n->keys;

            while (begin <= end) {
                unsigned mid = begin + (end - begin) / 2;
                if (cmp(keys[mid], key)) {
                    begin = mid + 1;
                }
                else if (cmp(key, keys[mid])) {
                    end = mid - 1;
                }
                else {
                    return mid;
                }
            }
            return begin;
        }

        bool full(const BNode *n) const {
            return n->size == (2 * degree(n) - 1);
        }

        template<typename TT>
        bool node_insert(BNode *n, TT&& key) {
            auto bound     = search_index(n, key);
            bool not_found = !equal(n, bound, key);

            if (not_found) {
                node_insert_index(n, bound,
                    std::forward<TT>(key));
                ++n->size;
                ++size;
            }
            return not_found;
        }


        unsigned degree(const BNode* n) const {
            return n->leaf ? leaf_degree : inner_degree;
        }

        unsigned fill(BNode *n, unsigned index, unsigned deg) {
            auto childs = n->childs;
            if (index != n->size
                && deg <= childs[index + 1]->size) {
                take_from_rigth(n, index);
            }
            else if (index != 0
                && deg <= childs[index - 1]->size) {
                take_from_left(n, index);
            }
            else {
                if (index == n->size) {
                    --index;
                }
                merge(n, index);
            }
            return index;
        }

        void destroy_tree(BNode *n) {
            if (!n->leaf) {
                for (auto i = 0u; i <= n->size; ++i) {
                    destroy_tree(n->childs[i]);
                }
            }
            delete n;
        }

        template<typename TT>
        bool insert_generic(TT&& key) {
            if (full(root)) {
                auto child      = root;
                root            = new BNode(false, inner_degree);
                root->childs[0] = child;
                split_child(root, 0);
            }
            auto n = root;
            while (!n->leaf) {
                auto index = search_index(n, key);
                bool found = equal(n, index, key);

                if (full(n->childs[index])) {
                    split_child(n, index);
                    found  = found || equal(n, index, key);
                    index += cmp(n->keys[index], key);
                }
                if (found) {
                    return false;
                }
                n = n->childs[index];
            }
            return node_insert(n, std::forward<TT>(key));
        }

        const T& max(BNode* n) const {
            while (!n->leaf) {
                n = n->childs[n->size];
            }
            return n->keys[n->size - 1];
        }

        const T& min(BNode* n) const {
            while (!n->leaf) {
                n = n->childs[0];
            }
            return n->keys[0];
        }

        void delete_internal(BNode *n, unsigned index) {
            auto left  = n->childs[index];
            auto rigth = n->childs[index + 1];
            auto deg   = degree(left);

            if (left->size >= deg) {
                n->keys[index] = max(left);
                remove(left, n->keys[index]);
            }
            else if (rigth->size >= deg) {
                n->keys[index] = min(rigth);
                remove(rigth, n->keys[index]);
            }
            else {
                merge(n, index);
                remove(left, left->keys[deg - 1]);
            }
        }

        T node_remove(BNode* n, unsigned i) {
            T k = std::move(n->keys[i]);
            for (auto to = n->size - 1; i < to; ++i) {
                n->keys[i] = std::move(n->keys[i + 1]);
            }
            return k;
        }

        void merge(BNode *n, unsigned index) {
            auto left  = n->childs[index];
            auto rigth = n->childs[index + 1];
            auto deg   = degree(left);

            left->keys[deg - 1] = std::move(node_remove(n, index));
            for (auto i = index + 1; i < n->size; ++i) {
                n->childs[i] = n->childs[i + 1];
            }

            if (!rigth->leaf) {
                for (auto i = 0; i <= rigth->size; ++i) {
                    left->childs[i + deg] = rigth->childs[i];
                }
            }
            for (auto i = 0; i < rigth->size; ++i) {
                left->keys[i + deg] = std::move(rigth->keys[i]);
            }
            --n->size;
            left->size += rigth->size + 1;
            delete rigth;
        }


    public:

        b_tree(unsigned pleaf_degree, unsigned pinner_degree, Func pcmp)
            : leaf_degree(pleaf_degree),
            inner_degree(pinner_degree),
            root(new BNode(true, leaf_degree)),
            cmp(pcmp),
            size(0) { }

        b_tree(unsigned pleaf_degree, unsigned pinner_degree)
            : b_tree(pleaf_degree, pinner_degree, Func()) { }

        b_tree(unsigned min_degree)
            : b_tree((3 * min_degree) / 2, min_degree) { }

        ~b_tree() {
            destroy_tree(root);
        }

        void remove(const T& key) {
            remove(root, key);
            if (root->size == 0 && !root->leaf) {
                auto tmp = root;
                root     = root->childs[0];
                delete tmp;
            }
        }

        unsigned len() const {
            return size;
        }

        bool insert(T&& key) {
            return insert_generic(std::move(key));
        }

        bool contains(const T& key) {
            return search(root, key).first != nullptr;
        }

        bool insert(const T& key) {
            return insert_generic(key);
        }

        template<typename Func>
        void in_order_walk(const Func& func) const {
            in_order_recursive(root, func);
        }

        bool empty() {
            return size == 0;
        }
    };
}
\$\endgroup\$
  • \$\begingroup\$ Do you have any performance figures? Do you know how this compares to std::set? \$\endgroup\$ – coderodde Jul 3 '16 at 12:52
  • \$\begingroup\$ Not yet, but I plan to do some benchmarks later. \$\endgroup\$ – MAG Jul 3 '16 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.