Data Structures and Algorithms Midterm Review: Week of Oct 17, 2011 !"##$%&'•! ()'!"%*+&',+-./0-+-'•! 1'#/-23%+4"+-2+5'2/.67-8'–! 9%6+-'–! ::'9%++-'–! ;"<=3>$&'9%++-'–! ,+53?<$7@'9%++-'–! :AB'9%++-'9%6+-'•! C/0-65+%'6#.<+#+0=0D'E&'$'9%6+'–! F/5+-'5/0G2'7/02$60'2H+'7H$%$72+%'I"-2'J/%'5+#/0-2%$=/0'–! ,"0=#+'/J'-+$%7H'K'–! ;+#/%&'/J'9%6+'K'9%6+-'•! L6*+0'$'567=/0$%&'M62H'M/%5-'NO:OP'O2/OP'O2+$OP'O2+5OP'O2+0OP'O6OP'O60QP'$05'O600QR'•! C/0-65+%'6#.<+#+0=0D'E&'$'?!9'–! ,"0=#+'/J'-+$%7H'K'–! ;+#/%&'/J'?!9'K'9%6+-ST0-+%2'void insert(String input, int len, tree t){ /*base case—inserting last character of input*/ if(len == 1){ if(!(t->children.contains(input.substr(0, 1)))){ //first char t->children.add(input); } return; } /*recursive call—adding node if needed and *calling insert with input as everything but the *first letter of the input *e.g. old input = dogs, new input = ogs */ if(!(t->children.contains(input.substr(0, 1)))){ t->children.add(input.substr(0, 1)); } insert(input.substr(1, len – 1), len - 1, t->children.get(input.substr(0, 1)); } ::'9%++-'U+V06=/08''WX! Y*+%&'0/5+'6-'%+5'/%'E<$7@'ZX! ,//2'6-'E<$7@')X! Y[2+%0$<'0/5+-'$%+'E<$7@'\X! TJ'$'0/5+'6-'%+5P'7H6<5%+0'#"-2'E+'E<$7@'1X! ?<$7@'H+6DH2'#"-2'E+'7/0-2$02']0"#E+%'/J'E<$7@'0/5+-'J%/#'$'0/5+'2/'$'<+$J'0/5+'6-'2H+'-$#+'%+D$%5<+--'/J'.$2HX'^X! B+_'7H6<5'7$00/2'E+'%+5'::'9%++-8'9M/'C$-+-'2H$2'F++5'C/%%+7=0D'•! !/P'&/"G%+'60-+%=0D'/%'$'0/5+'60'2H+'2%++'$-'&/"'0/%#$<<&'M/"<5'E$-+5'"./0'2H+'/%5+%60D'7/056=/0']+`D`',3a'<+--'2H$0P'B3a'D%+$2+%'2H$0X'•! >H+0'&/"'5/'2H6-'+62H+%'&/"'*6/<$2+'2H+'602+D%62&'/J'2H+'2%++'/%'&/"'5/0G2'•! TJ'&/"'UbFG9'*6/<$2+'2H+'602+D%62&P'&/"G%+'5/0+'•! >H+0'&/"'Ub'*6/<$2+'2H+'602+D%62&P'&/"G*+'#$5+'/0+'/J'2M/'7$-+-8'::'9%++'T02+D%62&'A6/<$=/0'W8'B+_'c/%6d/02$<'B60@'6`+`'$'0/5+'H$-'$'%+5'<+_'7H6<5e0+6DHE/%'F/5+'fBQ'6-'%+5'9H6-'*6/<$2+-'2H+'602+D%62&'/J'$0'::'9%++'c/M'2/'V['$',+5'B+_'CH6<5K'>62H'$0'/.+%$=/0'7$<<+5'f-@+MQ8' skew(…){ -set red left child/neighbor (L) as parent/neighbor to old parent/neighbor (T) (swap direction of pointer) -set old parent/neighbor (T)’s old parent (dotted line) to new parent/neighbor (L) as its child -set new parent/neighbor (L)’s right subtree (B) as new child/neighbor’s (T)’s left child } !"#$!"#$::'9%++'T02+D%62&'A6/<$=/0'Z8'U/"E<+',6DH2'c/%6d/02$<'B60@'•! ]6`+`'%+5'0/5+'H$-'$'%6DH2'%+5'0/5+X'!"#$ !"#$c/M'2/'V['Z'C/0-+7"=*+'],6DH2X',+5-K'!"#$ !"#$>62H'$0'/.+%$=/0'7$<<+5'f-.<62Q8' split(…){ -elevate middle red node (R) to a parent with it’s left/neighbor (T) and right/neighbor (X) as children -set old middle node’s (R) old children (B) as grandchildren (make B a child of T) } Y[$#.<+'F D H R G I X Y A C E F D H R G I X Y A C E B+*+<')'B+*+<'Z'B+*+<'W'T0-+%2''g'F D H R G I X Y A C E B+*+<')'B+*+<'Z'B+*+<'W'F D H R G I X Y A C E B+*+<')'B+*+<'Z'B+*+<'W'J T0-+%2'B'F D H R G I X Y A C E B+*+<')'B+*+<'Z'B+*+<'W'J F D H R G I X Y A C E B+*+<')'B+*+<'Z'B+*+<'W'J L T0-+%2'B'F D H R G I X Y A C E B+*+<')'B+*+<'Z'B+*+<'W'J L F D H R G I X Y A C E B+*+<')'B+*+<'Z'B+*+<'W'J L T0-+%2'B'F D H R G I X Y A C E B+*+<')'B+*+<'Z'B+*+<'W'J L F D H R G I X Y A C E B+*+<')'B+*+<'Z'B+*+<'W'J LT0-+%2'B'F D H R G I X Y A C E B+*+<')'B+*+<'Z'B+*+<'W'J L F D H R G I X Y A C E B+*+<')'B+*+<'Z'B+*+<'W'J L ::'9%++-SU+<+=0D'$'F/5+8':'<6h<+'9%67@6+%'•! U+7%+$-+'2H+'<+*+<']6J'0++5+5X'o! i605'2H+'0/5+'2/'5+<+2+j'5+<+2+'62`'o! ' 2H+'5+<+2+5'0/5+G-'.$%+02'6-'!"#'/0'<+*+<'W'$05'0/M'62'/0<&'H$-'/0+'7H6<5`'!/P'-M$.'2H+'5+<+2+5'0/5+G-'.$%+02'M62H'62G-'%+#$6060D'7H6<5'$05'#$@+'2H+'0+M'7H6<5'%+5S2H6-'%+5"7+-'2H+'/*+%$<<'2%++'2/'H$*+'/0+'J+M+%'<+*+<-'•! C$<<'-@+M'/0']MH$2'M$-'2H+'%//2S-607+'0/M'2H+%+G-'#"<=.<+'0/5+-'$2'2H+'2/.'<+*+<X'•! C$<<'-.<62'/0'2H+'0+M'%//2'2H$2'M$-'7%+$2+5'E&'-@+M'U+<+2+'C'F D H R G I X Y A E B+*+<')'B+*+<'Z'B+*+<'W'J L C F D H R G I X Y A E B+*+<')'B+*+<'Z'B+*+<'W'J L U+<+2+'U'F D H R G I X Y A E B+*+<')'B+*+<'Z'B+*+<'W'J L F E H R G I X Y A D B+*+<')'B+*+<'Z'B+*+<'W'J LU+<+2+'U'F D H R G I X Y A E B+*+<')'B+*+<'Z'B+*+<'W'J L F E H R G I X Y A B+*+<')'B+*+<'Z'B+*+<'W'J L U+<+2+'U'F E H R G I X Y A B+*+<')'B+*+<'Z'B+*+<'W'J L F E H R G I X Y A B+*+<'Z'B+*+<'W'J L U+<+2+'U'F E H R G I X Y A B+*+<'Z'B+*+<'W'J L F E H R G I X Y A B+*+<'Z'B+*+<'W'J L U+<+2+'U'F E H R G I X Y A B+*+<'Z'B+*+<'W'J L F E H R G I X Y A B+*+<'Z'B+*+<'W'J LU+<+2+'U'F E H R G I X Y A B+*+<'Z'B+*+<'W'J L F E H R G I X Y A B+*+<'Z'B+*+<'W'J L B+*+<')'Z3)'9%++-'•! 9M/'2&.+-'/J'0/5+-8'''''''''Z'F/5+ ' ''''''''''')'F/5+'Wk ')k'\k'W1 'Z1'k'1k'lk '(k'Wk ')k'T0-+%=/0'•! m/--6E<+'C$-+-8'–! T0-+%=0D'602/'Z30/5+'<+$J'•! g"-2'60-+%2'0"#E+%'Wk ')k'\k'W1 'Z1'k'Wk ')k'\k '1k'W1 'Z1'k'T0-+%=/0'•! m/--6E<+'C$-+-8'–! T0-+%=0D'602/')30/5+'<+$J'•! ;"-2'-.<62'2H+')30/5+'•! m%/#/2+'#655<+'•! TJ'.%/#/=/0'7H$0D+-'Z30/5+'2/'$')30/5+'&/"G%+'5/0+'•! b2H+%M6-+'@++.'-.<6n0D'Wk'^' W) 'W\':55'W^'Wk'^'W) 'W\ 'W^'Wk 'W\'^'W^'W)'T0-+%=/0'•! !.<6n0D'M62H'7H6<5%+0''–! B+_'-6E<60D'$5/.2-'<+_3#/-2'7H6<5%+0'–! ,6DH2'-6E<60D'$5/.2-'%6DH23#/-2'7H6<5%+0'Wk'''''Zk ')k'\k'k'W1'Z1'\k'k'W1'Z1'Wk')k'Zk'T0-+%2'Zk'1k'lk '(k'Wk ')k'\k'W1 'Z1'k'^k'ok'Wkk'1k'lk '(k'Wk ')k'\k'W1'''''Zk 'Z1'k'^k'ok'Wkk'T0-+%2'Zk'1k'lk '(k'Wk ')k'\k'W1'''''Zk 'Z1'k'^k'ok'Wkk'1k'lk '(k'Wk'''''Zk ')k'\k'k'^k'ok'Wkk'W1'Z1'T0-+%2'Zk'1k'lk '(k'Wk'''''Zk ')k'\k'k'^k'ok'Wkk'W1'Z1'lk '(k'\k'k'^k'ok'Wkk'W1'Z1'Zk '1k'Wk')k'U+<+=/0'WX! TJ'0/5+'2/'5+<+2+'6-'0/2'$'<+$JP'-M$.'M62H'60'/%5+%'-"77+--/%`'F/M'&/"'$%+'5+<+=0D'J%/#'$'<+$J'ZX! TJ'&/"G%+'5+<+=0D'J%/#'$')30/5+P'5+<+2+'$05'&/"G%+'5/0+')X! TJ'&/"G%+'5+<+=0D'J%/#'$'Z30/5+P'0++5'2/'+62H+%'#+%D+'/%'%/2$2+'U+<+=/0'3';+%D+'•! ;+%D+'6J'-6E<60D'6-'$'Z30/5+'Merge U+<+2+'(k''lk '(k'\k'k'^k'ok'Wkk'W1'Z1'Zk '1k'Wk')k'lk 'Wkk'\k'k'^k'ok'(k'W1'Z1'Zk '1k'Wk')k'U+<+2+'(k''lk 'Wkk'\k'k'^k'ok'(k'W1'Z1'Zk '1k'Wk')k'lk 'Wkk'\k'k'^k'ok'W1'Z1'Zk '1k'Wk')k'U+<+2+'(k''lk 'Wkk'\k'k'^k'ok'W1'Z1'Zk '1k'Wk')k'lk'\k'k'^k'ok 'Wkk'W1'Z1'Zk '1k'Wk')k'U+<+=/0'3',/2$2+'•! ,/2$2+'6J'-6E<60D'6-'$')30/5+'Rotate U+<+2+'^k''lk'\k'k'ok 'Wkk'W1'Z1'Zk '1k'Wk')k'lk'\k'k'^k'ok 'Wkk'W1'Z1'Zk '1k'Wk')k'U+<+2+'^k''ok'\k'k'Wkk'W1'Z1'Zk '1k'Wk')k'lk'\k'k'ok 'Wkk'W1'Z1'Zk '1k'Wk')k'lk'U+<+=/0'•! >H$2'6J'/0+'-6E<60D'6-'$')30/5+'$05'/0+'6-'$'Z30/5+'–! 9$@+'&/"%'.67@'&/"'7$0'+62H+%'#+%D+'M62H'2H+'Z30/5+'/%'%/2$2+'M62H'2H+')30/5+'–!