bstree.java

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

    public BTNode rotateAVL(BTNode node)
    {
        int side = node.getBalance();
        BTNode child = node.getChild(side);
        if(child.getBalance() == -side)
        {
            BTNode grand = child.getChild(-side);
            if(grand.getBalance() == -side)
            {
                grand.setBalance(0);
                child.setBalance(side);
                node.setBalance(0);
            } else
            if(grand.getBalance() == side)
            {
                grand.setBalance(0);
                child.setBalance(0);
                node.setBalance(-side);
            } else
            {
                node.setBalance(0);
                child.setBalance(0);
            }
            rotate(child, side);
        } else
        if(child.getBalance() == side)
        {
            node.setBalance(0);
            child.setBalance(0);
        } else
        if(child.getBalance() == 0)
        {
            node.setBalance(side);
            child.setBalance(-side);
        }
        node = rotate(node, -side);
        return node;
    }

    public void balanceAVL(BTNode node)
    {
        int side = node.getBalance();
        BTNode child = node.getChild(side);
        if(child.getBalance() == -side)
        {
            BTNode grand = child.getChild(-side);
            if(grand.getBalance() == -side)
            {
                grand.setBalance(0);
                child.setBalance(side);
                node.setBalance(0);
            } else
            if(grand.getBalance() == side)
            {
                grand.setBalance(0);
                child.setBalance(0);
                node.setBalance(-side);
            } else
            {
                node.setBalance(0);
                child.setBalance(0);
            }
        } else
        if(child.getBalance() == side)
        {
            child.setBalance(0);
            node.setBalance(0);
        } else
        if(child.getBalance() == 0)
            child.setBalance(-side);
    }

    public boolean isAVLcompliant(BTNode node)
    {
        boolean balanced = true;
        if(node == null)
            return true;
        int l = getHeight(node.getChild(-1), 0);
        int r = getHeight(node.getChild(1), 0);
        node.setBalance(r - l);
        if(r - l > 1 || r - l < -1)
            balanced = false;
        return balanced && isAVLcompliant(node.getChild(-1)) && isAVLcompliant(node.getChild(1));
    }

    public int getHeight(BTNode node, int depth)
    {
        if(node == null)
            return 0;
        if(node.isLeaf())
        {
            return depth + 1;
        } else
        {
            int lmax = getHeight(node.getChild(-1), depth + 1);
            int rmax = getHeight(node.getChild(1), depth + 1);
            return lmax <= rmax ? rmax : lmax;
        }
    }

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

    public BTNode splitinsert(BTData data)
    {
        BTNode node = new BTNode(data);
        int side = -root.compareSide(data);
        BTNode child = root.getChild(-side);
        root.setChild(-side, null);
        link(node, side, root);
        link(node, -side, child);
        root = node;
        return root;
    }

    public BTNode deleteSPL(BTData data, int minmax)
    {
        BTNode node = locate(data);
        splay(lastnode);
        if(node == null)
            return null;
        BTNode root = node;
        node = getSuccessor(root, minmax);
        if(node != null)
            splay(node);
        return remove(root);
    }

    public void splay(BTNode node)
    {
        while(node != root) 
        {
            BTNode parent = node.getParent();
            BTNode grandparent = parent.getParent();
            int side = node.getSide();
            if(grandparent == null)
                rotate(parent, -side);
            else
            if(parent.getSide() == side)
            {
                rotate(grandparent, -side);
                rotate(parent, -side);
            } else
            if(parent.getSide() != side)
            {
                rotate(parent, -side);
                rotate(grandparent, side);
            }
        }
    }

    public boolean isSPLcompliant()
    {
        return true;
    }

    public BTNode insertRBL(BTData data)
    {
        if(root == null)
        {
            root = add(null, 0, data);
            root.setColor(2);
            return root;
        }
        if(locate(data) != null)
        {
            return null;
        } else
        {
            BTNode node = add(lastnode, nextside, data);
            node.setColor(1);
            fixRBinsert(node);
            return node;
        }
    }

    public void fixRBinsert(BTNode node)
    {
        while(node != root) 
        {
            BTNode parent = node.getParent();
            if(parent.getColor() == 2)
                break;
            BTNode grandparent = parent.getParent();
            int side = parent.getSide();
            BTNode uncle = grandparent.getChild(-side);
            if(uncle != null && uncle.getColor() == 1)
            {
                parent.setColor(2);
                uncle.setColor(2);
                grandparent.setColor(1);
                node = grandparent;
            } else
            if(node.getSide() == -side)
            {
                rotate(parent, side);
                node = parent;
            } else
            if(node.getSide() == side)
            {
                parent.setColor(2);
                grandparent.setColor(1);
                rotate(grandparent, -side);
            }
        }
        root.setColor(2);
    }

    public BTNode deleteRBL(BTData data, int minmax)
    {
        BTNode node = locate(data);
        if(node == null)
            return null;
        if(node.hasTwoChildren())
            node = swap(node, minmax);
        int color = node.getColor();
        int side = node.getSide();
        node = remove(node);
        if(root != null && side == 0)
            root.setColor(2);
        else
        if(node != null && color == 2)
            fixRBdelete(node, side);
        return node;
    }

    public void fixRBdelete(BTNode parent, int side)
    {
        BTNode node = parent.getChild(side);
        if(node != null && node.getColor() == 1)
        {
            node.setColor(2);
            return;
        }
        while(node != root && isBlack(node)) 
        {
            if(node != null)
            {
                parent = node.getParent();
                side = node.getSide();
            }
            BTNode sibling = parent.getChild(-side);
            BTNode nephew = sibling.getChild(side);
            BTNode niece = sibling.getChild(-side);
            if(sibling.getColor() == 1)
            {
                sibling.setColor(2);
                parent.setColor(1);
                rotate(parent, side);
            } else
            if(isBlack(nephew) && isBlack(niece))
            {
                sibling.setColor(1);
                node = node != null ? node.getParent() : parent;
            } else
            if(isBlack(niece) && isRed(nephew))
            {
                sibling.setColor(1);
                nephew.setColor(2);
                rotate(sibling, -side);
            } else
            if(isRed(niece))
            {
                sibling.setColor(parent.getColor());
                parent.setColor(2);
                niece.setColor(2);
                rotate(parent, side);
                node = root;
            }
        }
        node.setColor(2);
    }

    public boolean isRed(BTNode node)
    {
        return node != null && node.getColor() == 1;
    }

    public boolean isBlack(BTNode node)
    {
        return node == null || node.getColor() == 2;
    }

    public boolean isRBLcompliant(BTNode node)
    {
        return false;
    }

    public static final int INSERT = 1;
    public static final int DELETE = -1;
    BTNode root;
    boolean AVL;
    boolean SPL;
    boolean RBL;
    BTNode lastnode;
    int nextside;
}