btreeinterioruos.java

国外的数据结构与算法分析用书

        If the node is not to be deleted, the second item of the pair specifies
        its new low value or null.  If the node is to be deleted, the second 
        item is always null unless the deleted node is the first node of the 
        parent.  In this latter case, a non-null value is the correct low 
        value for the second child.  A null value indicates the ancestor already has
        the correct value, unless the deletion node is leaf. <br>
        Analysis : O(h*order) + O(h) file reads and writes,
            where h = the height of the tree rooted at this node. 
        @param itemKey The key of the item to delete */
    public PairUos delete(Comparable itemKey, BtreeFileUos treeHeader) 
    {
        int deletionIndex = obtainIndex(itemKey);
        BtreeNodeUos deletionChild = child(deletionIndex);
        PairUos pair = deletionChild.delete(itemKey, treeHeader);

        if (((Boolean)pair.firstItem()).booleanValue())
        {
            /* The deletion child needs to be deleted */
            Comparable newKeyForParent; 
            if (deletionIndex == 1)
                if (deletionChild instanceof BtreeLeafUos)
                    newKeyForParent = getKey(2);
                else
                    /* One or more children of child 1 have been moved to child 2.
                       The low value for this node is the low value of one of these moved
                       children.  The second item of the pair indicates whether the parent
                       key needs to be updated or not. */
                    newKeyForParent = (Comparable)pair.secondItem();
            else
                newKeyForParent = null; 

            shuffleChildrenLeft(deletionIndex+1);
            childCount--;  

            if (childCount == 0) 
            {
                nodeFile.recoverNodeAddress(fileAddress());
                return new PairUos(new Boolean(true), null);
            }
            else if ((childCount >= order + 1) | (parent == null))
            {
                nodeFile.writeNode(this);
                return new PairUos(new Boolean(false), newKeyForParent);
            }
            else 
            {
                BtreeInteriorUos sibling = adjacentSibling();   
                if (sibling.childCount > order + 1) 
                {
                    /* Sibling can spare a child */
                    long newFileAddress;
                    if (fileAddress() == parent.getChildFileAddress(parent.childCount))
                    {
                        /* `this' is the last child of the parent, so sibling on the left */
                        newFileAddress = sibling.getChildFileAddress(sibling.childCount);     
                        sibling.putChildFileAddress(0, sibling.childCount);
                        /* Update my key in parent for use by suffleChildrenRight.
                           It will be overwritten later by the last key of sibling. */
                        if (newKeyForParent != null)
                            parent.putKey(newKeyForParent, parent.childCount);
                        newKeyForParent = sibling.getKey(sibling.childCount);
                        sibling.putKey(null, sibling.childCount);
                        sibling.setChildCount(sibling.childCount - 1);
                        nodeFile.writeNode(sibling);
                        shuffleChildrenRight(1);
                        putChildFileAddress(newFileAddress, 1);           
                        child(1).setParent(this);
                        childCount = childCount + 1;
                        nodeFile.writeNode(this);
                        return new PairUos(new Boolean(false), newKeyForParent);
                    }
                    else
                    {
                        /* The sibling is on the right. */
                        newFileAddress = sibling.getChildFileAddress(1);
                        /* The low key for the child that `this' is taking
                           is the key of the parent for the sibling */
                        int newKeyIndex = parent.indexOfAddress(sibling.fileAddress());
                        Comparable newKey = parent.getKey(newKeyIndex);
                        parent.putKey(sibling.getKey(2), newKeyIndex);
                        nodeFile.writeNode(parent);
                        sibling.shuffleChildrenLeft(2);
                        sibling.setChildCount(sibling.childCount - 1);
                        nodeFile.writeNode(sibling);
                        putChildFileAddress(newFileAddress, childCount + 1);
                        putKey(newKey, childCount + 1);
                        childCount = childCount + 1;
                        child(childCount).setParent(this);
                        nodeFile.writeNode(this);
                        return new PairUos(new Boolean(false), newKeyForParent);
                    }
                }
                else
                {
                    /* Sibling has no children to spare so give it mine */
                    /* Update my key in parent for use by appendChildren and prependChildren */
                    int indexInParent = parent.indexOfAddress(fileAddress());
                    if (newKeyForParent != null & indexInParent != 1)
                    {
                        parent.putKey(newKeyForParent, indexInParent);
                        newKeyForParent = null;
                    }
                    /* When indexInParent == 1, newKeyForParent is passed to the parent
                       where it can be used to update the key in the grandparent. */
                       
                    if (indexInParent == parent.childCount)
                    {
                        /* this node is last child of parent, and sibling is on left */
                        sibling.appendChildren(this);    
                    } 
                    else
                    {
                        /* Sibling is on the right */
                        sibling.prependChildren(this);
                    }

                    childCount = 0;
                    nodeFile.recoverNodeAddress(fileAddress());
                    return new PairUos(new Boolean(true), newKeyForParent);           
                }
            }
        }
        else
        {
            /* Although the child need not be deleted, there might be a new key 
                value for the child */
            if (deletionIndex > 1)
            {
                if (pair.secondItem()!=null)
                {
                    putKey((Comparable)pair.secondItem(), deletionIndex);
                    nodeFile.writeNode(this);
                }
                return new PairUos(new Boolean(false), null);
            }
            else
                return pair;
        }
    }


    /** Returns a string representation of the node. <br>
        Analysis : Time = O(childCount) */
    public String toString()
    {
        String result = "";
        for (int i = 1; i <= childCount; i++)
            result += child(i);
        return result;
    }
    
    /** Returns a string representation of the complete node. <br>
        Analysis : Time = O(order) */
    public String toStringComplete()
    {
        String result = "";
        for (int i = 1; i <= 2*order+1; i++)
        {
            result += "\n          " + getChildFileAddress(i);
            if (i < 2*order+1)
                if (getKey(i+1) != null)
                    result += "\n" + getKey(i+1);
                else
                    result += "\nnull";
        }
        return result;
    }
    
    /** Return a string representation of the node with the proper indentation. <br>
        Analysis: Time = O(h*order), where h = the height of the tree rooted at this node. */   
    public String formatToString(int index, String indentation)
    {
        String result = "\n" +indentation + index+ ":" + "Internal : ";
        String nextindentation = indentation + "        ";
        
        for (int i = 1; i <= 2*order+1; i++)
        {
            result +="  Adr:  "+ getChildFileAddress(i) + "   ";
            if (i < 2*order+1)
                if (getKey(i+1) !=null)
                    result += "Key:  "+ getKey(i+1);
                else
                    result += "Key:  null";
        }
        
        for (int i =1; i <= childCount; i++)
        {
            result += child(i).formatToString(i, nextindentation);
        }
        return result;  
    }
 
    /** Shift the children one position left starting from startIndex,
        without attempting to save a possible low value. <br>
        Analysis : Time = O(childCount - startIndex)
        @param startIndex The index where shuffling will start */
    private void shuffleChildrenLeft(int startIndex)
    {
        /* Should have precondition startIndex >= 2 */
        for (int i = startIndex; i <= childCount; i++)
        {  
            putChildFileAddress(getChildFileAddress(i), i-1);
            if (i > 2) 
                putKey(getKey(i), i-1);
        }
        putChildFileAddress(0, childCount);
        putKey(null, childCount);
    } 

    /** Shift the children one position right starting from startIndex,
        using key in parent if necessary. <br>
        Analysis : Time = O(childCount - startIndex) 
        @param startIndex The index where shuffling will start */
    public void shuffleChildrenRight(int startIndex) 
    {
        /* Should have precondition childCount < 2*order+1 */
        for (int i = childCount; i >= startIndex; i--)
        { 
            putChildFileAddress(getChildFileAddress(i), i+1);

            if (i > 1)
                putKey(getKey(i), i+1); 
            else 
            {
                int indexInParent = parent.indexOfAddress(fileAddress());
                putKey(parent.getKey(indexInParent), 2);
            }
        }
    }

    /** Append the children of node onto the end of the children of this.  This 
        includes copying over key values and saving this node to disk. 
        Note that node is always the right sibling, whose key in parent is used. <br>
        Analysis : Time = O(node.childCount) + 1 file write and read. 
        @param node The node that children will be taken from */
    public void appendChildren(BtreeInteriorUos node)
    {
        int myIndex = childCount + 1;
        for (int nodeIndex = 1; nodeIndex <= node.childCount; nodeIndex++)
        {    
            putChildFileAddress(node.getChildFileAddress(nodeIndex), myIndex);
            child(myIndex).setParent(this);
            if (nodeIndex == 1) 
            {
                int indexInParent = parent.indexOfAddress(node.fileAddress());
                putKey(parent.getKey(indexInParent), myIndex);
            }
            else
                putKey(node.getKey(nodeIndex), myIndex); 
            
            myIndex++; 
        }
        childCount = childCount + node.childCount;
        nodeFile.writeNode(this);
    }
 
    /** Prepend the children of node to the children of this.  This includes 
        copying over the key values.  Node is always the left sibling, whose
        key value in parent is used, if it exists.  Also, a new key value
        is placed in the parent for the current node. <br>
        Analysis : Time = O(childCount) + 1 file read and one write.
        @param node The node that children will be taken from */
    public void prependChildren(BtreeInteriorUos node)
    {
        /* node is to be removed so assign its arrays to this, after saving the current contents. */
        long[] oldChildAddress = childFileAddress;
        Comparable[] oldKeys = keys;
        int oldChildCount = childCount;
      
        childFileAddress = node.childFileAddress;
        keys = node.keys;
        childCount = node.childCount;
        for (int i = 1; i <= childCount; i++)
            child(i).setParent(this);
            
        int indexInNew = childCount + 1;
        for (int indexInOld=1; indexInOld<=oldChildCount; indexInOld++)
        { 
            /* Need to use offset of -1 in oldChildAddess and -2 in oldKeys. */
            putChildFileAddress(oldChildAddress[indexInOld-1], indexInNew);
            if (indexInOld == 1)
            {
                int indexInParent = parent.indexOfAddress(fileAddress());
                putKey(parent.getKey(indexInParent), indexInNew);
                if (indexInParent > 2)
                    parent.putKey(parent.getKey(indexInParent-1), indexInParent);
                /* if (indexParent=2) parent.getKey(2) is handled in invoking method. */
            }
            else
                putKey(oldKeys[indexInOld-2], indexInNew);
                 
            indexInNew++;
        }
        childCount = oldChildCount + childCount;
        nodeFile.writeNode(this);   
    }

    /** Return a child of the parent that is adjacent to this node. <br> 
        Analysis : Time = O(childCount) + 1 file read. */
    public BtreeInteriorUos adjacentSibling()
    {
        if (parent == null) 
            return null;
        else
        {    
            int indexInParent = parent.indexOfAddress(fileAddress());
            if (indexInParent == parent.childCount)
                return (BtreeInteriorUos) parent.child(indexInParent-1);
            else
                return (BtreeInteriorUos) parent.child(indexInParent+1);        
        }
    }

    /** Return the index within the childFileAddress array where the address compAddress 
        exists.  It returns 0 if the address is not in the address array. <br>
        Analysis: Time = O(childCount)
        @param compAddress The address being sought */
    public int indexOfAddress(long compAddress) 
    {
        int result;
        for (result=1; (result <= childCount) && (getChildFileAddress(result) != compAddress); result++);
        return result;
    }
    
    /** The smallest key value of the tree.  If the correct key is not stored 
        for a child in this node or a descendant node throw an exception. <br>
        Analysis : Time = O(n) file reads, n = number of descendant nodes */
    protected Object minOfValidTree()
    {
        Object result = child(1).minOfValidTree();
        for (int i=2; i <= childCount; i++)
            if (!getKey(i).equals(child(i).minOfValidTree()))
                throw new RuntimeException("Error in structure of the Btree");
        return result;
    }
}