Gain insights into array and linked list-based implementations, delve into advanced structures like skiplists and trees, and explore template-based collections for efficient data optimization and retrieval.

java.tar.gz

Data structures and algorithms are essential in computer science since they play a crucial role in efficient information retrieval and processing, dealing with files, storing contacts on phones, social networks and web searches.

In this course, you’ll learn about the array-based implementation of various linear data structures, stack, and queues. You’ll also learn about linked list-based implementation. Next, you’ll explore advanced data structures like skiplists and hashing. You’ll learn how to implement a variety of trees and graphs, and data structures related to bits of an integer. Toward the end of the course, you’ll learn the implementation of structures based on external storage.

After completing this course, you’ll be able to create reusable programs with template-based collections that can efficiently analyze how to optimize the storage and retrieval of very large amounts of data. Overall, this course will enhance your productivity and performance as a software developer.

Data Structures with Generic Types in C++

## 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.

#ifndef UTILS_H_
#define UTILS_H_

namespace ods {

    template < class T > inline
    T min(T a, T b) {
        return ((a) < (b) ? (a) : (b));
    }

    template < class T > inline
    T max(T a, T b) {
        return ((a) > (b) ? (a) : (b));
    }

    template < class T > inline
    int compare(T & x, T & y) {
        if (x < y) return -1;
        if (y < x) return 1;
        return 0;
    }

    template < class T > inline
    bool equals(T & x, T & y) {
        return x == y;
    }

    inline
    unsigned intValue(int x) {
        return (unsigned) x;
    }

    /**
     * This is terrible - don't use it
     */
    int hashCode(int x);

    template < class T > class XFastTrieNode1;

    template < class T >
        unsigned hashCode(const XFastTrieNode1 < T > * u) {
            return u -> prefix;
        }

    class dodo {
        public: bool operator < (dodo & d) {
            return this < & d;
        }
    };

} /* namespace ods */

#endif /* UTILS_H_ */

#include <iostream>
#include "ScapegoatTree.h"

using namespace std;
using namespace ods;

// Function to perform an inorder traversal of the tree and print the elements
template <class T>
void inorderTraversal(BSTNode1<T>* node) {
    if (node == nullptr) {
        return;
    }
    inorderTraversal(node->left);
    cout << node->x << " ";
    inorderTraversal(node->right);
}

int main() {
    ScapegoatTree1<int> tree;

    // Insert elements into the tree
    tree.add(5);
    tree.add(2);
    tree.add(8);
    tree.add(1);
    tree.add(4);
    tree.add(7);
    tree.add(9);
    tree.add(3);
    tree.add(6);

    // Access the root node of the tree
    BSTNode1<int>* root = tree.r;

    // Print the elements of the tree using inorder traversal
    cout << "Elements of the tree: ";
    inorderTraversal(root);
    cout << endl;

    // Remove the element 4 from the tree
    tree.remove(4);

    // Print the elements of the tree after removal using inorder traversal
    cout << "Tree after removing 4: "<<endl;
    inorderTraversal(root);
    cout << endl;

    return 0;
}


#ifndef ARRAY_H_
#define ARRAY_H_
#include <iostream>

#include <algorithm>

#include <stdlib.h>

#include <assert.h>

namespace ods {

    /**
     * A simple array class that simulates Java's arrays implementation - kind of
     * TODO: Make a reference-counted version so that the = operator doesn't have
     * to destroy its right-hand side.
     */
    template < class T >
        class array {
            protected: T * a;
            public: int length;
            array(int len);
            array(int len, T init);
            void fill(T x);
            virtual~array();

            array < T > & operator = (array < T > & b) {
                if (a != NULL) delete[] a;
                a = b.a;
                b.a = NULL;
                length = b.length;
                return * this;
            }

            T & operator[](int i) {
                assert(i >= 0 && i < length);
                return a[i];
            }

            T * operator + (int i) {
                return & a[i];
            }

            void swap(int i, int j) {
                T x = a[i];
                a[i] = a[j];
                a[j] = x;
            }

            static void copyOfRange(array < T > & a0, array < T > & a, int i, int j);
            virtual void reverse();
        };

    template < class T >
        array < T > ::array(int len) {
            length = len;
            a = new T[length];
        }

    template < class T >
        array < T > ::array(int len, T init) {
            length = len;
            a = new T[length];
            for (int i = 0; i < length; i++)
                a[i] = init;
        }

