\Head{}
\L{\LB{\Proc{NewNode}\K{function} NewNode\(k$1$ {\DP} typekey{\PC} p$0${\CO} p$1$ {\DP} btree\) {\DP} btree{\PC}}}
\L{\LB{}}
\L{\LB{\K{var} t {\DP} btree{\PC}}}
\L{\LB{\K{begin}}}
\L{\LB{     new\(t\){\PC}}}
\L{\LB{     t\^.p\[$0$\] {\DP}\= p$0${\PC}}}
\L{\LB{     t\^.p\[$1$\] {\DP}\= p$1${\PC}}}
\L{\LB{     t\^.k\[$1$\] {\DP}\= k$1${\PC}}}
\L{\LB{     t\^.d {\DP}\= $1${\PC}}}
\L{\LB{     NewNode {\DP}\= t}}
\L{\LB{\K{end}{\PC}}}
\L{\LB{}}
\L{\LB{\Proc{insert}\K{procedure} insert\(key {\DP} typekey{\PC} \K{var} t {\DP} btree\){\PC}}}
\L{\LB{}}
\L{\LB{\K{var}  ins {\DP} typekey{\PC}}}
\L{\LB{     NewTree {\DP} btree{\PC}}}
\L{\LB{}}
\L{\LB{\Proc{InternalInsert}   \K{function} InternalInsert\(t {\DP} btree\) {\DP} typekey{\PC}}}
\L{\LB{   \K{var}  i{\CO} j {\DP} integer{\PC}}}
\L{\LB{        ins {\DP} typekey{\PC}}}
\L{\LB{        tempr {\DP} btree{\PC}}}
\L{\LB{   \K{begin}}}
\L{\LB{   \K{if} t\=\K{nil} \K{then} \K{begin} \C{}\{\*\*\* The bottom of the tree has been reached{\DP}}}
\L{\LB{                            indicate insertion to be done \*\*\*\}\CE{}}}
\L{\LB{        InternalInsert {\DP}\= key{\PC}}}
\L{\LB{        NewTree {\DP}\= \K{nil}}}
\L{\LB{   \K{end}}}
\L{\LB{   \K{else} \K{with} t\^ \K{do} \K{begin}}}
\L{\LB{        InternalInsert {\DP}\= NoKey{\PC}}}
\L{\LB{        i {\DP}\= $1${\PC}}}
\L{\LB{        \K{while} \(i\<d\) \K{and} \(key\>k\[i\]\) \K{do}     i {\DP}\= i\+$1${\PC}}}
\L{\LB{        \K{if} key \= k\[i\] \K{then}}}
\L{\LB{             Error \C{}\{\*\*\* Key already in table \*\*\*\}\CE{}}}
\L{\LB{        \K{else} \K{begin}}}
\L{\LB{             \K{if} key \> k\[i\] \K{then} i {\DP}\= i\+$1${\PC}}}
\L{\LB{             ins {\DP}\= InternalInsert\(p\[i\-$1$\]\){\PC}}}
\L{\LB{             \K{if} ins \<\> NoKey \K{then}}}
\L{\LB{             \C{}\{\*\*\* the key in \"ins\" has to be inserted in present node \*\*\*\}\CE{}}}
\L{\LB{                  \K{if} d\<$2$\*M \K{then}     InsInNode\(t{\CO} ins{\CO} NewTree\)}}
\L{\LB{                  \K{else}     \C{}\{\*\*\* Present node has to be split \*\*\*\}\CE{}}}
\L{\LB{                  \K{begin}}}
\L{\LB{                    \C{}\{\*\*\* Create new node \*\*\*\}\CE{}}}
\L{\LB{                    \K{if} i\<\=M\+$1$ \K{then} \K{begin}}}
\L{\LB{                        tempr {\DP}\= NewNode\(k\[$2$\*M\]{\CO} \K{nil}{\CO} p\[$2$\*M\]\){\PC}}}
\L{\LB{                        d {\DP}\= d\-$1${\PC}}}
\L{\LB{                        InsInNode\(t{\CO} ins{\CO} NewTree\)}}
\L{\LB{                    \K{end}}}
\L{\LB{                    \K{else} tempr {\DP}\= NewNode\(ins{\CO} \K{nil}{\CO} NewTree\){\PC}}}
\L{\LB{                    \C{}\{\*\*\* move keys and pointers \*\*\*\}\CE{}}}
\L{\LB{                    \K{for} j{\DP}\=M\+$2$ \K{to} $2$\*M \K{do}}}
\L{\LB{                         InsInNode\(tempr{\CO} k\[j\]{\CO} p\[j\]\){\PC}}}
\L{\LB{                    d {\DP}\= M{\PC}}}
\L{\LB{                    tempr\^.p\[$0$\] {\DP}\= p\[M\+$1$\]{\PC}}}
\L{\LB{                    InternalInsert {\DP}\= k\[M\+$1$\]{\PC}}}
\L{\LB{                    NewTree {\DP}\= tempr}}
\L{\LB{                  \K{end}}}
\L{\LB{             \K{end}}}
\L{\LB{        \K{end}}}
\L{\LB{   \K{end}{\PC}}}
\ProcCont{insert}\L{\LB{}}
\L{\LB{\K{begin}}}
\L{\LB{     ins {\DP}\= InternalInsert\(t\){\PC}}}
\L{\LB{     \C{}\{\*\*\* check for growth at the root \*\*\*\}\CE{}}}
\L{\LB{     \K{if} ins \<\> NoKey \K{then} t {\DP}\= NewNode\(ins{\CO} t{\CO} NewTree\)}}
\L{\LB{\K{end}{\PC}}}
