More 2,3,4 Tree Notes

ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ

ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ

2334ÿ5ÿ6ÿ7389 ÿ 933 ÿ

ÿÿÿ 9 ÿ8 ÿ!88ÿ79" "93 ÿ

#ÿ%3 "93ÿ0ÿ &ÿ7'8(ÿ 933 ÿ #ÿ%3 "93ÿ)ÿ &ÿ*)+,-ÿ 933 ÿ #ÿ%3 "93ÿÿ

%3 "93ÿ)ÿ&ÿ*)+,-ÿ 933 ÿ

"628(ÿ7389 ÿ 933 ÿ *;ÿ5<,<0-ÿ #ÿÿ"608(ÿ 389 ÿ933ÿ ÿ8ÿ9393 ÿ933ÿ " ÿ8ÿÿ

2334ÿ5ÿ6ÿ7389 ÿ 933 ÿ

#ÿ"608(ÿ7389 ÿ 933 ÿ #ÿ*)+,-ÿ 933 ÿ #ÿ1'33ÿ8ÿ! 89(ÿ #ÿ*8+/-ÿ 933 ÿ 3ÿ #ÿ26 933 ÿ 8ÿÿ9ÿÿ:ÿ

56ÿÿ57ÿ

"628(ÿ1939ÿ 98O39 8ÿ

3ÿ 55ÿ

&ÿ=8 ÿ398ÿ 3ÿ8 ÿ8ÿ38 ÿ0ÿ 93ÿ8 ÿ 93 ÿÿ>?@ÿ 393 +ÿ0393ÿ>ÿ ÿ3ÿ"/39ÿCÿ 93ÿÿ &ÿD9ÿ8ÿ 3ÿ0ÿ 93ÿE@ÿEFÿGÿE>ÿÿ 9ÿÿ43( ÿH@ÿHFÿGÿH>?@ÿ #ÿ43( ÿÿ3ÿ "/933ÿCÿE@ÿ893ÿ3

ÿ8ÿH@ÿ #ÿ43( ÿÿ3ÿ "/933ÿCÿEIÿ893ÿ/3033ÿHI?@ÿ8 ÿHIÿJIÿKÿFLÿGLÿ>ÿ?ÿ@Nÿ #ÿ43( ÿÿ3ÿ "/933ÿCÿE>ÿ893ÿ93839ÿ8ÿH>?@ÿ

#ÿ23ÿ 8ÿ3S3 ÿ3ÿÿCÿ939ÿ98O39 8ÿC9ÿ/89(ÿ933 ÿ ÿ"608(ÿ 389 ÿ933 ÿ #ÿT83(+ÿ03ÿO ÿ3ÿJHILÿUINÿCÿ 3ÿEÿ/3033ÿ3ÿ93 "9 O3ÿ 98O39 8 ÿCÿ3ÿ "/933 ÿCÿEÿ93 ÿ8ÿ 93ÿEIÿ8 ÿEIV@ÿ #ÿÿ939ÿ98O39 8ÿCÿ8ÿ"608(ÿ 389 ÿ933ÿO  ÿ3ÿ43( ÿÿ  938 ÿ939ÿ 55ÿÿÿÿ87ÿ Qÿ 58ÿ 8ÿÿÿPÿÿÿQÿ 59ÿ 8:ÿÿÿÿR8ÿ 8ÿ 7ÿ Pÿ 57ÿ 5Qÿ 56ÿ R6ÿ 5ÿ Rÿ 9ÿ :ÿ

&ÿ.3 6/8 4ÿ933 ÿ

5Rÿ 5Pÿ 53ÿ 59ÿ 5:ÿ

&ÿ 3ÿ38O3 ÿ 93ÿÿ3 ÿ8 ÿ 39O3ÿ8 ÿ'8 339 ÿ 55ÿÿÿÿ87ÿ 8ÿÿÿPÿÿÿQÿ 59ÿ 8:ÿÿÿÿR8ÿ R6ÿ

"628(ÿ7389 ÿ

#ÿ789ÿÿ 389 ÿÿ8ÿ/89(ÿ 389 ÿ933ÿ #ÿÿ38 ÿ398ÿ 3ÿ0ÿ 93ÿE@ÿEFÿGÿE>ÿ8 ÿ43( ÿH@ÿHFÿGÿH>?@ÿ WÿHÿXÿHIÿJIÿKÿ@LÿGLÿ>ÿ?ÿ@NYÿ3ÿ 389 ÿ3983 ÿ "

3

C"(ÿ WÿHÿZÿH@Yÿ03ÿ "3ÿ3ÿ 389 ÿÿ ÿE@ÿ WÿHI?@ÿZÿÿHÿZÿHIÿJIÿKÿFLÿGLÿ>ÿ?ÿ@NYÿ03ÿ "3ÿ3ÿ 389 ÿÿ ÿEIÿ WÿHÿ[ÿH>?@Yÿ03ÿ "3ÿ3ÿ 389 ÿÿ ÿE>ÿ

#ÿ.38 ÿ8ÿ3S398ÿ 3ÿ3983 ÿ3ÿ 389 ÿ" "

3

C"(ÿ #ÿ=S8'3Yÿ 389 ÿC9ÿÿ 55ÿÿÿÿ87ÿ 8ÿÿÿPÿÿÿQÿ 59ÿ 8:ÿÿÿÿR8ÿ R6ÿ

0ÿ

20345ÿ67889ÿ2 ÿ 4 05ÿ

58ÿÿÿ20345ÿ6788ÿ

ÿÿ20345ÿ788ÿ29ÿ8ÿ04ÿ788ÿ7ÿ04ÿ7885ÿ9ÿÿÿ 987ÿÿ8ÿ ÿ!7!8789ÿ

ÿ6878'ÿÿ20345ÿ788ÿ97 ÿ6ÿ89ÿ9ÿ8ÿ89:;<ÿ6=ÿ ÿ&7'ÿ

ÿ)8!8 ÿÿ8ÿ+87ÿÿ783ÿÿ87ÿ8ÿÿÿ20345ÿ 788ÿ9ÿ8ÿÿ083ÿ8ÿ7ÿ48ÿ ,-ÿÿÿ,/ÿÿÿ01ÿ