    template < class T >
        array < T > ::~array() {
            if (a != NULL) delete[] a;
        }

    template < class T >
        void array < T > ::reverse() {
            for (int i = 0; i < length / 2; i++) {
                swap(i, length - i - 1);
            }
        }

    template < class T >
        void array < T > ::copyOfRange(array < T > & a0, array < T > & a, int i, int j) {
            array < T > b(j - i);
            std::copy(a.a, a.a + j - i, b.a);
            a0 = b;
        }

    template < class T >
        void array < T > ::fill(T x) {
            std::fill(a, a + length, x);
        }

} /* namespace ods */
#endif /* ARRAY_H_ */

#ifndef ARRAYDEQUE_H_
#define ARRAYDEQUE_H_
#include "array.h"

#include "utils.h"

namespace ods {

    template < class T >
        class ArrayDeque {
            protected: array < T > a;
            int j;
            int n;
            void resize();
            public: ArrayDeque();
            virtual~ArrayDeque();
            int size();
            T get(int i);
            T set(int i, T x);
            virtual void add(int i, T x);
            virtual T remove(int i);
            virtual void clear();
        };

    template < class T > inline
    T ArrayDeque < T > ::get(int i) {
        return a[(j + i) % a.length];
    }

    template < class T > inline
    T ArrayDeque < T > ::set(int i, T x) {
        T y = a[(j + i) % a.length];
        a[(j + i) % a.length] = x;
        return y;
    }

    template < class T >
        void ArrayDeque < T > ::clear() {
            n = 0;
            j = 0;
            array < T > b(1);
            a = b;
        }

    template < class T >
        ArrayDeque < T > ::ArrayDeque(): a(1) {
            n = 0;
            j = 0;
        }

    template < class T >
        ArrayDeque < T > ::~ArrayDeque() {}

    template < class T >
        void ArrayDeque < T > ::resize() {
            array < T > b(max(1, 2 * n));
            for (int k = 0; k < n; k++)
                b[k] = a[(j + k) % a.length];
            a = b;
            j = 0;
        }

    template < class T >
        int ArrayDeque < T > ::size() {
            return n;
        }

    template < class T >
        void ArrayDeque < T > ::add(int i, T x) {
            if (n + 1 > a.length) resize();
            if (i < n / 2) { // shift a[0],..,a[i-1] left one position
                j = (j == 0) ? a.length - 1 : j - 1;
                for (int k = 0; k <= i - 1; k++)
                    a[(j + k) % a.length] = a[(j + k + 1) % a.length];
            } else { // shift a[i],..,a[n-1] right one position
                for (int k = n; k > i; k--)
                    a[(j + k) % a.length] = a[(j + k - 1) % a.length];
            }
            a[(j + i) % a.length] = x;
            n++;
        }

    template < class T >
        T ArrayDeque < T > ::remove(int i) {
            T x = a[(j + i) % a.length];
            if (i < n / 2) { // shift a[0],..,[i-1] right one position
                for (int k = i; k > 0; k--)
                    a[(j + k) % a.length] = a[(j + k - 1) % a.length];
                j = (j + 1) % a.length;
            } else { // shift a[i+1],..,a[n-1] left one position
                for (int k = i; k < n - 1; k++)
                    a[(j + k) % a.length] = a[(j + k + 1) % a.length];
            }
            n--;
            if (3 * n < a.length) resize();
            return x;
        }

} /* namespace ods */

#endif /* ARRAYDEQUE_H_ */

#ifndef BINARYTREE_H_
#define BINARYTREE_H_
#include <cstdlib>

#include "ArrayDeque.h"

namespace ods {

    template < class N >
        class BTNode {
            public: N * left;
            N * right;
            N * parent;
            BTNode() {
                left = right = parent = NULL;
            }
        };

    template < class Node >
        class BinaryTree {
            protected: Node * r; // root node
            Node * nil; // null-like node
            virtual int size(Node * u);
            virtual int height(Node * u);
            virtual void traverse(Node * u);
            public: virtual~BinaryTree();
            BinaryTree();
            BinaryTree(Node * nil);
            virtual void clear();
            virtual int depth(Node * u);
            virtual int size();
            virtual int size2();
            virtual int height();
            virtual void traverse();
            virtual void traverse2();
            virtual void bfTraverse();
        };

    class BTNode1: public BTNode < BTNode1 > {};

    template < class Node >
        BinaryTree < Node > ::~BinaryTree() {
            clear();
        }

