/*This is a Java Program to implement ScapeGoat Tree. A scapegoat tree is a self-balancing binary search tree which provides worst-case O(log n) lookup time, and O(log n) amortized insertion and deletion time.*/

/*
 * Java Program to Implement ScapeGoat Tree
 */

import java.util.Scanner;

/* Class SGTNode */
class SGTNode
{
    SGTNode right, left, parent;
    int value;

    /* Constructor */
    public SGTNode(int val)
    {
        value = val;
    }
}

/* Class ScapeGoatTree */
class ScapeGoatTree
{
    private SGTNode root;
    private int n, q;

    /* Constructor */
    public ScapeGoatTree()
    {
        root = null;
        // size = 0
        n = 0;
    }
    /* Function to check if tree is empty */
    public boolean isEmpty()
    {
        return root == null;
    }
    /* Function to clear  tree */
    public void makeEmpty()
    {
        root = null;
        n = 0;
    }
    /* Function to count number of nodes recursively */
    private int size(SGTNode r)
    {
        if (r == null)
            return 0;
        else
            {
                int l = 1;
                l += size(r.left);
                l += size(r.right);
                return l;
            }
    }
    /* Functions to search for an element */
    public boolean search(int val)
    {
        return search(root, val);
    }
    /* Function to search for an element recursively */
    private boolean search(SGTNode r, int val)
    {
        boolean found = false;
        while ((r != null) && !found)
            {
                int rval = r.value;
                if (val < rval)
                    r = r.left;
                else if (val > rval)
                    r = r.right;
                else
                    {
                        found = true;
                        break;
                    }
                found = search(r, val);
            }
        return found;
    }
    /* Function to return current size of tree */
    public int size()
    {
        return n;
    }
    /* Function for inorder traversal */
    public void inorder()
    {
        inorder(root);
    }
    private void inorder(SGTNode r)
    {
        if (r != null)
            {
                inorder(r.left);
                System.out.print(r.value +" ");
                inorder(r.right);
            }
    }
    /* Function for preorder traversal */
    public void preorder()
    {
        preorder(root);
    }
    private void preorder(SGTNode r)
    {
        if (r != null)
            {
                System.out.print(r.value +" ");
                preorder(r.left);
                preorder(r.right);
            }
    }
    /* Function for postorder traversal */
    public void postorder()
    {
        postorder(root);
    }
    private void postorder(SGTNode r)
    {
        if (r != null)
            {
                postorder(r.left);
                postorder(r.right);
                System.out.print(r.value +" ");
            }
    }
    private static final int log32(int q)
    {
        final double log23 = 2.4663034623764317;
        return (int)Math.ceil(log23*Math.log(q));
    }
    /* Function to insert an element */
    public boolean add(int x)
    {
        /* first do basic insertion keeping track of depth */
        SGTNode u = new SGTNode(x);
        int d = addWithDepth(u);
        if (d > log32(q))
            {
                /* depth exceeded, find scapegoat */
                SGTNode w = u.parent;
                while (3*size(w) <= 2*size(w.parent))
                    w = w.parent;
                rebuild(w.parent);
            }
        return d >= 0;
    }
    /* Function to rebuild tree from node u */
    protected void rebuild(SGTNode u)
    {
        int ns = size(u);
        SGTNode p = u.parent;
        SGTNode[] a = new SGTNode[ns];
        packIntoArray(u, a, 0);
        if (p == null)
            {
                root = buildBalanced(a, 0, ns);
                root.parent = null;
            }
        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;
            }
    }
    /* Function to packIntoArray */
    protected int packIntoArray(SGTNode u, SGTNode[] a, int i)
    {
        if (u == null)
            {
                return i;
            }
        i = packIntoArray(u.left, a, i);
        a[i++] = u;
        return packIntoArray(u.right, a, i);
    }
    /* Function to build balanced nodes */
    protected SGTNode buildBalanced(SGTNode[] a, int i, int ns)
    {
        if (ns == 0)
            return null;
        int m = ns / 2;
        a[i + m].left = buildBalanced(a, i, m);
        if (a[i + m].left != null)
            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 != null)
            a[i + m].right.parent = a[i + m];
        return a[i + m];
    }
    /* Function add with depth */
    public int addWithDepth(SGTNode u)
    {
        SGTNode w = root;
        if (w == null)
            {
                root = u;
                n++;
                q++;
                return 0;
            }
        boolean done = false;
        int d = 0;
        do
            {
                if (u.value < w.value)
                    {
                        if (w.left == null)
                            {
                                w.left = u;
                                u.parent = w;
                                done = true;
                            }
                        else
                            {
                                w = w.left;
                            }
                    }
                else if (u.value > w.value)
                    {
                        if (w.right == null)
                            {
                                w.right = u;
                                u.parent = w;
                                done = true;
                            }
                        w = w.right;
                    }
                else
                    {
                        return -1;
                    }
                d++;
            }
        while (!done);
        n++;
        q++;
        return d;
    }
}

