btreeset.java

Office格式转换代码

            // If not root and can't steal left or right and can't merge left you must be able to merge right
            else mergeRight(parentIndex);
        }

        private void fixAfterDeletion(int parentIndex)
        {
            if (isRoot() || parent.isRoot()) return; // No fixing needed

            if (parent.nrElements < MIN)
            { // If parent lost it's n/2 element repair it
                BTreeNode temp = parent;
                temp.prepareForDeletion(parentIndex);
                if (temp.parent == null) return; // Root changed
                if (!temp.parent.isRoot() && temp.parent.nrElements < MIN)
                { // If need be recurse
                    BTreeNode x = temp.parent.parent;
                    int i = 0;
                    // Find parent's parentIndex
                    for (; i < entries.length; i++) if (x.entries[i].child == temp.parent) break;
                    temp.parent.fixAfterDeletion(i);
                }
            }
        }

        private void switchWithSuccessor(Object x)
        {
            int index = childToInsertAt(x, false);
            BTreeNode temp = entries[index + 1].child;
            while (temp.entries[0] != null && temp.entries[0].child != null) temp = temp.entries[0].child;
            Object successor = temp.entries[0].element;
            temp.entries[0].element = entries[index].element;
            entries[index].element = successor;
        }

        /*
         * This method is called only when the BTreeNode has the minimum number of elements,
         * has a leftSibling, and the leftSibling has more than the minimum number of elements.
        */
        private void stealLeft(int parentIndex)
        {
            BTreeNode p = parent;
            BTreeNode ls = parent.entries[parentIndex - 1].child;

            if (isLeaf())
            { // When stealing from leaf to leaf don't worry about children
                int add = childToInsertAt(p.entries[parentIndex - 1].element, true);
                insertNewElement(p.entries[parentIndex - 1].element, add);
                p.entries[parentIndex - 1].element = ls.entries[ls.nrElements - 1].element;
                ls.entries[ls.nrElements - 1] = null;
                ls.nrElements--;
            }

            else
            { // Was called recursively to fix an undermanned parent
                entries[0].element = p.entries[parentIndex - 1].element;
                p.entries[parentIndex - 1].element = ls.entries[ls.nrElements - 1].element;
                entries[0].child = ls.entries[ls.nrElements].child;
                entries[0].child.parent = this;
                ls.entries[ls.nrElements] = null;
                ls.entries[ls.nrElements - 1].element = null;
                nrElements++;
                ls.nrElements--;
            }
        }

        /*
         * This method is called only when stealLeft can't be called, the BTreeNode
         * has the minimum number of elements, has a rightSibling, and the rightSibling
         * has more than the minimum number of elements.
        */
        private void stealRight(int parentIndex)
        {
            BTreeNode p = parent;
            BTreeNode rs = p.entries[parentIndex + 1].child;

            if (isLeaf())
            { // When stealing from leaf to leaf don't worry about children
                entries[nrElements] = new Entry();
                entries[nrElements].element = p.entries[parentIndex].element;
                p.entries[parentIndex].element = rs.entries[0].element;
                for (int i = 0; i < rs.nrElements; i++) rs.entries[i] = rs.entries[i + 1];
                rs.entries[rs.nrElements - 1] = null;
                nrElements++;
                rs.nrElements--;
            }

            else
            { // Was called recursively to fix an undermanned parent
                for (int i = 0; i <= nrElements; i++) entries[i] = entries[i + 1];
                entries[nrElements].element = p.entries[parentIndex].element;
                p.entries[parentIndex].element = rs.entries[0].element;
                entries[nrElements + 1] = new Entry();
                entries[nrElements + 1].child = rs.entries[0].child;
                entries[nrElements + 1].child.parent = this;
                for (int i = 0; i <= rs.nrElements; i++) rs.entries[i] = rs.entries[i + 1];
                rs.entries[rs.nrElements] = null;
                nrElements++;
                rs.nrElements--;
            }
        }

        /*
         * This method is called only when stealLeft and stealRight could not be called,
         * the BTreeNode has the minimum number of elements, has a leftSibling, and the
         * leftSibling has more than the minimum number of elements.  If after completion
         * parent has fewer than the minimum number of elements than the parents entries[0]
         * slot is left empty in anticipation of a recursive call to stealLeft, stealRight,
         * mergeLeft, or mergeRight to fix the parent. All of the before-mentioned methods
         * expect the parent to be in such a condition.
        */
        private void mergeLeft(int parentIndex)
        {
            BTreeNode p = parent;
            BTreeNode ls = p.entries[parentIndex - 1].child;

            if (isLeaf())
            { // Don't worry about children
                int add = childToInsertAt(p.entries[parentIndex - 1].element, true);
                insertNewElement(p.entries[parentIndex - 1].element, add); // Could have been a successor switch
                p.entries[parentIndex - 1].element = null;

                for (int i = nrElements - 1, nr = ls.nrElements; i >= 0; i--)
                    entries[i + nr] = entries[i];

                for (int i = ls.nrElements - 1; i >= 0; i--)
                {
                    entries[i] = ls.entries[i];
                    nrElements++;
                }

                if (p.nrElements == MIN && p != BTreeSet.this.root)
                {

                    for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x--, y--)
                        p.entries[x] = p.entries[y];
                    p.entries[0] = new Entry();
                    p.entries[0].child = ls; //So p doesn't think it's a leaf this will be deleted in the next recursive call
                }

                else
                {

                    for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++)
                        p.entries[x] = p.entries[y];
                    p.entries[p.nrElements] = null;
                }

                p.nrElements--;

                if (p.isRoot() && p.nrElements == 0)
                { // It's the root and it's empty
                    BTreeSet.this.root = this;
                    parent = null;
                }
            }

            else
            { // I'm not a leaf but fixing the tree structure
                entries[0].element = p.entries[parentIndex - 1].element;
                entries[0].child = ls.entries[ls.nrElements].child;
                nrElements++;

                for (int x = nrElements, nr = ls.nrElements; x >= 0; x--)
                    entries[x + nr] = entries[x];

                for (int x = ls.nrElements - 1; x >= 0; x--)
                {
                    entries[x] = ls.entries[x];
                    entries[x].child.parent = this;
                    nrElements++;
                }

                if (p.nrElements == MIN && p != BTreeSet.this.root)
                { // Push everything to the right
                    for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x++, y++)
                    {
                        System.out.println(x + " " + y);
                        p.entries[x] = p.entries[y];
                    }
                    p.entries[0] = new Entry();
                }

                else
                { // Either p.nrElements > MIN or p == BTreeSet.this.root so push everything to the left
                    for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++)
                        p.entries[x] = p.entries[y];
                    p.entries[p.nrElements] = null;
                }

                p.nrElements--;

                if (p.isRoot() && p.nrElements == 0)
                { // p == BTreeSet.this.root and it's empty
                    BTreeSet.this.root = this;
                    parent = null;
                }
            }
        }

        /*
         * This method is called only when stealLeft, stealRight, and mergeLeft could not be called,
         * the BTreeNode has the minimum number of elements, has a rightSibling, and the
         * rightSibling has more than the minimum number of elements.  If after completion
         * parent has fewer than the minimum number of elements than the parents entries[0]
         * slot is left empty in anticipation of a recursive call to stealLeft, stealRight,
         * mergeLeft, or mergeRight to fix the parent. All of the before-mentioned methods
         * expect the parent to be in such a condition.
        */
        private void mergeRight(int parentIndex)
        {
            BTreeNode p = parent;
            BTreeNode rs = p.entries[parentIndex + 1].child;

            if (isLeaf())
            { // Don't worry about children
                entries[nrElements] = new Entry();
                entries[nrElements].element = p.entries[parentIndex].element;
                nrElements++;
                for (int i = 0, nr = nrElements; i < rs.nrElements; i++, nr++)
                {
                    entries[nr] = rs.entries[i];
                    nrElements++;
                }
                p.entries[parentIndex].element = p.entries[parentIndex + 1].element;
                if (p.nrElements == MIN && p != BTreeSet.this.root)
                {
                    for (int x = parentIndex + 1, y = parentIndex; y >= 0; x--, y--)
                        p.entries[x] = p.entries[y];
                    p.entries[0] = new Entry();
                    p.entries[0].child = rs; // So it doesn't think it's a leaf, this child will be deleted in the next recursive call
                }

                else
                {
                    for (int x = parentIndex + 1, y = parentIndex + 2; y <= p.nrElements; x++, y++)
                        p.entries[x] = p.entries[y];
                    p.entries[p.nrElements] = null;
                }

                p.nrElements--;
                if (p.isRoot() && p.nrElements == 0)
                { // It's the root and it's empty
                    BTreeSet.this.root = this;
                    parent = null;
                }
           }

           else
           { // It's not a leaf

               entries[nrElements].element = p.entries[parentIndex].element;
               nrElements++;

               for (int x = nrElements + 1, y = 0; y <= rs.nrElements; x++, y++)
               {
                   entries[x] = rs.entries[y];
                   rs.entries[y].child.parent = this;
                   nrElements++;
               }
               nrElements--;

               p.entries[++parentIndex].child = this;

               if (p.nrElements == MIN && p != BTreeSet.this.root)
               {
                  for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x--, y--)
                      p.entries[x] = p.entries[y];
                  p.entries[0] = new Entry();
               }

               else
               {
                   for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++)
                       p.entries[x] = p.entries[y];
                   p.entries[p.nrElements] = null;
               }

               p.nrElements--;

               if (p.isRoot() && p.nrElements == 0)
               { // It's the root and it's empty
                   BTreeSet.this.root = this;
                   parent = null;
               }
            }
        }
  }

}