    template < class Node >
        void BinaryTree < Node > ::clear() {
            Node * u = r, * prev = nil, * next;
            while (u != nil) {
                if (prev == u -> parent) {
                    if (u -> left != nil) next = u -> left;
                    else if (u -> right != nil) next = u -> right;
                    else next = u -> parent;
                } else if (prev == u -> left) {
                    if (u -> right != nil) next = u -> right;
                    else next = u -> parent;
                } else {
                    next = u -> parent;
                }
                prev = u;
                if (next == u -> parent)
                    delete u;
                u = next;
            }
            r = nil;
        }

    template < class Node >
        BinaryTree < Node > ::BinaryTree(Node * nil) {
            this -> nil = nil;
            r = nil;
        }

    template < class Node >
        BinaryTree < Node > ::BinaryTree() {
            nil = NULL;
            r = nil;
        }

    template < class Node >
        int BinaryTree < Node > ::depth(Node * u) {
            int d = 0;
            while (u != r) {
                u = u -> parent;
                d++;
            }
            return d;
        }

    template < class Node >
        int BinaryTree < Node > ::size() {
            return size(r);
        }

    template < class Node >
        int BinaryTree < Node > ::size(Node * u) {
            if (u == nil) return 0;
            return 1 + size(u -> left) + size(u -> right);
        }

    template < class Node >
        int BinaryTree < Node > ::size2() {
            Node * u = r, * prev = nil, * next;
            int n = 0;
            while (u != nil) {
                if (prev == u -> parent) {
                    n++;
                    if (u -> left != nil) next = u -> left;
                    else if (u -> right != nil) next = u -> right;
                    else next = u -> parent;
                } else if (prev == u -> left) {
                    if (u -> right != nil) next = u -> right;
                    else next = u -> parent;
                } else {
                    next = u -> parent;
                }
                prev = u;
                u = next;
            }
            return n;
        }

    template < class Node >
        int BinaryTree < Node > ::height() {
            return height(r);
        }

    template < class Node >
        int BinaryTree < Node > ::height(Node * u) {
            if (u == nil) return -1;
            return 1 + max(height(u -> left), height(u -> right));
        }

    template < class Node >
        void BinaryTree < Node > ::traverse() {
            traverse(r);
        }

    template < class Node >
        void BinaryTree < Node > ::traverse(Node * u) {
            if (u == nil) return;
            traverse(u -> left);
            traverse(u -> right);
        }

    template < class Node >
        void BinaryTree < Node > ::traverse2() {
            Node * u = r, * prev = nil, * next;
            while (u != nil) {
                if (prev == u -> parent) {
                    if (u -> left != nil) next = u -> left;
                    else if (u -> right != nil) next = u -> right;
                    else next = u -> parent;
                } else if (prev == u -> left) {
                    if (u -> right != nil) next = u -> right;
                    else next = u -> parent;
                } else {
                    next = u -> parent;
                }
                prev = u;
                u = next;
            }
        }

    template < class Node >
        void BinaryTree < Node > ::bfTraverse() {
            ArrayDeque < Node * > q;
            if (r != nil) q.add(q.size(), r);
            while (q.size() > 0) {
                Node * u = q.remove(q.size() - 1);
                if (u -> left != nil) q.add(q.size(), u -> left);
                if (u -> right != nil) q.add(q.size(), u -> right);
            }
        }

} /* namespace ods */
#endif /* BINARYTREE_H_ */

#ifndef BINARYSEARCHTREE_H_
#define BINARYSEARCHTREE_H_
#include <climits>

#include <cmath>

#include "BinaryTree.h"

#include "utils.h"

namespace ods {

    template < class Node, class T >
        class BSTNode: public BTNode < Node > {
            public: T x;
        };

    /**
     * A binary search tree class.  The Node parameter should be a subclass
     * of BSTNode<T> (or match it's interface)
     */
    template < class Node, class T >
        class BinarySearchTree: public BinaryTree < Node > {
            protected: using BinaryTree < Node > ::r;
            using BinaryTree < Node > ::nil;
            int n;
            T null;
            virtual Node * findLast(T x);
            virtual bool addChild(Node * p, Node * u);
            virtual void splice(Node * u);
            virtual void remove(Node * u);
            virtual void rotateRight(Node * u);
            virtual void rotateLeft(Node * u);
            virtual bool add(Node * u);
            public: BinarySearchTree();
            BinarySearchTree(T null);
            virtual~BinarySearchTree();
            virtual bool add(T x);
            virtual bool remove(T x);
            virtual T find(T x);
            virtual T findEQ(T x);
            virtual int size();
            virtual void clear();
        };

