binarytree.java

Office格式转换代码

                                                                    == node.getParent(
                                                                        index).getLeft(
                                                                        index)));
    }

    /**
     * is this node its parent's right child? mind you, the node, or
     * its parent, may not exist. no problem. if the node doesn't
     * exist ... it's its non-existent parent's right child. If the
     * node does exist but has no parent ... no, we're not the
     * non-existent parent's right child. Otherwise (both the
     * specified node AND its parent exist), check.
     *
     * @param node the node (may be null) in question
     * @param index _KEY or _VALUE
     */

    private static boolean isRightChild(final Node node, final int index)
    {
        return (node == null) ? true
                              : ((node.getParent(index) == null) ? false
                                                                 : (node
                                                                    == node.getParent(
                                                                        index).getRight(
                                                                        index)));
    }

    /**
     * do a rotate left. standard fare in the world of balanced trees
     *
     * @param node the node to be rotated
     * @param index _KEY or _VALUE
     */

    private void rotateLeft(final Node node, final int index)
    {
        Node right_child = node.getRight(index);

        node.setRight(right_child.getLeft(index), index);
        if (right_child.getLeft(index) != null)
        {
            right_child.getLeft(index).setParent(node, index);
        }
        right_child.setParent(node.getParent(index), index);
        if (node.getParent(index) == null)
        {

            // node was the root ... now its right child is the root
            _root[ index ] = right_child;
        }
        else if (node.getParent(index).getLeft(index) == node)
        {
            node.getParent(index).setLeft(right_child, index);
        }
        else
        {
            node.getParent(index).setRight(right_child, index);
        }
        right_child.setLeft(node, index);
        node.setParent(right_child, index);
    }

    /**
     * do a rotate right. standard fare in the world of balanced trees
     *
     * @param node the node to be rotated
     * @param index _KEY or _VALUE
     */

    private void rotateRight(final Node node, final int index)
    {
        Node left_child = node.getLeft(index);

        node.setLeft(left_child.getRight(index), index);
        if (left_child.getRight(index) != null)
        {
            left_child.getRight(index).setParent(node, index);
        }
        left_child.setParent(node.getParent(index), index);
        if (node.getParent(index) == null)
        {

            // node was the root ... now its left child is the root
            _root[ index ] = left_child;
        }
        else if (node.getParent(index).getRight(index) == node)
        {
            node.getParent(index).setRight(left_child, index);
        }
        else
        {
            node.getParent(index).setLeft(left_child, index);
        }
        left_child.setRight(node, index);
        node.setParent(left_child, index);
    }

    /**
     * complicated red-black insert stuff. Based on Sun's TreeMap
     * implementation, though it's barely recognizeable any more
     *
     * @param inserted_node the node to be inserted
     * @param index _KEY or _VALUE
     */

    private void doRedBlackInsert(final Node inserted_node, final int index)
    {
        Node current_node = inserted_node;

        makeRed(current_node, index);
        while ((current_node != null) && (current_node != _root[ index ])
                && (isRed(current_node.getParent(index), index)))
        {
            if (isLeftChild(getParent(current_node, index), index))
            {
                Node y = getRightChild(getGrandParent(current_node, index),
                                       index);

                if (isRed(y, index))
                {
                    makeBlack(getParent(current_node, index), index);
                    makeBlack(y, index);
                    makeRed(getGrandParent(current_node, index), index);
                    current_node = getGrandParent(current_node, index);
                }
                else
                {
                    if (isRightChild(current_node, index))
                    {
                        current_node = getParent(current_node, index);
                        rotateLeft(current_node, index);
                    }
                    makeBlack(getParent(current_node, index), index);
                    makeRed(getGrandParent(current_node, index), index);
                    if (getGrandParent(current_node, index) != null)
                    {
                        rotateRight(getGrandParent(current_node, index),
                                    index);
                    }
                }
            }
            else
            {

                // just like clause above, except swap left for right
                Node y = getLeftChild(getGrandParent(current_node, index),
                                      index);

                if (isRed(y, index))
                {
                    makeBlack(getParent(current_node, index), index);
                    makeBlack(y, index);
                    makeRed(getGrandParent(current_node, index), index);
                    current_node = getGrandParent(current_node, index);
                }
                else
                {
                    if (isLeftChild(current_node, index))
                    {
                        current_node = getParent(current_node, index);
                        rotateRight(current_node, index);
                    }
                    makeBlack(getParent(current_node, index), index);
                    makeRed(getGrandParent(current_node, index), index);
                    if (getGrandParent(current_node, index) != null)
                    {
                        rotateLeft(getGrandParent(current_node, index),
                                   index);
                    }
                }
            }
        }
        makeBlack(_root[ index ], index);
    }

    /**
     * complicated red-black delete stuff. Based on Sun's TreeMap
     * implementation, though it's barely recognizeable any more
     *
     * @param deleted_node the node to be deleted
     */

    private void doRedBlackDelete(final Node deleted_node)
    {
        for (int index = _MINIMUM_INDEX; index < _INDEX_COUNT; index++)
        {

            // if deleted node has both left and children, swap with
            // the next greater node
            if ((deleted_node.getLeft(index) != null)
                    && (deleted_node.getRight(index) != null))
            {
                swapPosition(nextGreater(deleted_node, index), deleted_node,
                             index);
            }
            Node replacement = ((deleted_node.getLeft(index) != null)
                                ? deleted_node.getLeft(index)
                                : deleted_node.getRight(index));

            if (replacement != null)
            {
                replacement.setParent(deleted_node.getParent(index), index);
                if (deleted_node.getParent(index) == null)
                {
                    _root[ index ] = replacement;
                }
                else if (deleted_node
                         == deleted_node.getParent(index).getLeft(index))
                {
                    deleted_node.getParent(index).setLeft(replacement, index);
                }
                else
                {
                    deleted_node.getParent(index).setRight(replacement,
                                           index);
                }
                deleted_node.setLeft(null, index);
                deleted_node.setRight(null, index);
                deleted_node.setParent(null, index);
                if (isBlack(deleted_node, index))
                {
                    doRedBlackDeleteFixup(replacement, index);
                }
            }
            else
            {

                // replacement is null
                if (deleted_node.getParent(index) == null)
                {

                    // empty tree
                    _root[ index ] = null;
                }
                else
                {

                    // deleted node had no children
                    if (isBlack(deleted_node, index))
                    {
                        doRedBlackDeleteFixup(deleted_node, index);
                    }
                    if (deleted_node.getParent(index) != null)
                    {
                        if (deleted_node
                                == deleted_node.getParent(index)
                                    .getLeft(index))
                        {
                            deleted_node.getParent(index).setLeft(null,
                                                   index);
                        }
                        else
                        {
                            deleted_node.getParent(index).setRight(null,
                                                   index);
                        }
                        deleted_node.setParent(null, index);
                    }
                }
            }
        }
        shrink();
    }

    /**
     * complicated red-black delete stuff. Based on Sun's TreeMap
     * implementation, though it's barely recognizeable any more. This
     * rebalances the tree (somewhat, as red-black trees are not
     * perfectly balanced -- perfect balancing takes longer)
     *
     * @param replacement_node  the node being replaced
     * @param index _KEY or _VALUE
     */

    private void doRedBlackDeleteFixup(final Node replacement_node,
                                       final int index)
    {
        Node current_node = replacement_node;

        while ((current_node != _root[ index ])
                && (isBlack(current_node, index)))
        {
            if (isLeftChild(current_node, index))
            {
                Node sibling_node =
                    getRightChild(getParent(current_node, index), index);

                if (isRed(sibling_node, index))
                {
                    makeBlack(sibling_node, index);
                    makeRed(getParent(current_node, index), index);
                    rotateLeft(getParent(current_node, index), index);
                    sibling_node =
                        getRightChild(getParent(current_node, index), index);
                }
                if (isBlack(getLeftChild(sibling_node, index), index)
                        && isBlack(getRightChild(sibling_node, index), index))
                {
                    makeRed(sibling_node, index);
                    current_node = getParent(current_node, index);
                }
                else
                {
                    if (isBlack(getRightChild(sibling_node, index), index))
                    {
                        makeBlack(getLeftChild(sibling_node, index), index);
                        makeRed(sibling_node, index);
                        rotateRight(sibling_node, index);
                        sibling_node =
                            getRightChild(getParent(current_node, index),
                                          index);
                    }
                    copyColor(getParent(current_node, index), sibling_node,
                              index);
                    makeBlack(getParent(current_node, index), index);
                    makeBlack(getRightChild(sibling_node, index), index);
                    rotateLeft(getParent(current_node, index), index);
                    current_node = _root[ index ];
                }
            }
            else
            {
                Node sibling_node =
                    getLeftChild(getParent(current_node, index), index);

                if (isRed(sibling_node, index))
                {
                    makeBlack(sibling_node, index);
                    makeRed(getParent(current_node, index), index);
                    rotateRight(getParent(current_node, index), index);
                    sibling_node =
                        getLeftChild(getParent(current_node, index), index);
                }
                if (isBlack(getRightChild(sibling_node, index), index)
                        && isBlack(getLeftChild(sibling_node, index), index))
                {
                    makeRed(sibling_node, index);
                    current_node = getParent(current_node, index);
                }
                else
                {
                    if (isBlack(getLeftChild(sibling_node, index), index))
                    {
                        makeBlack(getRightChild(sibling_node, index), index);
                        makeRed(sibling_node, index);
                        rotateLeft(sibling_node, index);
                        sibling_node =
                            getLeftChild(getParent(current_node, index),
                                         index);
                    }
                    copyColor(getParent(current_node, index), sibling_node,
                              index);
                    makeBlack(getParent(current_node, index), index);
                    makeBlack(getLeftChild(sibling_node, index), index);
                    rotateRight(getParent(current_node, index), index);
                    current_node = _root[ index ];
                }
            }
        }
        makeBlack(current_node, index);
    }

    /**
     * swap two nodes (except for their content), taking care of
     * special cases where one is the other's parent ... hey, it
     * happens.
     *
     * @param x one node
     * @param y another node
     * @param index _KEY or _VALUE
     */

    private void swapPosition(final Node x, final Node y, final int index)
    {

        // Save initial values.
        Node    x_old_parent      = x.getParent(index);
        Node    x_old_left_child  = x.getLeft(index);
        Node    x_old_right_child = x.getRight(index);
        Node    y_old_parent      = y.getParent(index);
        Node    y_old_left_child  = y.getLeft(index);
        Node    y_old_right_child = y.getRight(index);
        boolean x_was_left_child  =
            (x.getParent(index) != null)
            && (x == x.getParent(index).getLeft(index));
        boolean y_was_left_child  =
            (y.getParent(index) != null)
            && (y == y.getParent(index).getLeft(index));

        // Swap, handling special cases of one being the other's parent.
        if (x == y_old_parent)
        {   // x was y's parent
            x.setParent(y, index);
            if (y_was_left_child)