# 12728 - Container Tree

> author: IntSys
###### tags: `BST` `iterator` `container`

---

## Brief

:::spoiler **Class Definitions**

#include <cstdint>


namespace oj {
    using size_type = uint64_t;
    using value_type = int32_t;
    using reference = value_type&;

    struct Node {
        size_type size;
        value_type* p_data;
        Node* lc;
        Node* rc;
        Node(value_type* pv) : size(1), p_data(pv), lc(nullptr), rc(nullptr) {}
        ~Node() { delete p_data; }
    };

    struct iterator_impl_base {
        virtual reference operator*() const = 0;
        virtual bool operator!=(const iterator_impl_base&) const = 0;
        virtual iterator_impl_base* clone() const = 0;
    };

    class set_iterator : public iterator_impl_base {
    protected:
        Node* _node;
    public:
        set_iterator();
        set_iterator(Node* u);
        reference operator*() const;
        iterator_impl_base* clone() const;
        bool operator!=(const iterator_impl_base&) const;
    };

    class iterator {
    protected:
        iterator_impl_base* _p;
    public:
        iterator(iterator_impl_base*);
        reference operator*() const;
        bool operator!=(const iterator&) const;
    };

    struct container_base {
        virtual size_type size() const = 0;
        virtual bool empty() const = 0;
        virtual void clear() = 0;
    };

    struct dynamic_size_container : container_base {
        virtual iterator begin() = 0;
        virtual iterator end() = 0;
    };

    struct associative_container : dynamic_size_container {
        virtual void insert(const value_type&) = 0;
    };

    struct sorted_container : associative_container {
        virtual iterator lower_bound(const value_type&) = 0;
    };

    class set : public sorted_container {
    protected: // you have two pointers to spare :) do anything you wish
        Node* root;
        Node* infy;
    public:
        set();
        ~set();
        void clear();
        size_type size() const;
        bool empty() const;
        iterator begin();
        iterator end();
        void insert(const value_type&);
        iterator lower_bound(const value_type&);
    };
};

:::

## Solution 0

#include <cstdint>

#include "function.h"

#define INF INT32_MAX

namespace oj {
    using size_type = uint64_t;
    using value_type = int32_t;
    using reference = value_type&;
    using const_reference = value_type const&;

    set_iterator::set_iterator() : _node(nullptr) {}

    set_iterator::set_iterator(Node* u) : _node(u) {}

    reference set_iterator::operator*() const { return *_node->p_data; }

    iterator_impl_base* set_iterator::clone() const { return new set_iterator(_node); }

    bool set_iterator::operator!=(const iterator_impl_base& rhs) const {
        return operator*() != *rhs;
    }

    iterator::iterator(iterator_impl_base* p) : _p(p->clone()) {}

    reference iterator::operator*() const { return **_p; }

    bool iterator::operator!=(const iterator& rhs) const {
        return *_p != *rhs._p;
    }


    size_type size_of_tree(Node* root);
    void delete_tree(Node* root);
    void insert_node(Node*& root, const_reference c_val);
    Node* search_least_upper(Node* root, Node* upper, const_reference key);

    // Return the number of nodes in a tree.
    size_type size_of_tree(Node* root) {
        if (root == nullptr) return 0;
        return size_of_tree(root->lc) + 1 + size_of_tree(root->rc);
    }

    // Delete a tree.
    void delete_tree(Node* root) {
        if (root != nullptr) {
            delete_tree(root->lc);
            delete_tree(root->rc);
            delete root;
        }
    }

    // Regular insertion.
    void insert_node(Node*& root, const_reference c_val) {
        if (root == nullptr) root = new Node(new value_type(c_val));
        else if (*root->p_data == c_val) return;
        else if (*root->p_data < c_val) return insert_node(root->rc, c_val);
        else return insert_node(root->lc, c_val);
    }

    // Assumes a non-empty set.
    Node* search_least_upper(Node* root, Node* upper, const_reference key) {
        if (*root->p_data == key) return root;
        if (*root->p_data < key) {
            if (root->rc == nullptr) return upper;
            else return search_least_upper(root->rc, upper, key);
        }
        if (root->lc == nullptr) return (*root->p_data >= key) ? root : upper;
        else return search_least_upper(root->lc, root, key);
    }

    set::set() : root(nullptr), infy(new Node(new value_type(INF))) {}

    set::~set() {
        clear();
        delete infy;
    }

    void set::clear() {
        delete_tree(root);
        root = nullptr;
    }

    size_type set::size() const {
        return empty() ? 0 : size_of_tree(root);
    }

    bool set::empty() const {
        return root == nullptr;
    }

    iterator set::begin() {
        set_iterator root_ptr(root);
        return iterator(&root_ptr);
    }

    iterator set::end() {
        set_iterator infy_ptr(infy);
        return iterator(&infy_ptr);
    }

    void set::insert(const_reference key) {
        insert_node(root, key);
    }

    iterator set::lower_bound(const_reference key) {
        set_iterator bound_ptr(search_least_upper(root, infy, key));
        return iterator(&bound_ptr);
    }

};

// By IntSys

## Solution 1 ([Scapegoat Tree](https://en.wikipedia.org/wiki/Scapegoat_tree))

#include <cstdint>
#include <cmath>

#include "function.h"

#define INF INT32_MAX

#define ALPHA 0.85

// Note: 0.5 < ALPHA < 1.0
// High ALPHA makes insertions quicker.
// Low ALPHA makes lookups and deletions quicker.

// Here, lower_bound() is a kind of lookup.

namespace oj {
    using size_type = uint64_t;
    using value_type = int32_t;
    using reference = value_type&;
    using const_reference = value_type const&;

    set_iterator::set_iterator() : _node(nullptr) {}

