bstree.java

The applet illustrates the behaviour of binary search trees, Searching and Sorting Algorithms, Self-

// Source File Name:   BSTree.java


class BSTree
{

    public BSTree(int mode)
    {
        root = null;
        setMode(mode, true);
    }

    public void setMode(int mode, boolean state)
    {
        switch(mode)
        {
        case 1: // '\001'
            if(state)
            {
                AVL = true;
                SPL = false;
                RBL = false;
            } else
            {
                AVL = false;
            }
            break;

        case 2: // '\002'
            if(state)
            {
                SPL = true;
                AVL = false;
                RBL = false;
            } else
            {
                SPL = false;
            }
            break;

        case 3: // '\003'
            if(state)
            {
                RBL = true;
                AVL = false;
                SPL = false;
            } else
            {
                RBL = false;
            }
            break;

        default:
            AVL = false;
            SPL = false;
            RBL = false;
            break;
        }
    }

    public boolean isAVL()
    {
        return AVL;
    }

    public boolean isSPL()
    {
        return SPL;
    }

    public boolean isRBL()
    {
        return RBL;
    }

    public BTNode getRoot()
    {
        return root;
    }

    public void setRoot(BTNode node)
    {
        root = node;
    }

    public boolean isEmpty()
    {
        return root == null;
    }

    public int getDepth()
    {
        int maxdepth = 0;
        for(BTNode node = root; node != null; node = node.nextPrO())
        {
            int depth = node.getDepth(root);
            if(depth > maxdepth)
                maxdepth = depth;
        }

        return maxdepth;
    }

    public void destroy(BTNode node)
    {
        node = null;
    }

    public BTNode find(BTData data)
    {
        BTNode node = locate(data);
        if(isSPL())
            splay(lastnode);
        return node;
    }

    public BTNode insert(BTData data)
    {
        if(isSPL())
            return insertSPL(data);
        if(isAVL())
            return insertAVL(data);
        if(isRBL())
            return insertRBL(data);
        else
            return insertBST(data);
    }

    public BTNode delete(BTData data, int minmax)
    {
        if(isAVL())
            return deleteAVL(data, minmax);
        if(isSPL())
            return deleteSPL(data, minmax);
        if(isRBL())
            return deleteRBL(data, minmax);
        else
            return deleteBST(data, minmax);
    }

    public BTNode locate(BTData data)
    {
        BTNode node = root;
        BTNode next = null;
        int side = 0;
        for(; node != null; node = next)
        {
            side = node.compareSide(data);
            next = node.getChild(side);
            if(next == node || next == null)
                break;
        }

        lastnode = node;
        nextside = side;
        return next;
    }

    public BTNode add(BTNode node, int side, BTData data)
    {
        BTNode newnode = new BTNode(data);
        link(node, side, newnode);
        return newnode;
    }

    public BTNode remove(BTNode node)
    {
        BTNode child = node.getChild();
        BTNode parent = node.getParent();
        int side = node.getSide();
        link(parent, side, child);
        destroy(node);
        return parent;
    }

    public void link(BTNode parent, int side, BTNode child)
    {
        if(child != null)
            child.setParent(parent);
        if(parent != null)
            parent.setChild(side, child);
        else
            root = child;
    }

    public BTNode rotate(BTNode node, int side)
    {
        BTNode parent = node.getParent();
        BTNode child = node.getChild(-side);
        BTNode grand = child.getChild(side);
        link(node, -side, grand);
        link(parent, node.getSide(), child);
        link(child, side, node);
        return child;
    }

    public BTNode swap(BTNode node, int minmax)
    {
        BTNode swap = getSuccessor(node, minmax);
        BTNode temp = node;
        swapData(node, swap);
        node = swap;
        swap = temp;
        return node;
    }

    public BTNode getSuccessor(BTNode node, int minmax)
    {
        return minmax != 1 ? node.nextInO() : node.prevInO();
    }

    public void swapData(BTNode node1, BTNode node2)
    {
        BTData data = node1.getData();
        node1.setData(node2.getData());
        node2.setData(data);
    }

    public void deleteAll()
    {
        for(BTNode node = root.firstPoO(); node != null;)
        {
            BTNode leaf = node;
            node = leaf.nextPoO();
            destroy(leaf);
        }

        root = null;
    }

    public BTNode locateBST(BTData data)
    {
        BTNode node;
        int side;
        for(node = root; node != null; node = node.getChild(side))
        {
            side = node.compareSide(data);
            if(side == 0)
                break;
        }

        return node;
    }

    public BTNode insertBST(BTData data)
    {
        if(root == null)
        {
            return add(null, 0, data);
        } else
        {
            BTNode node = locate(data);
            return node == null ? add(lastnode, nextside, data) : null;
        }
    }

    public BTNode deleteBST(BTData data, int minmax)
    {
        BTNode node = locate(data);
        if(node == null)
            return null;
        if(node.hasTwoChildren())
            node = swap(node, minmax);
        return remove(node);
    }

    public BTNode insertAVL(BTData data)
    {
        if(root == null)
            return add(null, 0, data);
        if(locate(data) != null)
        {
            return null;
        } else
        {
            BTNode node = add(lastnode, nextside, data);
            rebalanceAVL(lastnode, nextside, 1);
            return node;
        }
    }

    public BTNode deleteAVL(BTData data, int minmax)
    {
        BTNode node = locate(data);
        if(node == null)
            return null;
        if(node.hasTwoChildren())
            node = swap(node, minmax);
        int side = node.getSide();
        node = remove(node);
        rebalanceAVL(node, side, -1);
        return node;
    }

    public void rebalanceAVL(BTNode node, int side, int in)
    {
        for(; node != null; node = node.getParent())
        {
            if(node.getBalance() != in * side)
                node.setBalance(node.getBalance() + in * side);
            else
                node = rotateAVL(node);
            if(in == 1 && node.getBalance() == 0 || in == -1 && node.getBalance() != 0)
                break;
            side = node.getSide();
        }

    }