private void findInsert ( InsertNodes point , InsertStack stack , Object new1 ) { java . util . Comparator comp = insertComparator ( ) ; NodeInsertPoint ip = stack . nodeInsertPoint ( ) ; GBSNode p ; /* P is used to march down the tree */ int xcc ; /* Compare result */ GBSNode l_last = null ; /* Node from which we last departed by */ /* turning left (logical successor) */ GBSNode r_last = null ; /* Node from which we last departed by */ /* turning right (logical predecessor) */ p = root ( ) ; /* Root of tree */ /* Remember father of root */ stack . start ( dummyTopNode ( ) , "GBSTree.findInsert" ) ; for ( ; ; ) /* Through the whole tree */ { xcc = comp . compare ( new1 , p . middleKey ( ) ) ; if ( ! ( xcc > 0 ) ) /* New key <= node key */ { GBSNode leftChild = p . leftChild ( ) ; if ( leftChild != null ) /* Have a left child */ { l_last = p ; /* Remember node from which we */ /* last moved left (successor) */ stack . balancedPush ( NodeStack . PROCESS_CURRENT , p ) ; p = leftChild ; /* Move left */ } else /* Have no left child */ { leftAdd ( /* Add a left child */ p , /* Current node */ r_last , /* Node from which we last turned right */ new1 , /* Key to add */ ip , /* NodeInsertPoint */ point ) ; /* Returned InsertNodes */ break ; } } else /* New key > node key */ { GBSNode rightChild = p . rightChild ( ) ; if ( rightChild != null ) /* There is a right child */ { r_last = p ; /* Remember node from which we */ /* last moved right (predecessor) */ stack . balancedPush ( NodeStack . DONE_VISITS , p ) ; p = rightChild ; /* Move right */ } else /* There is no right child */ { rightAdd ( /* Add a right child */ p , /* Current node */ l_last , /* Node from which we last turned left */ new1 , /* Key to add */ ip , /* NodeInsertPoint */ point ) ; /* Returned InsertNodes */ break ; } } } // for }
Find the insert point within the tree .