    template < class T >
        class BSTNode1: public BSTNode < BSTNode1 < T > , T > {};

    template < class T >
        class BinarySearchTree1: public BinarySearchTree < BSTNode1 < T > , T > {
            public: BinarySearchTree1();
        };

    /*
     * FIXME: Why doesn't this work?
    template<class Node>
    BinarySearchTree<Node,int>::BinarySearchTree()  {
    	this->null = INT_MIN;
    	n = 0;
    }
    */

    template < class Node, class T >
        BinarySearchTree < Node, T > ::BinarySearchTree() {
            this -> null = (T) NULL; // won't work for non-primitive types
            n = 0;
        }

    template < class Node, class T >
        BinarySearchTree < Node, T > ::BinarySearchTree(T null) {
            this -> null = null;
            n = 0;
        }

    template < class Node, class T >
        Node * BinarySearchTree < Node, T > ::findLast(T x) {
            Node * w = r, * prev = nil;
            while (w != nil) {
                prev = w;
                int comp = compare(x, w -> x);
                if (comp < 0) {
                    w = w -> left;
                } else if (comp > 0) {
                    w = w -> right;
                } else {
                    return w;
                }
            }
            return prev;
        }

    template < class Node, class T >
        T BinarySearchTree < Node, T > ::findEQ(T x) {
            Node * w = r;
            while (w != nil) {
                int comp = compare(x, w -> x);
                if (comp < 0) {
                    w = w -> left;
                } else if (comp > 0) {
                    w = w -> right;
                } else {
                    return w -> x;
                }
            }
            return null;
        }

    template < class Node, class T >
        T BinarySearchTree < Node, T > ::find(T x) {
            Node * w = r, * z = nil;
            while (w != nil) {
                int comp = compare(x, w -> x);
                if (comp < 0) {
                    z = w;
                    w = w -> left;
                } else if (comp > 0) {
                    w = w -> right;
                } else {
                    return w -> x;
                }
            }
            return z == nil ? null : z -> x;
        }

    template < class Node, class T >
        BinarySearchTree < Node, T > ::~BinarySearchTree() {
            // nothing to do - BinaryTree destructor does cleanup
        }

    template < class Node, class T >
        bool BinarySearchTree < Node, T > ::addChild(Node * p, Node * u) {
            if (p == nil) {
                r = u; // inserting into empty tree
            } else {
                int comp = compare(u -> x, p -> x);
                if (comp < 0) {
                    p -> left = u;
                } else if (comp > 0) {
                    p -> right = u;
                } else {
                    return false; // u.x is already in the tree
                }
                u -> parent = p;
            }
            n++;
            return true;
        }

    template < class Node, class T >
        bool BinarySearchTree < Node, T > ::add(T x) {
            Node * p = findLast(x);
            Node * u = new Node;
            u -> x = x;
            return addChild(p, u);
        }

    template < class Node, class T >
        bool BinarySearchTree < Node, T > ::add(Node * u) {
            Node * p = findLast(u -> x);
            return addChild(p, u);
        }

    template < class Node, class T >
        void BinarySearchTree < Node, T > ::splice(Node * u) {
            Node * s, * p;
            if (u -> left != nil) {
                s = u -> left;
            } else {
                s = u -> right;
            }
            if (u == r) {
                r = s;
                p = nil;
            } else {
                p = u -> parent;
                if (p -> left == u) {
                    p -> left = s;
                } else {
                    p -> right = s;
                }
            }
            if (s != nil) {
                s -> parent = p;
            }
            n--;
        }

    template < class Node, class T >
        void BinarySearchTree < Node, T > ::remove(Node * u) {
            if (u -> left == nil || u -> right == nil) {
                splice(u);
                delete u;
            } else {
                Node * w = u -> right;
                while (w -> left != nil)
                    w = w -> left;
                u -> x = w -> x;
                splice(w);
                delete w;
            }
        }

    template < class Node, class T >
        bool BinarySearchTree < Node, T > ::remove(T x) {
            Node * u = findLast(x);
            if (u != nil && compare(x, u -> x) == 0) {
                remove(u);
                return true;
            }
            return false;
        }