    set_iterator::set_iterator(Node* u) : _node(u) {}

    reference set_iterator::operator*() const { return *_node->p_data; }

    iterator_impl_base* set_iterator::clone() const { return new set_iterator(_node); }

    bool set_iterator::operator!=(const iterator_impl_base& rhs) const {
        return operator*() != *rhs;
    }

    iterator::iterator(iterator_impl_base* p) : _p(p->clone()) {}

    reference iterator::operator*() const { return **_p; }

    bool iterator::operator!=(const iterator& rhs) const {
        return *_p != *rhs._p;
    }


    size_type size_of_tree(Node* root);
    void delete_tree(Node* root);
    void insert_node(Node*& root, const_reference c_val);
    bool scapegoat_insert(Node*& root, Node** path[], const_reference c_val, reference depth);
    Node* get_scapegoat(Node** path[], reference depth, size_type current_size);
    void BST_to_sorted_array(Node* root, value_type arr[], reference top);
    void sorted_array_to_balanced_BST(Node*& root, value_type arr[], value_type L, value_type R);
    Node* search_least_upper(Node* root, Node* upper, const_reference key);

    // Return the number of nodes in a tree.
    size_type size_of_tree(Node* root) {
        if (root == nullptr) return 0;
        return size_of_tree(root->lc) + 1 + size_of_tree(root->rc);
    }

    // Delete a tree.
    void delete_tree(Node* root) {
        if (root != nullptr) {
            delete_tree(root->lc);
            delete_tree(root->rc);
            delete root;
        }
    }

    // Regular insertion.
    void insert_node(Node*& root, const_reference c_val) {
        if (root == nullptr) root = new Node(new value_type(c_val));
        else if (*root->p_data == c_val) return;
        else if (*root->p_data < c_val) return insert_node(root->rc, c_val);
        else return insert_node(root->lc, c_val);
    }

    // Insertion that records the path taken and the depth reached. Returns true upon success.
    bool scapegoat_insert(Node*& root, Node** path[], const_reference c_val, reference depth) {
        path[depth++] = &root;
        if (root == nullptr) {
            root = new Node(new value_type(c_val));
            return true;
        }
        if (*root->p_data == c_val) return false;
        if (*root->p_data < c_val) return scapegoat_insert(root->rc, path, c_val, depth);
        return scapegoat_insert(root->lc, path, c_val, depth);
    }

    // Find the deepest scapegoat node in the tree by traveling back up the path given.
    Node* get_scapegoat(Node** path[], reference depth, size_type current_size) {
        if (--depth < 0) return nullptr;
        Node*& parent = *path[depth - 1];
        Node* sibling = (parent->lc == *path[depth]) ? parent->rc : parent->lc;
        size_type sibling_size = size_of_tree(sibling);
        size_type parent_size = sibling_size + current_size + 1;
        if (current_size > ALPHA * parent_size || sibling_size > ALPHA * parent_size) return parent;
        current_size = parent_size;
        return get_scapegoat(path, depth, current_size);
    }

    // Move the data in a BST into the given array with inorder traversal, and delete the tree.
    void BST_to_sorted_array(Node* root, value_type arr[], reference top) {
        if (root != nullptr) {
            BST_to_sorted_array(root->lc, arr, top);
            arr[top++] = *root->p_data;
            BST_to_sorted_array(root->rc, arr, top);
            delete root;
        }
    }

    // Insert the data in a sorted array into a tree while making the new tree balanced.
    void sorted_array_to_balanced_BST(Node*& root, value_type arr[], value_type L, value_type R) {
        if (R - L == 1) return;
        value_type mid = (L + R) / 2;
        insert_node(root, arr[mid]);
        sorted_array_to_balanced_BST(root, arr, L, mid);
        sorted_array_to_balanced_BST(root, arr, mid, R);
    }

    // Assumes a non-empty set.
    Node* search_least_upper(Node* root, Node* upper, const_reference key) {
        if (*root->p_data == key) return root;
        if (*root->p_data < key) {
            if (root->rc == nullptr) return upper;
            else return search_least_upper(root->rc, upper, key);
        }
        if (root->lc == nullptr) return (*root->p_data >= key) ? root : upper;
        else return search_least_upper(root->lc, root, key);
    }

    set::set() : root(nullptr), infy(new Node(new value_type(INF))) {}

    set::~set() {
        clear();
        delete infy;
    }

    void set::clear() {
        delete_tree(root);
        root = nullptr;
    }

    size_type set::size() const {
        return empty() ? 0 : root->size;
    }

    bool set::empty() const {
        return root == nullptr;
    }

    iterator set::begin() {
        set_iterator root_ptr(root);
        return iterator(&root_ptr);
    }

    iterator set::end() {
        set_iterator infy_ptr(infy);
        return iterator(&infy_ptr);
    }

    void set::insert(const_reference key) {
        value_type depth = 0;
        Node** path[100];
        if (scapegoat_insert(root, path, key, depth)) root->size++;
        if (depth > floor(log2(root->size) / log2(1 / ALPHA) + 1)) {
            Node* scapegoat = get_scapegoat(path, depth, 1);
            Node*& scapegoat_parent = (depth > 2) ? *path[depth - 2] : root;
            if (scapegoat_parent->lc == *path[depth - 1]) scapegoat_parent->lc = nullptr;
            else scapegoat_parent->rc = nullptr;
            value_type val_arr[100];
            value_type top = 0;
            BST_to_sorted_array(scapegoat, val_arr, top);
            sorted_array_to_balanced_BST(scapegoat_parent, val_arr, -1, top);
        }
    }

    iterator set::lower_bound(const_reference key) {
        set_iterator bound_ptr(search_least_upper(root, infy, key));
        return iterator(&bound_ptr);
    }

};



// By IntSys

## Reference