<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 12 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
        {font-family:SimSun;
        panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
        {font-family:SimSun;
        panose-1:2 1 6 0 3 1 1 1 1 1;}
@font-face
        {font-family:Calibri;
        panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
        {font-family:SimSun;
        panose-1:2 1 6 0 3 1 1 1 1 1;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0cm;
        margin-bottom:.0001pt;
        font-size:11.0pt;
        font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
        {mso-style-priority:99;
        color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {mso-style-priority:99;
        color:purple;
        text-decoration:underline;}
span.EmailStyle17
        {mso-style-type:personal-compose;
        font-family:"Calibri","sans-serif";
        color:windowtext;}
span.apple-style-span
        {mso-style-name:apple-style-span;}
.MsoChpDefault
        {mso-style-type:export-only;}
@page WordSection1
        {size:612.0pt 792.0pt;
        margin:72.0pt 90.0pt 72.0pt 90.0pt;}
div.WordSection1
        {page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal>For non-terminal handling, I have do some experiment, the following is the general idea.<span class=apple-style-span><o:p></o:p></span></p><p class=MsoNormal>The key point for this task is to find the next node of one node, and for that we need the node path (all the ancestor nodes)<o:p></o:p></p><p class=MsoNormal>During find process, we can get the node path( typedef stack<const RBNode<T> *> NodeChain), if we got the node path, to find<o:p></o:p></p><p class=MsoNormal>The next node of node, the steps are:<o:p></o:p></p><p class=MsoNormal>(tree in following sentences means the one level tree, and the whole rbtree consists of  bunch of trees using down point connected)<o:p></o:p></p><p class=MsoNormal>If node has down tree, return the smallest(left most)node in the down tree<o:p></o:p></p><p class=MsoNormal>Otherwise, find the not null successor of node in the tree which node resides<o:p></o:p></p><p class=MsoNormal>Otherwise, find the not null successor of the top node in node chain,  if no null successor we will keep pop the node chain, until the node chain gets empty<o:p></o:p></p><p class=MsoNormal>Return null node<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Successor node of one node, is that <o:p></o:p></p><p class=MsoNormal>If node has right node, then it is the leftmost node of right node<o:p></o:p></p><p class=MsoNormal>Otherwise find the first left branch on the path to root.  If found, the parent of the branch is the successor.<o:p></o:p></p><p class=MsoNormal>Otherwise return null node.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><o:p> </o:p></p></div></body></html>