    template < class Node, class T > inline
    int BinarySearchTree < Node, T > ::size() {
        return n;
    }

    template < class Node, class T > inline
    void BinarySearchTree < Node, T > ::clear() {
        BinaryTree < Node > ::clear();
        n = 0;
    }

    template < class Node, class T >
        void BinarySearchTree < Node, T > ::rotateLeft(Node * u) {
            Node * w = u -> right;
            w -> parent = u -> parent;
            if (w -> parent != nil) {
                if (w -> parent -> left == u) {
                    w -> parent -> left = w;
                } else {
                    w -> parent -> right = w;
                }
            }
            u -> right = w -> left;
            if (u -> right != nil) {
                u -> right -> parent = u;
            }
            u -> parent = w;
            w -> left = u;
            if (u == r) {
                r = w;
                r -> parent = nil;
            }
        }

    template < class Node, class T >
        void BinarySearchTree < Node, T > ::rotateRight(Node * u) {
            Node * w = u -> left;
            w -> parent = u -> parent;
            if (w -> parent != nil) {
                if (w -> parent -> left == u) {
                    w -> parent -> left = w;
                } else {
                    w -> parent -> right = w;
                }
            }
            u -> left = w -> right;
            if (u -> left != nil) {
                u -> left -> parent = u;
            }
            u -> parent = w;
            w -> right = u;
            if (u == r) {
                r = w;
                r -> parent = nil;
            }
        }

    /*
    template<class T>
    BinarySearchTree1<T*>::BinarySearchTree1() : BinarySearchTree<BSTNode1<T*>, T*>(NULL) {
    }
    */

    template < class T >
        BinarySearchTree1 < T > ::BinarySearchTree1() {}

} /* namespace ods */
#endif /* 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)` method:

 * **Line 139:** A new node `u` is created and initialized with the value `x`. It is set to have no children and no parent.

* **Line 142:** The `addWithDepth(u)` method is called to perform the basic insertion of the node `u` into the `ScapegoatTree` and keep track of the depth. The result is stored in the variable `d`.

* **Line 143:** If the depth `d` of the inserted node `u` exceeds the logarithmic threshold `log32(q)`, where `q` represents the number of nodes in the tree, it means the tree has become unbalanced and needs to be rebuilt.

* **Line 144:** The parent node of the inserted node `u` is assigned to the variable `w`. This will be used to find the scapegoat node.

* **Line 145:** The variables `a` and `b` are declared to store the sizes of the subtrees of `w`. We need to determine which subtree of `w` contains the newly inserted node `u`.

* **Lines 146–147:** We check if `w->left` is equal to `u`. If so, it means `u` is in the left subtree of `w`. In this case, we know that the size of the left subtree of `w` has already been computed as `d - 1`. Therefore, we assign `d - 1` to `a` and compute the size of the right subtree as the difference between the size of `w` and `a - 1`.

* **Lines 150–151:** If `w->left` is not equal to `u`, it means `u` is in the right subtree of `w`. In this case, we know that the size of the right subtree of `w` has already been computed as `d - 1`. Therefore, we assign `d - 1` to `b` and compute the size of the left subtree as the difference between the size of `w` and `b - 1`.

* **Lines 153–157:** The while loop is used to traverse up the tree from the scapegoat node `w` towards the root. It checks if the current subtree rooted at `w` is unbalanced by comparing the sizes of its left and right subtrees. If the condition `3 * a <= 2 * b` is false, it means that the size of the right subtree `b` is less than two-thirds of the size of the left subtree `a`. In this case, the current node `w` is not the scapegoat node, and we continue traversing up the tree towards the root to find the scapegoat node. The purpose of this while loop is to efficiently find the scapegoat node without recomputing the sizes of the subtrees that have already been computed. By checking the condition and updating `a` and `b` within the loop, we avoid unnecessary computations and quickly identify the scapegoat node with an unbalanced subtree.

* **Line 158:** Once the scapegoat node `w` is found, the `rebuild(w->parent)` method is called to rebuild the subtree rooted at the parent of the scapegoat node. This rebuild operation ensures that the `ScapegoatTree` remains balanced.

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

Overview

Array-Based Lists

Linked Lists

Skiplists

Hash Tables

Binary Trees

Random Binary Search Trees

Scapegoat Trees

Red-Black Trees

Heaps

Sorting Algorithms

Graphs

Data Structures for Integers

External Memory Searching

Wrap Up

Solution: Scapegoat Trees

Task