public class ScapeGoatTreeTest
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        /* Creating object of ScapeGoatTree */
        ScapeGoatTree sgt = new ScapeGoatTree();
        System.out.println("ScapeGoat Tree Test\n");
        char ch;
        /*  Perform tree operations  */
        do
            {
                System.out.println("\nScapeGoat Tree Operations\n");
                System.out.println("1. insert ");
                System.out.println("2. count nodes");
                System.out.println("3. search");
                System.out.println("4. check empty");
                System.out.println("5. make empty");
                int choice = scan.nextInt();
                switch (choice)
                    {
                    case 1 :
                        System.out.println("Enter integer element to insert");
                        sgt.add( scan.nextInt() );
                        break;
                    case 2 :
                        System.out.println("Nodes = "+ sgt.size());
                        break;
                    case 3 :
                        System.out.println("Enter integer element to search");
                        System.out.println("Search result : "+ sgt.search( scan.nextInt() ));
                        break;
                    case 4 :
                        System.out.println("Empty status = "+ sgt.isEmpty());
                        break;
                    case 5 :
                        System.out.println("\nTree cleared\n");
                        sgt.makeEmpty();
                        break;
                    default :
                        System.out.println("Wrong Entry \n ");
                        break;
                    }
                /*  Display tree  */
                System.out.print("\nPost order : ");
                sgt.postorder();
                System.out.print("\nPre order : ");
                sgt.preorder();
                System.out.print("\nIn order : ");
                sgt.inorder();
                System.out.println("\nDo you want to continue (Type y or n) \n");
                ch = scan.next().charAt(0);
            }
        while (ch == 'Y'|| ch == 'y');
    }
}

/*

ScapeGoat Tree Operations

1. insert
2. count nodes
3. search
4. check empty
5. make empty
1
Enter integer element to insert
34

Post order : 34
Pre order : 34
In order : 34
Do you want to continue (Type y or n)

y

ScapeGoat Tree Operations

1. insert
2. count nodes
3. search
4. check empty
5. make empty
1
Enter integer element to insert
67

Post order : 67 34
Pre order : 34 67
In order : 34 67
Do you want to continue (Type y or n)

y

ScapeGoat Tree Operations

1. insert
2. count nodes
3. search
4. check empty
5. make empty
1
Enter integer element to insert
11

Post order : 11 67 34
Pre order : 34 11 67
In order : 11 34 67
Do you want to continue (Type y or n)

y

ScapeGoat Tree Operations

1. insert
2. count nodes
3. search
4. check empty
5. make empty
1
Enter integer element to insert
24

Post order : 24 11 67 34
Pre order : 34 11 24 67
In order : 11 24 34 67
Do you want to continue (Type y or n)

y

ScapeGoat Tree Operations

1. insert
2. count nodes
3. search
4. check empty
5. make empty
1
Enter integer element to insert
6

Post order : 6 24 11 67 34
Pre order : 34 11 6 24 67
In order : 6 11 24 34 67
Do you want to continue (Type y or n)

y

ScapeGoat Tree Operations

1. insert
2. count nodes
3. search
4. check empty
5. make empty
1
Enter integer element to insert
97

Post order : 6 24 11 97 67 34
Pre order : 34 11 6 24 67 97
In order : 6 11 24 34 67 97
Do you want to continue (Type y or n)

y

ScapeGoat Tree Operations

1. insert
2. count nodes
3. search
4. check empty
5. make empty
1
Enter integer element to insert
12

Post order : 6 12 24 11 97 67 34
Pre order : 34 11 6 24 12 67 97
In order : 6 11 12 24 34 67 97
Do you want to continue (Type y or n)

y

ScapeGoat Tree Operations

1. insert
2. count nodes
3. search
4. check empty
5. make empty
1
Enter integer element to insert
57

Post order : 6 12 24 11 57 97 67 34
Pre order : 34 11 6 24 12 67 57 97
In order : 6 11 12 24 34 57 67 97
Do you want to continue (Type y or n)

y

ScapeGoat Tree Operations

1. insert
2. count nodes
3. search
4. check empty
5. make empty
2
Nodes = 8

Post order : 6 12 24 11 57 97 67 34
Pre order : 34 11 6 24 12 67 57 97
In order : 6 11 12 24 34 57 67 97
Do you want to continue (Type y or n)

y

ScapeGoat Tree Operations

1. insert
2. count nodes
3. search
4. check empty
5. make empty
3
Enter integer element to search
57
Search result : true

Post order : 6 12 24 11 57 97 67 34
Pre order : 34 11 6 24 12 67 57 97
In order : 6 11 12 24 34 57 67 97
Do you want to continue (Type y or n)


y

ScapeGoat Tree Operations

1. insert
2. count nodes
3. search
4. check empty
5. make empty
5

Tree cleared


Post order :
Pre order :
In order :
Do you want to continue (Type y or n)

y

ScapeGoat Tree Operations

1. insert
2. count nodes
3. search
4. check empty
5. make empty
4
Empty status = true

Post order :
Pre order :
In order :
Do you want to continue (Type y or n)

n