public final boolean remove()

in core-avl/src/main/java/org/apache/directory/server/core/avltree/avl/AvlTreeSet.java [204:354]

• 125 lines of code
• 26 McCabe index (conditional complexity)

    public final boolean remove( T value )
    {
        AvlNode<T> node = tree;

        if ( node == null )
        {
            return false;
        }

        // find the node to be removed
        for ( int cmp = value.compareTo( node.value ); cmp != 0; cmp = value.compareTo( node.value ) )
        {
            node = ( cmp < 0 ) ? node.left : node.right;

            if ( node == null )
            {
                return false;
            }
        }

        // find a replacement node (if needed)
        final int left = -1;
        final int right = 1;
        final int none = 0;
        int replaceFrom = none;

        if ( node.left != null && node.right == null )
        {
            replaceFrom = left;
        }
        else if ( node.right != null && node.left == null )
        {
            replaceFrom = right;
        }
        else if ( node.right != null && node.left != null )
        {
            if ( node.balance < 0 )
            {
                replaceFrom = left;
            }
            else if ( node.balance > 0 )
            {
                replaceFrom = right;
            }
            else
            {
                replaceFrom = left; // TODO: asymmetry
            }
        }
        else
        { // node is itself a leaf, replacement is not needed
            if ( node.parent == null )
            { // the tree root, single node in the tree
                tree = null;
                --size;
                recycleNode( node );

                return true;
            }
            else
            { // non-root leaf node
              // detach from parent
                if ( node.parent.left == node )
                {
                    node.parent.left = null;
                }
                else
                {
                    node.parent.right = null;
                }

                AvlNode<T> dead = node;
                // update heights/rebalance from node's parents up (the bottom of this method)
                node = node.parent;
                recycleNode( dead );
                replaceFrom = none;
            }
        }

        if ( replaceFrom != none )
        {
            AvlNode<T> leaf = null;

            if ( replaceFrom == left )
            {
                leaf = node.left;

                while ( leaf.left != null || leaf.right != null )
                {
                    if ( leaf.right != null )
                    {
                        leaf = leaf.right;
                    }
                    else
                    {
                        // the rotation should ensure (leaf.right != null) on the next iteration
                        leaf = smallRightRotation( leaf );
                    }
                }
            }
            else if ( replaceFrom == right )
            {
                leaf = node.right;

                while ( leaf.right != null || leaf.left != null )
                {
                    if ( leaf.left != null )
                    {
                        leaf = leaf.left;
                    }
                    else
                    {
                        // the rotation should ensure (leaf.left != null) on the next iteration
                        leaf = smallLeftRotation( leaf );
                    }
                }
            }
            else
            {
                assert false : "should never happen";
            }

            assert leaf != null : "replacement leaf should always exist at this point";

            // detach leaf from its parent
            if ( leaf.parent.left == leaf )
            {
                leaf.parent.left = null;
            }
            else if ( leaf.parent.right == leaf )
            {
                leaf.parent.right = null;
            }
            else
            {
                assert false : "broken parent/child reference in the tree";
            }

            node.value = leaf.value; // replace node value with leaf's value
            node = leaf.parent; // change recursion point down so that below down-up update picks up
            // everything from leaf's parent up

            recycleNode( leaf );
        }

        rebalanceUp( node );

        --size;

        return true;
    }