ÿ$87 ÿÿÿ20345ÿ788ÿÿ6ÿ89ÿN89ÿ89:;<ÿ6=ÿ8ÿ

"ÿ#8$%8ÿ&7!87'ÿ8(87ÿ87ÿ8ÿ9ÿÿ9ÿ7ÿ78ÿ "ÿ)8!ÿ&7!87'ÿÿ8ÿ8*87ÿ89ÿ(8ÿ8ÿ98ÿ8!ÿ

0ÿÿÿ2ÿ

,0ÿ

,2ÿ

03ÿÿÿÿ40ÿ

W987ÿ

ÿX8ÿ987ÿÿ8ÿ8ÿ9YEÿZ=ÿÿ8ÿ!78ÿ[ÿÿ8ÿ8ÿ788ÿ+ÿ 987 ÿ7ÿYÿ "ÿX8ÿ!78987(8ÿ8ÿ8!ÿ!7!87ÿ+ÿÿ "ÿX8ÿÿ98ÿÿ(87ÿ2 8 3ÿ8ÿ[ÿÿ+88ÿÿ\85ÿ

ÿ]*!8'ÿ987 ÿN8ÿ^ÿ989ÿÿ(87ÿ 0ÿÿÿ2ÿ

0ÿÿÿ2ÿ

,-ÿÿÿ,/ÿÿÿ01ÿ ,0ÿ ,2ÿ ,-ÿÿÿ,/ÿÿÿ01ÿ ,0ÿ ,2ÿ

[ÿ

03ÿÿÿ40ÿÿÿ4/ÿ

[ÿ

03ÿÿÿ4-ÿÿÿ40ÿÿÿ4/ÿ

99ÿÿW987ÿ

ghijklmnoÿB6qrst9YEÿZ=ÿ

ÿ>8ÿ’ÿ+8ÿÿ20345ÿ788ÿÿ 6ÿ89ÿ 88ÿ’ÿ9ÿ89:;<ÿ6=ÿ Iuÿvwÿxwyz{|ÿ};zÿ~wÿYÿ€;ÿ:;{y€wÿ€|wÿ‚xwz€;‚ÿ "ÿ67 8ÿÿ ‚;ƒwÿ[ÿ "ÿ$8!ÿ“ÿN89ÿ89:;<ÿ6=ÿ 8ÿ+898ÿ8ÿ(9ÿ Auÿvwÿyƒƒÿ€|wÿ‚w„ÿw‚€zÿ9YEÿZ=ÿy€ÿ‚;ƒwÿ[ÿ 89:;<ÿ6=ÿ89ÿ " ÿ$ 8!ÿ0ÿN89ÿ89I=ÿ8ÿ euÿ…nlh†ÿZ[rs‡ˆZ‰9[=ÿ " ÿ$ 8!ÿÿN89ÿ89:;<ÿ6=ÿ lŠÿBq‹ZZt9[=ÿ 8ÿ+898ÿ8ÿ9!ÿ N89ÿ89I=ÿ8ÿÿ8ÿ ÿÿ{zwy€wÿyÿ‚w„ÿwŒ€ÿz;;€ÿyŽ;wÿ[ÿ !877ÿ89:;<ÿ6=ÿ9!9ÿ [ÿÿq‘ˆBt9[=ÿ

ÿ693ÿÿ987ÿÿÿ

20345ÿ788ÿN89ÿ89:;<ÿ6=ÿ 8ÿ

"ÿ>8ÿ?ÿ+8ÿ8ÿ8ÿÿÿ20345ÿ788ÿÿ6ÿ89ÿ "ÿ$8ÿ878ÿ78ÿÿ89ÿABÿ89ÿÿ8!ÿBÿCÿDEÿFÿEÿ?ÿGÿIÿÿÿ 89ÿÿ8!ÿ?3ÿ8ÿ(?G8Iÿÿ ?ÿ ÿ ÿÿÿ6ÿJÿIÿKÿAÿKÿLÿKÿFÿKÿA CÿAGÿI "ÿ693ÿ?ÿMÿ:;<ÿ96ÿKÿI=ÿ

TQUPVÿOPQRSÿ Dÿ Iÿ Iÿ Aÿ ?GIÿ A?GIÿ ?ÿ Dÿ

_(87ÿÿ$!ÿ

ÿX8ÿ8ÿÿ(87ÿÿÿ\8ÿ[ÿÿÿ9!ÿ!87'ÿ "ÿ8ÿ[IÿFÿ[`ÿ+8ÿ8ÿ78ÿÿ[ÿÿÿYIÿFÿYLÿ+8ÿ8ÿN89ÿÿ[ÿ "ÿ8ÿ[ÿ9ÿ78!8ÿ89ÿ[aÿÿ[cÿ dÿ[aÿ9ÿÿ8ÿÿN89ÿYIÿYAÿÿ78ÿ[Iÿ[Aÿ[eÿ dÿ[cÿ9ÿÿ08ÿÿN8ÿYLÿÿ78ÿ[Lÿ[`ÿ

"ÿN8ÿYeÿÿ9ÿ9878ÿÿ8ÿ!78ÿfÿÿ[ÿ2ÿ8ÿ7ÿÿ+8ÿ7885ÿ

ÿ68ÿ(87ÿÿ!7! 8ÿÿ8ÿ!78ÿ8ÿfÿ

fÿ

fÿ

,/ÿÿÿ01ÿ

,/ÿ01ÿÿ40ÿ

[ÿ

,0ÿ ,2ÿ 03ÿÿ4-ÿÿ40ÿÿ4/ÿ

[Iÿ [Aÿ [eÿ [Lÿ [`ÿ

[aÿ

[cÿ

,0ÿ ,2ÿ 03ÿÿ4-ÿ 4/ÿ

[Iÿ [Aÿ [eÿ [Lÿ [`ÿ

)88ÿ

ÿ X8ÿ788ÿ88ÿÿÿ87ÿÿ8ÿ98ÿ878ÿ8ÿ8ÿ9ÿÿ8ÿ8ÿÿ 8ÿ78ÿ

ÿ _87983ÿ8ÿ78!8ÿ8ÿ87ÿÿ9ÿ787ÿ98997ÿ273ÿ8”(83ÿÿ 9ÿ787ÿ!78889975ÿÿ888ÿ8ÿ87ÿ87ÿ

ÿ ]*!8'ÿÿ888ÿN8ÿ043ÿ8ÿ78!8ÿÿÿ0•ÿ2787ÿ989975ÿ ,-ÿÿÿ,/ÿÿÿ01ÿ 0ÿÿÿ2ÿ ,0ÿ ,2ÿ 03ÿÿÿ40ÿÿÿ4/ÿ

0ÿÿÿ2ÿ

,-ÿÿÿ,/ÿÿÿ03ÿ ,0ÿ ,2ÿ

40ÿÿÿ4/ÿ

0ÿ

23456789 ÿ34ÿ 93ÿ

ÿ5853ÿ3ÿ536ÿ769ÿÿ3945ÿÿÿ 5ÿ3ÿ 3456789 ÿ 565ÿ 3945ÿÿ595ÿÿ3945ÿ ÿ935ÿ84ÿ34ÿ39ÿ5ÿ ÿ9ÿ3485ÿ3ÿ 3456789 ÿÿ3945ÿÿ ÿ!653ÿ"ÿ 5ÿ93456ÿ 9ÿ 5ÿ ÿ#5ÿ$ÿ5ÿ4%53ÿ83ÿ97ÿÿ65ÿ&3945ÿ

'ÿ 93ÿ9!5693$ÿ 5ÿ565ÿÿ ÿ3ÿ4%53ÿ83ÿ(ÿ34ÿ9)5ÿ3ÿ 536ÿ769ÿ"ÿ9ÿ5ÿ5654ÿ3945ÿ*ÿ 'ÿ+756ÿÿ7 93ÿ5ÿ 3456789 ÿÿ!69!5ÿ9ÿ5ÿ!653ÿ"ÿ

"ÿ ,ÿÿ./ÿ

0ÿÿ1ÿÿ2ÿ

(ÿ ÿ .3ÿ

"ÿ ,ÿ

0ÿÿ1ÿÿ2ÿ

*ÿ .3ÿÿ./ÿ

+38ÿ97ÿ58593ÿ

ÿ:5ÿ;ÿ5ÿÿ<&6=ÿ655ÿ ÿ>ÿ5ÿ 'ÿ655ÿ;ÿÿ?@ABCÿ>Eÿ5ÿÿ ÿF3ÿÿ458593ÿ9!5693ÿ

23456789 ÿ34ÿ63756ÿ

ÿ#5ÿ&$ÿ3ÿ4%53ÿ83ÿ(ÿ97ÿÿÿÿ03945ÿ96ÿÿ63945ÿ 'ÿ63756ÿ9!5693$ÿ ÿÿ7ÿÿ 5ÿ9)5ÿÿ84ÿ97ÿ(ÿ9ÿÿÿ ÿÿ&7ÿÿ 5ÿ9)5ÿ3ÿ5ÿ769ÿ"ÿ9ÿÿ ÿÿ07ÿÿ 5ÿ9)5ÿ3ÿ5ÿ769ÿ(ÿ9ÿ"ÿ 'ÿ+756ÿÿ63756ÿ39ÿ 3456789 ÿ9 6ÿ

"ÿ

"ÿ

/ÿÿ,ÿ

0ÿ

(ÿ ÿ 8ÿÿ9ÿ

/ÿÿ9ÿ

0ÿ

(ÿ ,ÿÿ

8ÿ

F!85533ÿÿ936ÿ

ÿ#9!693ÿ97ÿ57753ÿ4936ÿ!855393ÿ

'ÿG5ÿ)ÿ?@ABCÿ>Eÿ3945ÿ9ÿ895ÿ5ÿ3945ÿ769ÿ

ÿ9ÿ45855ÿ5ÿ536ÿ 'ÿG5ÿ3485ÿ3ÿ 3456789 ÿ ÿÿ565ÿ97ÿ?@ABCÿ>Eÿ 7 93ÿ79889 54ÿÿÿ9ÿ935ÿ63756ÿ 'ÿÿHÿ7 93ÿ34ÿ63756ÿ5ÿ?@IEÿ5ÿ

J56ÿF356ÿ 5855ÿK95ÿ 9ÿ9645654ÿ4936ÿÿ Lÿ Iÿ Iÿ Iÿ ÿÿÿÿ3ÿ5 85ÿ MNOMPQMRÿ MNOMPQMRÿ MNOMPQMRÿ ÿ!859ÿ49ÿÿ!8553ÿ 349X54ÿ35693ÿ J!ÿ:ÿSTACBSCÿOÿU>BVÿWÿ STACBSCÿOÿU>BVÿWÿ STACBSCÿOÿU>BVÿWÿ ÿÿ6! 85ÿ9ÿ!8553ÿ

<=ÿ655ÿ

<=ÿ655ÿ

ÿ ÿ45853ÿ3ÿ5ÿ769ÿÿ<&6=ÿ655ÿ5ÿ ?@ABCÿ>Eÿ5ÿ

ÿ^5356893ÿ97ÿÿ<&6=ÿ655ÿ ÿ+3ÿ<_`a=ÿ655ÿÿÿ 8 ÿ56ÿ655ÿ  ÿÿ5ÿ3945ÿÿ5 553ÿ_ÿ34ÿ aÿ84653ÿ34ÿ965ÿ5 553ÿ_ÿ34ÿ aÿ53657ÿ

<&6=ÿ ABCÿ>ÿ ABCÿ>ÿ ABCÿ>ÿ ÿ9!85]ÿ9ÿ!8553ÿ 655ÿ YBUZQ[P\ZMÿYBUZQ[P\ZMÿ YBUZQ[P\ZMÿ

ÿ5737ÿ

'ÿ+3ÿ<_`a=ÿ655ÿÿÿ 8 ÿ56ÿ655ÿbÿ ÿÿ &ÿcÿ_ÿcÿ
0ÿ

23456ÿ7899 ÿ9 7ÿ

ÿ9ÿ9 7ÿÿ3ÿ23456ÿ7899ÿ 78  ÿÿ 978 9 ÿ ÿÿ ÿ2 ÿÿÿ ÿ6ÿ ÿ 9ÿ37ÿ93 7ÿ ÿ2 ÿÿÿ ÿ6ÿ ÿ 9ÿ37ÿ  7ÿ

()7983ÿ 9 8'ÿ ÿ()7983ÿ 9 8'ÿ ÿ* *3'ÿ3ÿ$ +ÿ ÿ,&&9

ÿ7 9ÿ ÿ *&ÿ -98ÿ737ÿ7 9ÿ* 9$ÿ7ÿ783 98ÿ79ÿ 8 37 ÿ28$98 ÿÿ 3  7*$96ÿ ÿ.373ÿ978 9 ÿ389ÿ 8*%9$ÿ 7ÿ5&+ ÿ ÿ,ÿ/$ +ÿ783 980ÿÿ783 98 ÿ3ÿ5&+ÿ3 ÿ3ÿ-9ÿ ÿ13ÿ-9ÿ 3 73   ÿ3ÿ$ &7 38'ÿ ÿ9)7983ÿ 9 8'ÿ ÿ7ÿ  9ÿ79ÿ* 598ÿÿ$ +ÿ783 98 ÿ ÿ2ÿ& %9) 7'ÿ8998 ÿ7ÿ79ÿ* 598ÿÿ783 98 ÿ ÿ 73$38$ÿ $ &7 38'ÿ 938&ÿ3$ÿ*%$379ÿ%9837  ÿ

!"899 ÿ

ÿ# 9$ÿ8ÿ %9 97  ÿ3ÿ8$989$ÿ $ &7 38'ÿ8ÿ3ÿ38 9ÿ&9&7 ÿÿ 978 9 ÿ737ÿ$ÿ7ÿ 7ÿ ÿ 3 ÿ 9 8'ÿ ÿ( ÿ$373ÿ53 9ÿ %9 9737  ÿ

!"7899ÿ$9ÿ

ÿ,ÿ3"7899ÿÿ8$98ÿ$ÿ ÿ3ÿ246ÿ7899ÿ- 7ÿÿ5ÿ6789ÿ3$ÿ :7ÿ ÿ; 9ÿ7ÿ *&ÿ737ÿ79ÿ7ÿ& $89ÿ89989&9 ÿ3$ÿ7"<ÿ +9' ÿ 789$ÿ37ÿ3ÿ$9ÿ&3ÿ 7ÿ 7ÿ3ÿ  9ÿ5&+ÿ ÿ,ÿ3"7899ÿ- 7ÿÿ978 9 ÿ3 ÿ2ÿ& %9) 7'ÿ2 3ÿ6ÿ 8ÿ 938&ÿ8ÿ*%$379ÿ%9837 4ÿ3$ÿ* 9 ÿ2=36ÿ 5&+ ÿ-989ÿ3ÿ ÿ79ÿ rel="nofollow">9ÿÿ79ÿ5&+ÿ

?99+ÿ@ÿ"ÿA938&ÿ899 ÿ

ÿB9&7*89ÿ<ÿ ÿA%3'ÿ899 ÿ ÿB9&7*89ÿ8ÿ ÿ28406ÿ899 ÿ ÿB9&7*89ÿCÿ

ÿD9$"53&+ÿ7899 ÿ

0ÿ

ÿÿ

8 !ÿ"#ÿÿ9$%&%&

93  ÿ 

()* +"#

' ' ' '

()* +"# ,* (*

93  ÿÿ9$%&%&3

 3ÿÿÿÿ

' '

4ÿÿ

-*./*ÿ*)ÿ"*!ÿ./.* 01213443ÿ3642ÿ78

93  ÿ 



80!ÿ+"#ÿ 

1ÿ. !ÿ"#ÿÿÿÿ*ÿÿ"#ÿ#ÿ

2"#ÿÿ*ÿ#ÿÿÿ *ÿ"#ÿÿ*ÿÿ345ÿ 7!.ÿ.ÿ89:;ÿ<:= ÿ#ÿ3ÿÿ#ÿ.?ÿ*)ÿ"#ÿ ' @* ÿÿ*ÿ #ÿ"#ÿA5ÿABCÿA3*ÿÿ7!ÿ95ÿ9BCÿ9345 '

'

D 7!ÿÿ#ÿ?ÿ*)ÿA5ÿÿÿ#ÿ95 D 7!ÿÿ#ÿ?ÿ*)ÿA:ÿ? ÿ9:45ÿÿ9:8:EÿB;ÿC;ÿ345= D 7!ÿÿ#ÿ?ÿ*)ÿA3ÿÿ#ÿ9345

#ÿFÿ*ÿ*ÿ.ÿÿFÿÿ/"#* ÿ 3 3ÿÿÿ0ÿÿÿ2  3ÿÿÿÿ%3 %4

01213443ÿ3642ÿ78

93  ÿ 

%

+.ÿ*ÿ"#ÿÿÿ?!ÿ"#ÿ 1ÿ"#ÿÿ*ÿ #ÿ"#ÿA5ÿABCÿA3ÿ7!ÿ95ÿ9BCÿ9345 9J98:Eÿ5;ÿC;ÿ345=6ÿ#ÿ"#ÿ.ÿ"")! 9K96ÿÿ"*ÿ#ÿ"#ÿÿ"#ÿA5 9 K9K98:EÿB;ÿC;ÿ345=6ÿÿ"*ÿ#ÿ"#ÿÿ"#ÿA: 9Lÿ9 6ÿÿ"*ÿ#ÿ"#ÿÿ"#ÿA3

' : ' 5 ' :45ÿ : ' 345

"#ÿÿGÿ*ÿ.ÿ#ÿ"#ÿ"")! 2G./6ÿ"#ÿ)*ÿ%4 ÿ 3 3ÿÿÿ0ÿÿÿ2  3ÿÿÿÿ%3 %4 93  ÿ 



93  ÿ 

3

80!ÿ,*ÿ F

0ÿ"ÿGÿ#ÿ**ÿ*)ÿ*ÿFÿ)*.ÿ?!ÿÿ *ÿ. !ÿ"#ÿ H.! ÿ ÿFÿ.ÿ89;ÿ<=*)ÿ*ÿA? ÿ#ÿ"Fÿ Fÿ*)ÿ#ÿ?:ÿ*:)ÿA**ÿÿ"#ÿA:ÿA:I5 1ÿ*ÿFÿ*)ÿÿ. !ÿ"#ÿÿFÿ#ÿ7!ÿÿ "ÿ* ÿ 3 2 3 3ÿÿÿ0ÿÿÿ2  3ÿÿÿÿ%3 3  0  2 4 %4  %  

80!ÿ+"#

01213443ÿ3642ÿ78

01213443ÿ3642ÿ78

01213443ÿ3642ÿ78





%

93  ÿ 

0   



93  ÿ 

1ÿ93  ÿÿ9*ÿ"ÿ3ÿÿ*ÿ3%ÿ ÿÿÿ. !ÿ "#ÿ#ÿ#ÿ)** ÿ/*/ ' '

H*+Nÿ7*/!6ÿF!ÿÿ*ÿ#ÿÿ.*ÿ)*ÿ"# (/#ÿ7*/!6ÿÿ#ÿGÿ*ÿ#Fÿ#ÿ.ÿ/#

(/ÿ*ÿ#ÿ.?ÿ*)ÿ"# ÿÿÿ*ÿ*)ÿÿ 93  ÿÿÿ"ÿÿ3* ÿ%*ÿ*ÿ* 4ÿÿÿÿÿÿ3 3ÿÿÿ2 01213443ÿ3642ÿ78

3 93  ÿ 

2

3ÿÿÿÿ%3 0

ÿÿÿ93  ÿ 

@Aÿÿÿ)ÿÿB4ÿC$ÿÿ1ÿDÿÿ-ÿ,0ÿ(Eÿ

6ÿ93  ÿÿÿÿÿÿ!"ÿ$ 76 % % %

,ÿÿB

&ÿ'(ÿÿÿÿÿ93  ÿÿ)ÿÿ +,ÿÿÿÿ-ÿ./ÿÿ01ÿ/234ÿ5ÿ4ÿ'ÿ67ÿ0ÿÿ ÿÿ01ÿ' ÿ)ÿ8 '67ÿ 'ÿ 97ÿ:ÿ.ÿ:<ÿ:5ÿ:. 2.67

= ÿ'> !"ÿÿ:ÿ7$

% %

Aÿ18ÿÿ01ÿ11Eÿ(=ÿ AÿEÿ,=ÿÿ8-)9FF ÿ0ÿDEÿ(,ÿÿGH0

IJ1-6ÿÿ?EÿK4ÿ,=ÿÿ8-)

+,ÿÿÿ93  ÿÿ)ÿÿ?ÿ!"ÿ$

01  3 7 7 . '67 .'67 ' 3 01213443ÿ3642ÿ78

93  ÿ 



N8-)ÿ0ÿ+1- % %

-ÿD75ÿDO(ÿÿ,-0ÿÿD0ÿÿB75ÿB<(ÿÿ?EÿÿD 0ÿDÿ1-,0ÿ0ÿDPÿ0ÿDR

%

?EÿBTÿÿ0ÿÿÿ1ÿUÿDÿ9ÿ)ÿÿEÿ(ÿ,0

S DPÿÿKH0ÿ)ÿ?EÿB7B.0ÿ,-0ÿD7D.DT S DRÿÿ3H0ÿ)ÿ?EÿB<0ÿ,-0ÿD
ÿ8-)ÿEÿ11ÿÿÿ1ÿ0ÿU U U

LGÿ3ÿÿK3

D

L3 L2 3ÿÿK4ÿÿK3KG

D7 D. DT D< DO

01213443ÿ3642ÿ78

L3 L2

DP

3ÿÿK4

DR

KG

D7 D. DT D< DO

93  ÿ 

M

„-

Aÿ0=,ÿ0-ÿÿÿÿÿÿ,ÿ)ÿÿÿÿÿÿ 0ÿ)ÿ-ÿ,-0 N) ÿ)ÿ1-,ÿÿÿ)ÿÿ0ÿ=,,ÿ9 ÿ …=8--E ÿ)ÿÿ0ÿ10, ÿ0ÿ0-ÿÿ-ÿ IJ1-6ÿÿ0-ÿ?Eÿ3 ÿ)ÿ1-,ÿÿ)ÿ3ÿ90ÿ=,,

01213443ÿ3642ÿ78

3ÿÿÿ2

L4ÿÿÿLGÿÿÿ3 L3 L2

3ÿÿÿ2

L4ÿÿÿLGÿÿÿ3 L3 L2 93  ÿ 

3ÿÿÿK3ÿÿÿKG

3ÿÿÿ2

L4ÿÿÿLGÿÿÿ3 L3 L2

3ÿÿÿK4 K3ÿÿÿKG

01213443ÿ3642ÿ78

D

D

93  ÿ 

2

-Eÿÿ@

Aÿ0-ÿÿ8-)ÿÿGH0ÿD)ÿÿ1-ÿ16

LGÿÿÿ3

3ÿÿÿ2

L4ÿÿÿLGÿÿÿ3 L3 L2

VWXYZ[\]^/_`abcb`dB4ÿC$ 7efgÿhgijklÿm!jÿngoÿBp!ÿ!kipgÿplgÿ qrhgjpq!rÿr!sgÿD .efgÿissÿplgÿrgtÿqpguÿB4ÿC$ÿipÿr!sgÿD Teÿv][WwCD`axyCzD$ [{ÿ/_}CCbD$ kjgipgÿiÿrgtÿgu~poÿj!!pÿi!€gÿD Dÿ _‚y/bD$

01213443ÿ3642ÿ78

LL

% % %

ÿƒ!"ÿ$ÿ  +1ÿLÿ?ÿ!"ÿ$ ÿ(,=ÿ)ÿ8ÿ !"ÿ$0 +1ÿ3ÿ?ÿ7$ +1ÿKÿ?ÿ!"ÿ$ ÿ(,=ÿ,ÿ1-ÿ ?ÿ7$ÿ0ÿ)ÿ 1ÿ!"ÿ$ÿ1-

= ÿÿÿÿÿ 93  ÿÿ?ÿ!"ÿ$ 

93  ÿ 

L4

„-ÿÿÿÿÿ0ÿDEÿ,=ÿÿ=0-) ÿ)ÿ 0ÿD(,ÿÿLH0ÿ)ÿÿ,-0ÿ0ÿÿ?E

ÿ0-ÿÿ=0-)ÿÿ0ÿDÿ)ÿ1ÿU ÿ)ÿ,0ÿ)ÿ , ˆÿL6ÿ0‰,ÿ(-ÿÿDÿ3H0 %

‡=ÿ16)ÿÿD)ÿÿ0‰,ÿ(-ÿz0ÿ8ÿ ÿÿÿUÿÿ0ÿ0ÿDP ÿÿ= ÿÿ=0-)ÿEÿ11ÿÿÿ1ÿU

U MÿÿL

3ÿÿGÿÿ

K3ÿÿÿKG

%

†0-)ÿ0ÿ‡= %

3ÿÿÿK3ÿÿÿKG

&ÿƒ(ÿÿ93  ÿÿ )ÿ

01213443ÿ3642ÿ78

z

L4

D 93  ÿ 

UM

3ÿÿGÿÿ

L4ÿÿL L3

DP

ÿÿ 

.0ÿÿ1

ÿÿÿÿÿÿÿÿ!ÿ" ÿÿ#ÿ ÿ# $ÿ36ÿ%#ÿ&'ÿ(ÿÿÿ)ÿÿÿ) *

*

ÿ!6 +ÿÿÿ,-ÿÿ#ÿÿ(ÿ 3+ÿÿÿ,-ÿÿ,ÿ,ÿ"ÿ +ÿÿÿ,-ÿÿ,ÿ,ÿ(ÿ" .ÿÿ ÿÿÿ##

3 01213443ÿ3642ÿ78

( 0ÿÿ2



"

ÿÿ2

3

0

(

93  ÿ 



/



<,!,'ÿÿ1#0

$,!ÿÿ#ÿ#0ÿ,!, Q# < 1 U Tÿ @ @ @ ÿÿ#0ÿ

& JRNJHFJS JRNJHFJS JRNJHFJS ,,!ÿÿ,!, , Kÿ Q?!ÿ2 LM798L9ÿNÿD48OP LM798L9ÿNÿD48OP LM798L9ÿNÿD48OP ,! ÿÿ,!, 93  ÿ 789ÿ4 789ÿ4 789ÿ4

 C8DEFGHIEJ C8DEFGHIEJ C8DEFGHIEJ

01213443ÿ3642ÿ78

93  ÿ 

=ÿ-ÿ56789ÿ4;ÿÿ#ÿÿÿ,ÿ #ÿÿÿÿ, * =ÿ ÿÿÿÿÿÿÿ56789ÿ4;  ÿÿ&0ÿÿ,ÿÿ * >#ÿ ÿÿÿ?ÿ56@;, *

"

ÿÿ/

2ÿ3&ÿÿ93  ÿÿÿ4 , *  ÿ356789ÿ4;ÿ' <ÿÿÿ!

#,!Bÿÿ,!, A

 ÿ'ÿÿ,ÿ,ÿÿ93  ÿÿ?ÿ 56789ÿ4;, 01213443ÿ3642ÿ78

93  ÿ 



Balanced search trees: 2-3-4 trees.

Example 2-3-4 tree

2-3-4 (or 2-4) trees improve the efficiency of insertItem and deleteItem methods of 2-3 trees, because they are performed on the path from the root to the leaf. However, they require more memory for storing 3 data items and 4 pointers in each node node. Definition: A 2-3-4 tree is a general tree which satisfies the following properties: 1 Each node may store three data items. 2 Each node may have four children. 3 The second and third data items in any node may be empty, in which case sentinel value emptyFlag is stored there (assume emptyFlag := 0). If they are not empty, the first data item precedes the second one according to the specified ordering relationship relationship, the second data item precedes the third data item. 4. For each node, data in the first child precedes the first data item in the node; data in the second child follows the first data item, but precedes the second; data in the third child follows the second data item, but precedes the third; data in the fourth child follows the third data item. 5 All leaf nodes are on the same level.

Search in 2-3-4 trees The search algorithm is similar to that in 2-3 trees and binary search trees. In the example 2-3-4 tree, the search for 10 is carried out as follows: 1 1. 2. 3.

Compare 10 to the only item in the root root. 10 > 4 4, continue the search in the second child. 10 > 6 and 10 > 8, continue the search in the third child. 10 > 9, 10 = 10. Stop.

As in 2-3 trees, the efficiency of the search operation is guaranteed to be O(log n). On average, it will be better that the search efficiency in 2-3 trees because the height of a 2-3-4 tree might be less than the height of the trees, 2-3 tree with the same data.

4 2 1

6 8 3

5

7

9 10 11

Class Node234tree { Node234tree firstChild; Node234tree secondChild; Node234tree thirdChild; Node234tree fourthChild;; Node234tree parent; int firstItem; int secondItem; int thirdItem; .... class methods follow }

Insertion in 2-3-4 trees Step 1 Search for the item to be inserted (same as in 2-3 trees). Step 2 Insert at the leaf level. The following cases are possible: • The termination node is a 2-node. Then, make it a 3-node, and insert the new item appropriately. • The termination node is a 3-node. Then, make it a 4-node, and insert the new item appropriately. • The termination node is a 4 node. Split is, pass the middle to the parent, and insert the new item appropriately. General rules for inserting new nodes in 2-3-4 trees: Rule 1: During the search step, every time a 2-node connected to a 4-node is encountered, transform it into a 3-node connected to two 2-nodes. R l 2 Rule 2: During D i the h search h step, every time i a3 3-node d connected d to a 4 4-node d is encountered, transform it into a 4-node connected to two 2-nodes. Note that two 2-nodes resulting from these transformations have the same number of children as the original 4-node. This is why the split of a 4-node does not affect any nodes below the level where the split occurs.

1

Efficiency of search and insert operations Result 1: Search in a 2-3-4 tree with N nodes takes at most O(log N) time. This is in case if all nodes are 2 nodes. If there are 3-nodes and 4-nodes on the tree, the search will take less than (log N) time. Result 2: Insertion into a 2-3-4 tree takes less than O(log N) time, and on average requires less than 1 node split.

Deletion in 2-3-4 tree Consider our example tree 4 2 1

6 8 3

5

7

9 10 11

The following special cases (with multiple sub-cases each) are possible: Case 1 (three sub-cases): The item is deleted from a leaf node (a node with external children), which currently contains 2 or 3 items. Easy sub-cases – delete the item transforming a 4-node into a 3 node, or a 3 node into a 2 node. No other nodes are affected. Example: delete 9 – the existing 4 node, containing 9, 10, and 11 is transformed into a 3 node, containing 10 and 11. Deleting from a 2-node (the third sub-case) requires an item from the parent node to be drawn, which in turn must be replaced by an item from the sibling note (if the sibling node is NOT a 2-node as well). See case 2.

Deletion in 2-3-4 tree (contd.) Case 2 (with several more sub-cases) Delete from a node that has non-external children. For example, delete 8. This case can be reduced to case 1 by finding the item that precedes the one to be deleted in in-order traversal (7, in our example) and exchanging y the two items. If 7 were part of a 3- or 4- node, 8 would have been deleted easily. However, since 8 is now the only item in the node, we have a case of underflow. This requires that an item from the parent node be transferred to the underflow node, and substituted in the parent node by an item from the sibling node. In our example, 7 will be transferred back to where it was, and 9 will move to the parent node to fill the gap. However, if the sibling node is also a 2-node, the so-called fusing takes place. That is, the two 2-node siblings are “fused” in a single 3-node, after an item is transferred from the parent node node. The later suggests that the parent can now handle one less child child, and it indeed has one child less after two of its former children are fused. The last sub-case suggests that a parent node is also a 2-node. Then, it must in turn borrow from its parent, etc., resulting in the 2-3-4 tree becoming one level shorter.

2