CNode::Insert ( S )
 
I'm using the Hungarian notation by which a member variable starts with "m_". 
A CNode has member variables:

m_Key, which is a string;
m_Parent, which is a pointer to a CNode;

and a hash that takes a char and returns a pointer to a daughter node (or the equivalent).



    i = 0;
    while ( i <= length( m_Key) and  i <= length(S)  )
	{
		Case 1: m_Key[i] != S[i]
		{	
			For example,  m_Key = jumps and S = jumping
			
			1. Create a new node pNode whose key is "jump" --
				that is, its key is m_Key.Left(i);

			2. pNode's parent is this->Parent;

			3. pNode has a downward pointer to this through the letter 's',
				which is m_Key[i];

			4. Create a new node qNode whose key is the rest of
				string S, "ing".

			5. pNode has a downward pointer to qNode through the letter 'i',
				which is S[i];

			6. return the message that a new word was added.

		}

		Case 2:S is shorter than  (this's) m_Key
		that is, i == Length (S) && i < Length (m_Key)
		For example, this's m_Key is "jumping" and S = "jump"
		{
			1. We create a new node, pNode, whose m_Key is "S" = "jump"
				and place it above this in the trie.
				pNode->Parent = this->Parent;
				this->Parent  = pNode;

			2. Change this->m_Key to "ing" - -
				its length is Length (m_Key) - Length (S),
				and it is the end of m_Key: "ing" in this case.

			3. return the message that a new word was added.

		}


		Case 3: S is exactly this's m_Key
		that is, m_Key = S (character by character comparison)
		{
			1. if the node did not represent a terminal node before,
				then it does now; and return the message that a new
				word was found.

			2. otherwise, return the message that an old word was found.

		}



		Now, S agrees with m_Key as far as m_Key goes, but S is longer.
			
			
			
		i is now equal to the length of m_Key, and 
		Letter = S[i] is the NEXT letter.
		If m_Key = JUMP and S = JUMPING, then Letter = I.

		Is there a downward pointer from this based on Letter?
	
		if there is one, then it points to rNode:
		{
			1. NewString = S.Mid (i);
			rNode->Insert (NewString) and the pointer it returns is qNode:
			"qNode = rNode->Insert (NewString)" 

			!! Danger -- This function returns a pointer to the node that 
			should be "on top" -- that is, the root of the sub-trie. This 
			is likely to be rNode, but it may not be. If it's not rNode, then
			we have to rearrange the pointer on this so it no longer points to rNode,
			but rather to the new qNode.  !!

			Why would this happen? Suppose this = construct, and it has 
			a pointer based on "i" that points to a node (rNode) whose key is "ion" (for
			the word "construction").

			Now we want to insert "constructing".

			When we pass to rNode->Insert(ing), it will create a new node whose
			key is "i". This is our new qNode, and this has to point now to qNode, not rNode.
	
			return message that an new word was added.

		}

		else there wasn't a pointer,
			so we create a new Node under this whose key is S.Mid(i),
			and return the message that a new word was found.









 } end of Big While loop