Hi, I've noticed that, just as you can have a heap with an array-backed store, you can also have a binary search tree with the same store (although structured differently; see attachment for a bare-bones unsorted binary tree implementation -- which I have NOT yet tested, but which I can test if it will be used). The improvement will be in data locality, and while it may seem to use a bit more space than a link-based tree, I think it's worth it to let the RedBlackTree class use a custom store, such as any store that has getLeft/getRight/setLeft/setRight methods, and that uses opaque pointers.
How does this idea sound? Thank you! begin 644 arraycontainer.d M<')I=F%T92!I;7!O<G0@<W1D+F%L9V]R:71H;2`Z(&UA>"P@<W=A<#L-"G!R M:79A=&4@:6UP;W)T('-T9"YC;VYT86EN97([#0H-"G!U8FQI8R!S=')U8W0@ M3F]D92A4*0T*>PT*"7!U8FQI8R!4('9A;'5E.PT*"7!R:79A=&4@<'1R9&EF M9E]T('-E;&8[#0H)<')I=F%T92!P=')D:69F7W0@<&%R96YT.PT*"7!R:79A M=&4@<'1R9&EF9E]T(&QE9G0[#0H)<')I=F%T92!P=')D:69F7W0@<FEG:'0[ M#0I]#0H-"G!U8FQI8R!C;&%S<R!!<G)A>4)I;F%R>51R964H5"D-"GL-"@EP M<FEV871E($)I;F%R>4AE87`A*'!T<F1I9F9?=%M=*2!O<&5N26YD:6-E<SL- M"@EP<FEV871E($YO9&4A*%0I6UT@:71E;7,[#0H)<')I=F%T92!P=')D:69F M7W0@:5)O;W0@/2`M,3L-"@T*"6EN=F%R:6%N="@I#0H)>PT*"0DO+V9O<F5A M8V@@*&D[('1H:7,N;W!E;DEN9&EC97,I('L@87-S97)T*'1H:7,N:71E;7-; M:5TN<V5L9B`\(#`L(")/<&5N('-L;W0@:6YD97@@=V%S(&YO;FYE9V%T:79E M+B(I.R!]#0H)"7-I>F5?="!C;W5N="`](#`[#0H)"69O<F5A8V@@*&DL(&ET M96T[('1H:7,N:71E;7,I('L@:68@*&ET96TN<V5L9B`^/2`P*2![(&%S<V5R M="AI=&5M+G-E;&8@/3T@:2P@(DET96T@:6YD97@@9&ED(&YO="!P;VEN="!T M;R!I=&5M+B(I.R!C;W5N="LK.R!]('T-"@D)87-S97)T*&-O=6YT(#T]('1H M:7,N:71E;7,N;&5N9W1H("T@=&AI<RYO<&5N26YD:6-E<RYL96YG=&@L(")4 M:&4@:71E;2!C;W5N="!W87,@:6YV86QI9"XB*3L-"@E]#0H-"@EP<FEV871E M('9O:60@=F%L:61A=&4H:6X@8V]N<W0H3F]D92$H5"DI*B!N;V1E*0T*"7L- M"@D):68@*&YO9&4@(3T@;G5L;"D-"@D)>PT*"0D)87-S97)T*"9T:&ES+FET M96US6VYO9&4N<V5L9ET@/3T@;F]D92D[#0H)"0EA<W-E<G0H;F]D92YL969T M(#P@,"!\?"!T:&ES+F=E=$QE9G0H;F]D92DN<&%R96YT(#T](&YO9&4N<V5L M9BD[#0H)"0EA<W-E<G0H;F]D92YR:6=H="`\(#`@?'P@=&AI<RYG9712:6=H M="AN;V1E*2YP87)E;G0@/3T@;F]D92YS96QF*3L-"@D)"6%S<V5R="AN;V1E M+G!A<F5N="`\(#`@?'P@*"AT:&ES+F=E=%!A<F5N="AN;V1E*2YL969T(#T] M(&YO9&4N<V5L9BD@?"`H=&AI<RYG971087)E;G0H;F]D92DN<FEG:'0@/3T@ M;F]D92YS96QF*2DI.PT*"0E]#0H)?0T*#0H)<'5B;&EC($!P<F]P97)T>2!C M;VYS="A.;V1E(2A4*2DJ(')O;W0H*2![(')E='5R;B!T:&ES+FE2;V]T(#X] M(#`@/R`F=&AI<RYI=&5M<UMT:&ES+FE2;V]T72`Z(&YU;&P[('T-"@EP=6)L M:6,@8V]N<W0H3F]D92$H5"DI*B!G971087)E;G0H8V]N<W0H3F]D92$H5"DI M*B!N;V1E*2!I;B![('1H:7,N=F%L:61A=&4H;F]D92D[('T@;W5T("AP*2![ M('1H:7,N=F%L:61A=&4H<"D[('T@8F]D>2![(')E='5R;B!N;V1E+G!A<F5N M="`^/2`P(#\@;G5L;"`Z("9T:&ES+FET96US6VYO9&4N<&%R96YT73L@?0T* M"7!U8FQI8R!C;VYS="A.;V1E(2A4*2DJ(&=E=$QE9G0H8V]N<W0H3F]D92$H M5"DI*B!N;V1E*2!I;B![('1H:7,N=F%L:61A=&4H;F]D92D[('T@;W5T("AP M*2![('1H:7,N=F%L:61A=&4H<"D[('T@8F]D>2![(')E='5R;B!N;V1E+FQE M9G0@/CT@,"`_(&YU;&P@.B`F=&AI<RYI=&5M<UMN;V1E+FQE9G1=.R!]#0H) M<'5B;&EC(&-O;G-T*$YO9&4A*%0I*2H@9V5T4FEG:'0H8V]N<W0H3F]D92$H M5"DI*B!N;V1E*2!I;B![('1H:7,N=F%L:61A=&4H;F]D92D[('T@;W5T("AP M*2![('1H:7,N=F%L:61A=&4H<"D[('T@8F]D>2![(')E='5R;B!N;V1E+G)I M9VAT(#X](#`@/R!N=6QL(#H@)G1H:7,N:71E;7-;;F]D92YR:6=H=%T[('T- M"@T*"7!U8FQI8R!V;VED('-E=$QE9G0H8V]N<W0H3F]D92$H5"DI*B!N;V1E M+"!I;B!C;VYS="A.;V1E(2A4*2DJ(&QE9G0I#0H):6X@>R!A<W-E<G0H;F]D M92`A/2!N=6QL*3L@=&AI<RYV86QI9&%T92AN;V1E*3L@=&AI<RYV86QI9&%T M92AL969T*3L@?0T*"6)O9'D@>R!T:&ES+FET96US6VYO9&4N<V5L9ETN;&5F M="`](&QE9G0@(3T@;G5L;"`_(&QE9G0N<V5L9B`Z("TQ.R!I9B`H;&5F="`A M/2!N=6QL*2![('1H:7,N:71E;7-;;&5F="YS96QF72YP87)E;G0@/2!N;V1E M+G-E;&8[('T@?0T*#0H)<'5B;&EC('9O:60@<V5T4FEG:'0H8V]N<W0H3F]D M92$H5"DI*B!N;V1E+"!I;B!C;VYS="A.;V1E(2A4*2DJ(')I9VAT*0T*"6EN M('L@87-S97)T*&YO9&4@(3T@;G5L;"D[('1H:7,N=F%L:61A=&4H;F]D92D[ M('1H:7,N=F%L:61A=&4H<FEG:'0I.R!]#0H)8F]D>2![('1H:7,N:71E;7-; M;F]D92YS96QF72YR:6=H="`](')I9VAT("$](&YU;&P@/R!R:6=H="YS96QF M(#H@+3$[(&EF("AR:6=H="`A/2!N=6QL*2![('1H:7,N:71E;7-;<FEG:'0N M<V5L9ETN<&%R96YT(#T@;F]D92YS96QF.R!]('T-"@T*"7!U8FQI8R!C;VYS M="A.;V1E(2A4*2DJ(&%L;&]C3F]D92@I#0H);W5T("AP*2![('1H:7,N=F%L M:61A=&4H<"D[('T-"@EB;V1Y#0H)>PT*"0ET:&ES+G)E<V5R=F4H=&AI<RYI M=&5M<RYL96YG=&@@*R`Q*3L-"@D)875T;R!I(#T@=&AI<RYO<&5N26YD:6-E M<RYF<F]N=#L-"@D)=&AI<RYI=&5M<UMI72`]($YO9&4A*%0I*%0N:6YI="P@ M:2P@+3$L("TQ+"`M,2D[#0H)"71H:7,N;W!E;DEN9&EC97,N<F5M;W9E1G)O M;G0H*3L-"@D):68@*'1H:7,N:5)O;W0@/"`P*2![('1H:7,N:5)O;W0@/2!I M.R!]#0H)"7)E='5R;B`F=&AI<RYI=&5M<UMI73L-"@E]#0H-"@EP=6)L:6,@ M=F]I9"!R97-E<G9E*'-I>F5?="!C87!A8VET>2D-"@E[#0H)"6EF("AT:&ES M+F]P96Y);F1I8V5S+FQE;F=T:"`\(&-A<&%C:71Y*0T*"0E[#0H)"0EA=71O M('!R979,96X@/2!T:&ES+FET96US+FQE;F=T:#L-"@D)"71H:7,N:71E;7,N M;&5N9W1H(#T@;6%X*&-A<&%C:71Y+"`R("H@=&AI<RYI=&5M<RYL96YG=&@I M.PT*"0D)875T;R!I;F1I8V5S(#T@;F5W('!T<F1I9F9?=%MT:&ES+FET96US M+FQE;F=T:%T[#0H)"0ES:7IE7W0@:2`](#`[#0H)"0EW:&EL92`H(71H:7,N M;W!E;DEN9&EC97,N96UP='DI('L@:6YD:6-E<UMI*RM=(#T@=&AI<RYO<&5N M26YD:6-E<RYF<F]N=#L@=&AI<RYO<&5N26YD:6-E<RYR96UO=F5&<F]N="@I M.R!]#0H)"0EF;W)E86-H("AJ.R!P<F5V3&5N("XN('1H:7,N:71E;7,N;&5N M9W1H*2![(&EN9&EC97-;:2LK72`](&H[('T-"@D)"71H:7,N;W!E;DEN9&EC M97,N86-Q=6ER92AI;F1I8V5S+"!I*3L-"@D)?0T*"7T-"@T*"7!U8FQI8R!V M;VED(&9R965.;V1E*&-O;G-T*$YO9&4A*%0I*2H@;F]D92D-"@EI;B![('1H M:7,N=F%L:61A=&4H;F]D92D[('T-"@EB;V1Y#0H)>PT*"0EI9B`H;F]D92`A M/2!N=6QL*0T*"0E[#0H)"0EA=71O('!->4YO9&4@/2`F=&AI<RYI=&5M<UMN M;V1E+G-E;&9=.PT*"0D)=&AI<RYF<F5E3F]D92AT:&ES+F=E=$QE9G0H<$UY M3F]D92DI.PT*"0D)<$UY3F]D92YL969T(#T@+3$[#0H)"0ET:&ES+F9R965. M;V1E*'1H:7,N9V5T4FEG:'0H<$UY3F]D92DI.PT*"0D)<$UY3F]D92YR:6=H M="`]("TQ.PT*"0D):68@*'!->4YO9&4N<&%R96YT(#X](#`@)B8@=&AI<RYI M=&5M<UMP37E.;V1E+G!A<F5N=%TN;&5F="`]/2!P37E.;V1E+G-E;&8I('L@ M=&AI<RYI=&5M<UMP37E.;V1E+G!A<F5N=%TN;&5F="`]("TQ.R!]#0H)"0EI M9B`H<$UY3F]D92YP87)E;G0@/CT@,"`F)B!T:&ES+FET96US6W!->4YO9&4N M<&%R96YT72YR:6=H="`]/2!P37E.;V1E+G-E;&8I('L@=&AI<RYI=&5M<UMP M37E.;V1E+G!A<F5N=%TN<FEG:'0@/2`M,3L@?0T*"0D)<$UY3F]D92YP87)E M;G0@/2`M,3L-"@D)"71H:7,N;W!E;DEN9&EC97,N:6YS97)T*'!->4YO9&4N M<V5L9BD[#0H)"0EP37E.;V1E+G-E;&8@/2`M,3L-"@D)"6EF("AT:&ES+FE2 M;V]T(#T]('!->4YO9&4N<V5L9BD@>R!T:&ES+FE2;V]T(#T@+3$[('T-"@D) M?0T*"7T-"@T*"7!R:79A=&4@=F]I9"!S=V%P4VQO='-.;TYO=&EF>4AE87`H M<'1R9&EF9E]T(&DL('!T<F1I9F9?="!J*0T*"7L-"@D)87-S97)T*&D@/CT@ M,"`F)B!J(#X](#`I.PT*"0ES=V%P*'1H:7,N:71E;7-;:5TL('1H:7,N:71E M;7-;:ETI.PT*"0ES=V%P*'1H:7,N:71E;7-;:5TN<V5L9BP@=&AI<RYI=&5M M<UMJ72YS96QF*3L-"@D):68@*'1H:7,N:71E;7-;:5TN;&5F="`^/2`P*2![ M('1H:7,N:71E;7-;=&AI<RYI=&5M<UMI72YL969T72YP87)E;G0@/2!J.R!] M#0H)"6EF("AT:&ES+FET96US6VE=+G)I9VAT(#X](#`I('L@=&AI<RYI=&5M M<UMT:&ES+FET96US6VE=+G)I9VAT72YP87)E;G0@/2!J.R!]#0H)"6EF("AT M:&ES+FET96US6VI=+FQE9G0@/CT@,"D@>R!T:&ES+FET96US6W1H:7,N:71E M;7-;:ETN;&5F=%TN<&%R96YT(#T@:3L@?0T*"0EI9B`H=&AI<RYI=&5M<UMJ M72YR:6=H="`^/2`P*2![('1H:7,N:71E;7-;=&AI<RYI=&5M<UMJ72YR:6=H M=%TN<&%R96YT(#T@:3L@?0T*"0EI9B`H=&AI<RYI4F]O="`]/2!I*2![('1H M:7,N:5)O;W0@/2!J.R!]#0H)"65L<V4@:68@*'1H:7,N:5)O;W0@/3T@:BD@ M>R!T:&ES+FE2;V]T(#T@:3L@?0T*"7T-"@T*"7!U8FQI8R!V;VED('1R:6TH M*0T*"7L-"@D)<VEZ95]T(&QE;E9A;&ED(#T@=&AI<RYI=&5M<RYL96YG=&@[ M#0H)"69O<F5A8VA?<F5V97)S92AI+"!R968@:71E;3L@=&AI<RYI=&5M<RD- M"@D)>PT*"0D):68@*'1H:7,N;W!E;DEN9&EC97,N96UP='DI('L@8G)E86L[ M('T-"@D)"65L<V4-"@D)"7L-"@D)"0EL96Y686QI9"`](&D[#0H)"0D)875T M;R!O<&5N26YD97@@/2!T:&ES+F]P96Y);F1I8V5S+F9R;VYT.PT*"0D)"71H M:7,N;W!E;DEN9&EC97,N<F5M;W9E1G)O;G0H*3L-"@D)"0ET:&ES+G-W87!3 M;&]T<TYO3F]T:69Y2&5A<"AI+"!O<&5n26y...@i.pt*"0D)"71H:7,N;W!E M;DEN9&EC97,N:6YS97)T*&DI.PT*"0D)?0T*"0E]#0H)"71H:7,N:71E;7,N M;&5N9W1H(#T@;&5N5F%L:60[#0H)?0T*#0H)<'5B;&EC(&EN="!O<$%P<&QY M*&EN="!D96QE9V%T92AR968@8V]N<W0H3F]D92$H5"DI*BD@9&<I#0H)>PT* M"0EI;G0@<F5S=6QT(#T@,#L-"@D)875T;R!S=&%C:R`](&YE=R!.;V1E(2A4 M*2I;,%T[#0H)"6EF("AT:&ES+G)O;W0@(3T@;G5L;"D-"@D)>PT*"0D)<W1A M8VL@?CT@=&AI<RYI4F]O="`^/2`P(#\@)G1H:7,N:71E;7-;=&AI<RYI4F]O M=%T@.B!N=6QL.PT*"0D)=VAI;&4@*'-T86-K+FQE;F=T:"`^(#`I#0H)"0E[ M#0H)"0D)875T;R!N;V1E(#T@<W1A8VM;)"`M(#%=.PT*"0D)"7-T86-K+FQE M;F=T:"`M/2`Q.PT*"0D)"69O<B`H875T;R!T96UP(#T@=&AI<RYG9712:6=H M="AN;V1E*3L@=&5M<"`A/2!N=6QL.R!T96UP(#T@=&AI<RYG971,969T*'1E M;7`I*0T*"0D)"7L-"@D)"0D)<W1A8VL@?CT@=&5M<"`A/2!N=6QL(#\@)G1H M:7,N:71E;7-;=&5M<"YS96QF72`Z(&YU;&P[#0H)"0D)?0T*"0D)"7)E<W5L M="`](&1G*&YO9&4I.PT*"0D)"6EF("AR97-U;'0I('L@8G)E86L[('T-"@D) M"7T-"@D)?0T*"0ER971U<FX@<F5S=6QT.PT*"7T-"GT-"@T*86QI87,@07)R M87E":6YA<GE4<F5E(2AI;G0I($EN=%1R964[("\O2G5S="!F;W(@=&5S=&EN !9P`` ` end