private void insertFringeMigrate ( InsertStack stack , GBSNode p , Object mkey ) { GBSNode endp = p ; int endIndex = stack . index ( ) ; /* Maximum number of right child nodes */ /* before the fringe must be rebalanced */ int maxBal = maximumFringeImbalance ( ) ; stack . setMigratingKey ( mkey ) ; if ( mkey != null ) /* Have a key to migrate */ { stack . processSubFringe ( p ) ; /* See InsertStack.processNode */ endp = stack . lastNode ( ) ; endIndex = stack . lastIndex ( ) ; } if ( stack . migrating ( ) ) /* Need a right child for migrating key */ { _xno ++ ; endp . addRightLeaf ( stack . migratingKey ( ) ) ; } insertCheckFringeBalance ( stack , endp , endIndex , maxBal ) ; }
Migrate a key from a partial leaf through to the proper place in its fringe adding a node to the right side of the fringe if necessary .