// Source File Name:   BTTree.java


class BTTree
{

    public BTTree()
    {
        root = null;
        nodecount = 0;
    }

    public BTTree(boolean flag)
    {
        root = null;
        nodecount = 0;
        AVLbalanced = flag;
    }

    public void insert(BTTree bttree)
    {
        for(BTNode btnode = bttree.root; btnode != null; btnode = btnode.nextPrO())
            insert(btnode.data);

    }

    public BTNode locate(BTData btdata)
    {
        BTNode btnode;
        int i;
        for(btnode = root; btnode != null && (i = btdata.compareTo(btnode.data)) != 0; btnode = btnode.child(i));
        return btnode;
    }

    public BTNode insert(BTData btdata)
    {
        if(root == null)
        {
            root = new BTNode(btdata);
            return root;
        }
        int i = 0;
        BTNode btnode = null;
        BTNode btnode1;
        for(btnode1 = root; btnode1 != null && (i = btdata.compareTo(btnode1.data)) != 0; btnode1 = btnode1.child(i))
            btnode = btnode1;

        if(btnode1 != null)
            return null;
        BTNode btnode2 = new BTNode(btdata);
        join(btnode, btnode2, i);
        if(AVLbalanced)
            rebalance(btnode, i);
        nodecount++;
        return btnode2;
    }

    public BTNode remove(BTData btdata)
    {
        int i = 0;
        BTNode btnode1 = root;
        BTNode btnode2 = null;			
        for(; btnode1 != null && (i = btdata.compareTo(btnode1.data)) != 0; btnode1 = btnode1.child(i));
        if(btnode1 == null)
            return null;
        if(btnode1.lchild != null && btnode1.rchild != null)
        {
            BTNode btnode3 = btnode1.prevInO();
            double d = btnode3.x;
            double d1 = btnode3.y;
            BTData btdata1 = btnode1.data;
            btnode1.data = btnode3.data;
            btnode3.data = btdata1;
            BTNode btnode4 = btnode1;
            btnode1 = btnode3;
            btnode3 = btnode4;
            btnode3.x = btnode1.x;
            btnode3.y = btnode1.y;
        }
        
        btnode2 = (btnode1.lchild == null ? btnode1.rchild : btnode1.lchild);
        BTNode btnode = btnode1.parent;
        i = btnode1.side();
        join(btnode, btnode2, i);
        if(root == btnode1)
            root = btnode2;
        if(AVLbalanced)
            debalance(btnode, i);
        nodecount--;
        return btnode1;
    }

    public void delall()
    {
        for(BTNode btnode1 = root.firstPoO(); btnode1 != null;)
        {
            BTNode btnode = btnode1;
            btnode1 = btnode.nextPoO();
            btnode.data = null;
            btnode = null;
        }

        root.data = null;
        root = null;
    }

    public void join(BTNode btnode, BTNode btnode1, int i)
    {
        if(btnode1 != null)
            btnode1.parent = btnode;
        if(btnode != null)
        {
            if(i == -1)
            {
                btnode.lchild = btnode1;
                return;
            }
            if(i == 1)
                btnode.rchild = btnode1;
        }
    }

    public BTNode rotate(BTNode btnode, int i)
    {
        BTNode btnode1 = btnode.child(-i);
        BTNode btnode2 = btnode1.child(i);
        join(btnode, btnode2, -i);
        join(btnode.parent, btnode1, btnode.side());
        join(btnode1, btnode, i);
        if(btnode == root)
            root = btnode1;
        return btnode1;
    }

    public BTNode balance(BTNode btnode)
    {
        int i = btnode.balance;
        BTNode btnode1 = btnode.child(i);
        BTNode btnode2 = btnode1.child(-i);
        if(btnode1.balance == -i)
        {
            rotate(btnode1, i);
            if(btnode2.balance == -i)
            {
                btnode.balance = 0;
                btnode1.balance = i;
            } else
            if(btnode2.balance == i)
            {
                btnode.balance = -i;
                btnode1.balance = 0;
            } else
            {
                btnode.balance = 0;
                btnode1.balance = 0;
            }
            btnode2.balance = 0;
        } else
        if(btnode1.balance == i)
        {
            btnode.balance = 0;
            btnode1.balance = 0;
        } else
        if(btnode1.balance == 0)
        {
            btnode.balance = i;
            btnode1.balance = -i;
        }
        btnode = rotate(btnode, -i);
        return btnode;
    }

    public void rebalance(BTNode btnode, int i)
    {
        for(; btnode != null; btnode = btnode.parent)
        {
            if(btnode.balance != i)
                btnode.balance += i;
            else
                btnode = balance(btnode);
            if(btnode.balance == 0)
                break;
            i = btnode.side();
        }

    }

    public void debalance(BTNode btnode, int i)
    {
        for(; btnode != null; btnode = btnode.parent)
        {
            if(btnode.balance != -i)
                btnode.balance -= i;
            else
                btnode = balance(btnode);
            if(btnode.balance != 0)
                break;
            i = btnode.side();
        }

    }

    BTNode root;
    int nodecount;
    boolean AVLbalanced;
    int mode;
}