AVL Tree Implementation with 3+4 Reshaping

avl.cc

#include <iostream>
#include <vector>
#include <utility>
#include <string>

#ifdef _NDEBUG
#   define DDD(X...)
#else
#   define DDD(X...) X
#endif

template <class T>
struct NewAllocator
{
    template <class U>
    using rebind = NewAllocator<U>;

    using value_type = T;
    using pointer = value_type*;

    template <class ...Ts>
    pointer alloc(Ts &&... args)
    {
        return new T{std::forward<Ts>(args)...};
    }
};

template <class T, class Allocator=NewAllocator<void>>
struct AvlTree
{
    using value_type = T;
    using depth_type = int;
    using depth_diff = depth_type;

    struct Node;
    using allocator = typename Allocator::template rebind<Node>;
    using node_pointer = typename allocator::pointer;
    using node_type = typename allocator::value_type;

    struct Node
    {
        Node(value_type value)
            : value{std::move(value)}
            , depth{1}
            , childs{}
        {}

        value_type value;
        depth_type depth;
        node_pointer childs[2];
    };

    void insert(value_type value)
    {
        auto node = ator.alloc(std::move(value));
        insert(root, node);
    }

    void inspect()
    {
        print(root, 0);
    }

    value_type & root_value() const
    {
        return root->value;
    }

private:
    allocator ator;
    node_pointer root{};

    static void insert(node_pointer & root, node_pointer const& node)
    {
        if (root) {
            auto cs = root->childs;
            auto& child = (node->value < root->value ? cs[0] : cs[1]);
            insert(child, node);
            update_depth(root);
            if (std::abs(balance_factor(root)) == 2) rebalance(root);
        } else {
            root = node;
        }
    }

    static void update_depth(node_pointer & root)
    {
        auto cs = root->childs;
        root->depth = std::max(depth_of(cs[0]), depth_of(cs[1])) + 1;
    }

    static depth_type depth_of(node_pointer const& root)
    {
        return (root ? root->depth : depth_type{});
    }

    static depth_diff balance_factor(node_pointer const& root)
    {
        auto cs = root->childs;
        return depth_of(cs[0]) - depth_of(cs[1]);
    }

    static void rebalance(node_pointer & root)
    {
        DDD(std::cerr << "Unbalanced\n");
        DDD(print(root, 2));

        switch (balance_factor(root)) {
            case +2: {
                auto& z = root;
                auto& child = z->childs[0];
                switch (balance_factor(child)) {
                    case +1: {
                        auto& y = child;
                        auto& x = y->childs[0];
                        auto& a = x->childs[0];
                        auto& b = x->childs[1];
                        auto& c = y->childs[1];
                        auto& d = z->childs[1];
                        root = reshape(x, y, z, a, b, c, d);
                    } break;
                    case -1: {
                        auto& x = child;
                        auto& y = x->childs[1];
                        auto& a = x->childs[0];
                        auto& b = y->childs[0];
                        auto& c = y->childs[1];
                        auto& d = z->childs[1];
                        root = reshape(x, y, z, a, b, c, d);
                    } break;
                    default: std::abort();
                }
            } break;
            case -2: {
                auto& x = root;
                auto& child = x->childs[1];
                switch (balance_factor(child)) {
                    case +1: {
                        auto& z = child;
                        auto& y = z->childs[0];
                        auto& a = x->childs[0];
                        auto& b = y->childs[0];
                        auto& c = y->childs[1];
                        auto& d = z->childs[1];
                        root = reshape(x, y, z, a, b, c, d);
                    } break;
                    case -1: {
                        auto& y = child;
                        auto& z = y->childs[1];
                        auto& a = x->childs[0];
                        auto& d = y->childs[0];
                        auto& b = z->childs[0];
                        auto& c = z->childs[1];
                        root = reshape(x, y, z, a, b, c, d);
                    } break;
                    default: std::abort();
                }
            } break;
            default: std::abort();
        }

        DDD(std::cerr << "Balanced\n");
        DDD(print(root, 2));
        DDD(std::cerr << "\n");
    }

    static node_pointer reshape(
            node_pointer x,
            node_pointer y,
            node_pointer z,
            node_pointer a,
            node_pointer b,
            node_pointer c,
            node_pointer d)
    {
        x->childs[0] = a;
        x->childs[1] = b;
        update_depth(x);

        z->childs[0] = c;
        z->childs[1] = d;
        update_depth(z);

        y->childs[0] = x;
        y->childs[1] = z;
        update_depth(y);

        return y;
    }

    static void print(node_pointer const& root, int indent)
    {
        if (root) {
            std::cerr << std::string(indent, ' ') << root->value << " (" << root->depth << "|" << balance_factor(root) << ")\n";
            auto shift = std::to_string(root->value).size() + 1;
            print(root->childs[0], indent+shift);
            print(root->childs[1], indent+shift);
        } else {
            std::cerr << std::string(indent, ' ') << "* (0|0)\n";
        }
    }
};

int main()
{
    int n;
    std::cin >> n;

    AvlTree<int> tree;
    while (n--) {
        int x;
        std::cin >> x;
        tree.insert(x);
    }
    DDD(tree.inspect());

    std::cout << tree.root_value() << '\n';
}