Data Structures with Generic Types in C++/

...

/

Solution: Scapegoat Trees

Solution: Scapegoat Trees

See the solution of the modified add() method of the scapegoat tree.

We'll cover the following...

Task

Here is the task that modifies the add(x) method of the ScapegoatTree so that it does not waste any time recomputing the sizes of subtrees that have already been computed. This is possible because, by the time the method wants to compute size(w), it has already computed one of size(w.left) or size(w.right).

Solution

We have implemented the code that modifies the add() method of the ScapegoatTree. The add() method inserts a new element x into the ScapegoatTree and rebalances the tree if the depth exceeds a certain threshold.

Press + to interact
ScapegoatTree.h
utils.h
main.cpp
array.h
ArrayDeque.h
BinaryTree.h
BinarySearchTree.h
#ifndef SCAPEGOATTREE_H_
#define SCAPEGOATTREE_H_
#include <cmath>
#include "BinarySearchTree.h"
namespace ods {
    template <class Node, class T>
    class ScapegoatTree : public BinarySearchTree<Node, T> {
    public:
        using BinaryTree<Node>::r;
    protected:
        using BinaryTree<Node>::nil;
        using BinarySearchTree<Node, T>::n;
        int q;
        static int log32(int q);
        int addWithDepth(Node* u);
        void rebuild(Node* u);
        int packIntoArray(Node* u, Node** a, int i);
        Node* buildBalanced(Node** a, int i, int ns);
    public:
        ScapegoatTree();
        virtual ~ScapegoatTree();
        virtual bool add(T x);
        virtual bool remove(T x);
    };
    template <class T>
    class ScapegoatTree1 : public ScapegoatTree<BSTNode1<T>, T> {};
    template <class Node, class T>
    inline int ScapegoatTree<Node, T>::log32(int q) {
        static double log23 = 2.4663034623764317;
        return (int)ceil(log23 * log(q));
    }
    template <class Node, class T>
    inline int ScapegoatTree<Node, T>::addWithDepth(Node* u) {
        Node* w = r;
        if (w == nil) {
            r = u;
            n++;
            q++;
            return 0;
        }
        bool done = false;
        int d = 0;
        do {
            int res = compare(u->x, w->x);
            if (res < 0) {
                if (w->left == nil) {
                    w->left = u;
                    u->parent = w;
                    done = true;
                }
                else {
                    w = w->left;
                }
            }
            else if (res > 0) {
                if (w->right == nil) {
                    w->right = u;
                    u->parent = w;
                    done = true;
                }
                w = w->right;
            }
            else {
                return -1;
            }
            d++;
        } while (!done);
        n++;
        q++;
        return d;
    }
    template <class Node, class T>
    inline void ScapegoatTree<Node, T>::rebuild(Node* u) {
        int ns = BinaryTree<Node>::size(u);
        Node* p = u->parent;
        Node** a = new Node*[ns];
        packIntoArray(u, a, 0);
        if (p == nil) {
            r = buildBalanced(a, 0, ns);
            r->parent = nil;
        }
        else if (p->right == u) {
            p->right = buildBalanced(a, 0, ns);
            p->right->parent = p;
        }
        else {
            p->left = buildBalanced(a, 0, ns);
            p->left->parent = p;
        }
        delete[] a;
    }
    template <class Node, class T>
    inline int ScapegoatTree<Node, T>::packIntoArray(Node* u, Node** a, int i) {
        if (u == nil) {
            return i;
        }
        i = packIntoArray(u->left, a, i);
        a[i++] = u;
        return packIntoArray(u->right, a, i);
    }
    template <class Node, class T>
    inline Node* ScapegoatTree<Node, T>::buildBalanced(Node** a, int i, int ns) {
        if (ns == 0) {
            return nil;
        }
        int m = ns / 2;
        a[i + m]->left = buildBalanced(a, i, m);
        if (a[i + m]->left != nil)
            a[i + m]->left->parent = a[i + m];
        a[i + m]->right = buildBalanced(a, i + m + 1, ns - m - 1);
        if (a[i + m]->right != nil)
            a[i + m]->right->parent = a[i + m];
        return a[i + m];
    }
    template <class Node, class T>
    inline ScapegoatTree<Node, T>::ScapegoatTree() : BinarySearchTree<Node, T>(), q(0) {
        // Constructor implementation
    }
    template <class Node, class T>
    inline ScapegoatTree<Node, T>::~ScapegoatTree() {
        // Destructor implementation
    }
    template <class Node, class T>
inline bool ScapegoatTree<Node, T>::add(T x) {
    Node* u = new Node;
    u->x = x;
    u->left = u->right = u->parent = nil;
    int d = addWithDepth(u);
    if (d > log32(q)) {
        Node* w = u->parent;
        int a, b;
        if (w->left == u) {
            a = d - 1; // Size of the left subtree of w has already been computed as d - 1
            b = BinaryTree<Node>::size(w) - a - 1; // Compute the size of the right subtree
        } else {
            b = d - 1; // Size of the right subtree of w has already been computed as d - 1
            a = BinaryTree<Node>::size(w) - b - 1; // Compute the size of the left subtree
        }
        while (3 * a <= 2 * b) {
            w = w->parent;
            a = BinaryTree<Node>::size(w->left);
            b = BinaryTree<Node>::size(w->right);
        }
        rebuild(w->parent);
    }
    return d >= 0;
}
    template <class Node, class T>
    inline bool ScapegoatTree<Node, T>::remove(T x) {
        if (BinarySearchTree<Node, T>::remove(x)) {
            if (2 * n < q) {
                rebuild(r);
                q = n;
            }
            return true;
        }
        return false;
    }
} /* namespace ods */
#endif /* SCAPEGOATTREE_H_ */

Explanation

Let’s focus on the detailed explanation for the add(T x) ...