22

Optimal Binary Search Trees with Costs Depending on the Access

  • Upload
    others

  • View
    4

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Optimal Binary Search Trees with Costs Depending on the Access

��������� � ���������� ���������� �������! �"#�$��� %�&� '�( ) ���*�+�-,.�/��0 &1� ������2#�����! ( #3�4�5�6 87

9;:=<?>A@CB�D!EGFIH�:�JLKIM�NL@OJQP R�S�TUFV:XWYS Z-:V[�:�J\JLS�]^6_YK`:�JLa�SAbc:�@OF=:edgfc:hNL@`i ] 9�S5jk iL: aU@lE�D�m-WY_n[�@V_nJo:;p

qr:XWsNQ@OJutwv�T;NQS;x Zljk [?_YSzy!_n[?_{:XT�_$|

}�~X�������I������!���$�Y���Y���Q�����������Y�����\���;���/�?�����L�n���Y�L�������\�+�/ ����������V�\���Q���Y¡¢���$���Y�{�¢�Y���$�$�$£¤���

¥ �L���{�¢�Y�\�¦�/�����§���(�����s�G���h��¨��$¡4�\�� o���L�\�(���¢�Y�\��©ª \���§���§�����L�«¨��$¡¬� ¥ �\���{� ¥ �$����Y�$�/�{�\�$�1���w���\�4 L�����w�����­�§®w¯��\�°�� \���/�\�����±�L�/���� \ \�����$���Y���/�L�5�Y�²�n�§���{�{�\���L�³������$�����L�L���Y¡1�!���!���Y¡w���L�����/�Q�����°���$®-¯ ¥ �²¨¬���Q�\�«���U�/ ����������;�Y���$�$�����Y�³�����Q�n�°�¬´�$���§�µ£��L�����$��¡+�� ��Y������� ¥ �/�Y�n���$�����?���Y���$�;���L� ¥ �$���/�/�Y�$�4�g¶��$�Y�����(�$�����?���Y���$�$®e¯��\��Y���!�����Q���� L�����������! \����·��������$�?���X�Q�����¸���������Y�����\���U���Y��¹!º¼»O½¿¾IÀ�Á?���L�¸¹!º�»O½¿¾VÂ$Á�£�Y�$�� o�$�¿�Y��¶/����¡�®8¯��L�!�����/���Y�­�Y�\���(�������L�/�n�§�³�����¢�����¬¶/���\�������?�\�$���/�! Q���n�������������L��{�Q���{���¿�Y���Y��ç���Y���/�L�5���?���$Ä��\���Q���$�!���(¨/��¡�� ¥ �\���{�����Y�4 L���Y�L�����U�n o�$�������;¨¬���L�L�!����L���L����¡����$���Y�{�!�Y���$�$�$®=ÅV���L������¡�£¬�L�����\�����$�\���{���Y���L�����\�L���������L�$£ ¥ �? \�Y�$�������X���+��·��/�¿����L����¡��n�°�X���V���\���¬�\�¦�Q�$�;���=�s�Y�� L�; o���������Y�!�$���¬¡����\�5�����/���Y�­�Y�\����®

ÆuǵÈÊÉÌËÎÍQÏGÐoÑ8ÒoÓÕԤ֤קؼÙgÚ=ÛcÜ�ÝOÖ¤ÞVÙ§ØßÛwÒoÓXàVØßáeÒo×�â6ܧã�Òoקä�ÚuÙg×$ã�ã�Ü/ÝÎÔ¤ã�á=ã/×�åÒQÙgØÕá=Ô¸æsç=á=ä�ÙgØßÖoá=Ü�è

é�¯��L���; Q�� o���;�L�/���Q�$���¢ L�������°������¡+�n�L \ Q�/�n�Y�$���¬¡+ \�Y��ês�§�¿�Gëhì?¯;íhîCïGðnð¿®�ñ$ò�ó'ðsô�ðsî(ð¿®õ�ö �\��¶����{�����\�/���(ÅL�$���$�Y���µ����ó'��������÷/���\�������Q£�ðø�L�n�������\�������Uù³���Y����ú���Y���$�\£�û?ëXíü���L�¢ë;ý?þhþ�í'£ëX����·��²þ=���s�{���(ÿ��/ÿ��L£'ÿ������\ñ�´ ò�����ó;���ü��� ÷����\�$���Y�L£;ó'÷Q£�ôX�{�������ß®Cíe´ ��������ên�g¡¬�!���(�L����® �����¼ê�® �\�§®þe�������°������¡G���\ \ o�������§���¬¡G�Y�\�Xë��/�L�n�$���L�GûG�/�������L�������hî(�$�����¬¶��/��¶¬���!�������(ë��������gú �� ���;��¯`�$���\���§ú���/�����L£ëXûGþhÄo£����Q��Å\�\�L�L���������G�����'�! L���Y����'þ=�§��Ä��\�°�Y�;���Gíh�n�Y�/���'���?ó;���(����÷����\�$���Y�L£§Å��Gþ�íhó'÷Q£$ôX�{�������ß®

� î(�� Q�����Y���!�$�/�Y�(���'ë������L�����/�`���X�°�Uë��/�� L���Y�/���§ú���I£ ö �L��¶/���{�n�°�\���8���;ë��L������®=ôX�����L���?íÎ�L�$���°���\�ÿ�ñ§ÿ��\£��\�������°���/�L£Vë��\������®¢íe´ �!��������$�/�L�g¶����Y���Q£ �Y�L����Ã$�����?�\�$��® �L�{�\�����/® ���Õ®¦þe�������°������¡ ���\ \ o�������§����¡Å\���Q���$��¡/�! ?�{�����'ò�ò�´"��#/ÿ$�¬®

% ö �\��¶����{�����\�/����Å\�§�����{���I����ó;�������5÷����\�$���Y�L£Lë;ý?þhþ�í'£\ëX����·\��þ=���s�{����#�&$'�ñ/ñ�£�ÿ�ñ$ò��$'�´ ò�����ó;������5÷/���\�����Y�L£�ó'÷Q£\ô��{�������Õ®eíe´ �������oês�/���Y�$�?���/�$® �����Õê�® �\�$®( î(�� \���L®r���6ë��/�! \���Y�/���§ú���I£ ö �\��¶/���{�n�°�\�/�)�¬���üú�/� ôX��� ú ¶����§£��' Q�����Y���\�*&�ò������\£�ëX���Y�/�����$£

ïe���\�$Ã��\�$���L®Îíe´ �!������=�����­�Y��� ë��\�������(���{¨¬���L�n�$¡�® ���/�4®+ ö �\��¶����{�����\�/��� ÅL�$���$�Y���(����ùª���Q���, ?���{���°��£;î(�� L���n�{���!�������w���¸ë��-���Q���°�1�\�wë��/�� L���Y�.�������Q£

�\ñ§ÿ$����´"�Lñ/��ôX�����10'���Y��Ã������Y��£Iù2 �£OôX�{�������ß®¦íδß��������U�\��¶¬�����?�\�$��® �����!�L® �\�§®�þe���n�Y��������¡ª�n�\ L Q�/�n�Y�$���¡3��ð4�Gùr \����ês�$�����/�Y���/�!ù�ëX¯65�ÅVðsû(íhþ�5/ëXûGþ�Ä�5�þhó'ý?ûGí879��#L® ò��¬®�ñ/�\ñ:#\® ���¢���Q�üëXûGþ�ĸ���{�����'�ÿ��L® òLñ/#�5�ò���´"&L®

;

Page 2: Optimal Binary Search Trees with Costs Depending on the Access

� ������������ ��������

�¦ØßáeÒo×�â-Ü$ã¬Òo×$ä�Ú*٧קã/ã�Ü¢æsÖ¤×$Û Ö¤á=ã�Öoæ5ÙgÚ=ã¸Ù§Ö¤Þ=Øßä/ܪÛwÖoÜ$Ùªä/Ö¤ÛwÛcÖ¤á=Ó¼â�Ü$Ù§ç��=Øßã��CØßá ä�ÖoÛ1åÞVçVÙgã/×�ܧä/Øßã/á=ä�ãQÝUÞ=קÖoàeÒoà=Ó¼â��=ç=ãwÙ§ÖuÙ§Ú=ã�ØÕ×��«Ø��=ãc×gÒoá=ÔoãüÖoæ!ÒoÞ=Þ=ÓÕØßä¬ÒLÙgØßÖoá=Ü�è���ÚVã�Øß× ØßÛ²åÞhÖ¤×�Ù�Òoá=ä/ã�ä�Òoácà�ã�ÒoܧÜ$ã�Ü$ܧã��6àµâcקã�Ò��=ØÕá=ÔªÙgÚ=ã+ä�ÓßÒoܧÜ$Øßä¬ÒQÓeà�ÖOÖ��Iܦàµâ��ªáIçVÙgÚ �"!VÝ$#&%Yè'��ÚVãÜ�Ùgç��`âlÖoæ«Ö¤Þ`ÙgØßÛwÒoÓ��¦ã�ØßÔoÚIÙ§ã�� à=ØÕáeÒo×�â Ü$ã¬Òo×$ä�Ú Ù§×§ã/ã�Ü(�eÒLÙgã�ܲà=Òoä)� Ù§Ö-ÙgÚ=ã+*=æøÙgØÕã�Ü�è�,Ù§çVÙgÖo×§Ø ÒQÓXÖ¤á�ÙgÚ=ØÕÜ�ܧç=à.-$ã�ä/Ù�ÚeÒoÜ«àhã�ã/á/�«×$ØÕ٧٧ã�áuàµâ04ÒoÔ¤Òo×gÒ&-1� ;32 %�ÝeÛwÖ¤×$ãª×§ã/ä�ã�áµÙ§ÓÕâ¤è45Òoä�Ú á=Ö5�=ã�Öoæ�ÒCàVØßáeÒo×�âlÜ$ã¬Òo×$ä�Ú Ù§×§ã�ã�ä�Òoá à�ã�ÒoÜ$ܧØÕÔ¤á=ã��ÊÒoá Òoä/ä�ã�Ü$Üwä/Ö¤Ü$Ù1Öo×1Ò

�¦ã�ØÕÔ¤ÚµÙ¬Ý6�«ÚVã�קã�ÙgÚVã.ÓßÒQ٧٧ã�×1ä¬Òoá קã/Þ=קã/ܧã/áIÙüÙgÚ=ã.Òoä�ä/ã�Ü$ÜüÞ=×$Ö¤àeÒoà=ØÕÓßؼٿâlÖoæ�ÙgÚ=ã�á=Ö5�=ãoè7 ؼÙgÚuÒoä/ä�ã�Ü$Ü�ä/Ö¤Ü$٧ܫ֤á=ã³ÛüÒ¬âüà�ã³ØßáµÙ§ã�קã/Ü$Ù§ã��-ØÕá6Ö¤ÞVÙ§ØßÛcØ98�ØÕá=Ô�Ù§Ú=ã:��Ö¤×$Ü$Ù+ä¬ÒQܧã³Ö¤×!ÙgÚVãÒ<;oã�×gÒQÔ¤ã!ä¬ÒQܧã�ä/Ö¤Ü$Ù�Ý��«Ú=ã/קã!ç=áVØÕæsÖ¤×$Û Òoä�ä/ã�ܧÜ?Þ=ק֤à=Òoà=ØßÓÕØÕÙ¿âªØÕÜ?ÒQܧܧçVÛwã���è>=¿á�Ù§Ú=ã�Ü$ã�ä/Ö¤á��ä�Òoܧã³Ö¤áVã³ÒoܧÜ$ç=Ûwã/Ü�ÙgÚeÒQÙ�ÙgÚ=ã Òoä/ä�ã�Ü$Ü«ä�Ö¤Ü�Ù«ØßÜ�ç=á=ؼæs֤קÛuÝ`Òoá���ØÕÙ�ØÕÜ!Þh֤ܧÜ$Øßà=ÓÕã4ÙgÖcÒoÜ$ܧØßÔoáÞVק֤àeÒQà=ØßÓÕØÕÙgØÕã�Ü�Öoá=ÓÕâ¢Ù§Ö4ØÕáIÙ§ã�×$áeÒoÓµÙg×$ã�ã8á=Ö?�Vã�Ü6@nܧçVä�ä�ã/ܧÜ�æsç=Ó=ܧã�Òoקä�ÚVã�Ü)A�ݵ֤á=Ó¼â¢ÙgÖ�ãCBOÙgã/קáeÒoÓ٧קã/ã�á=Ö5�=ã�ÜD@nç=áVܧç=ä/ä�ã�Ü$Ü$æsç=ÓeÜ$ã¬Òo×$ä�Ú=ã�ÜEA(Ö¤×GÙgÖ4àhÖoÙ§Ú�è>F(ØßáeÒoÓÕÓÕâoÝ&�¦ã�ä�Òoá¸ä/Ö¤á=ܧØ��=ã�×?Ò�Ûc֤קãÔoã�á=ã/×gÒoÓ;ÛcÖ?�Vã�ÓYÝ5�«Ú=ã�×$ã�àhÖoÙ§Ú.ÒQä�ä�ã/ܧÜ+ä�Ö¤Ü�ÙgÜ�Òoá����ã/ØßÔ¤ÚµÙ§Ü�ÒQקã³Øßá=ä/Óßç��Vã���è,�á ÒoÓßÔo֤קؼÙgÚ=Û æsÖ¤×wä/Ö¤á=Ü�ÙgקçVä/ÙgØÕá=ÔlÒQáAÖ¤ÞVÙ§ØßÛwÒoÓ�à=ØÕáeÒo×$â Ü$ã¬Òo×$ä�ÚAÙg×$ã�ã.ÚeÒoÜüàhã�ã/á

*=קÜ$ÙG�Vã�ܧä/קØÕà�ã��6àIâIH³ØÕÓßàhã�×�Ù!Òoá$�/J.Ö`ÖoקãK� ; %�ÝVæs֤צ٧Ú=ãªä¬ÒQܧãªØßá+�«Ú=Øßä�Ú6ÙgÖ²ã�Òoä�Ú�oã�â�ØßÜÒQܧܧØÕÔ¤á=ã��wÒL�¦ã�ØÕÔ¤ÚµÙ¬è'��Ú=ã«ä/Ö¤ÛwÞVÓßãCB`ؼٿâ¸ÖoæÎÙgÚVØßÜ5ÒoÓÕԤ֤קؼÙgÚ=Û ØÕÜNM�@PORQSA�è>�ªáOç`ÙgÚT�VUW%=ä�Ö¤á`åÜ$Ø9�=ã/קã���ÙgÚVã8ÛcÖ5�=ã�ÓµÖoæ=Òoä�ä/ã�Ü$Ü?Þ=×$Ö¤àeÒoà=ØÕÓßؼÙgØßã/ÜXØÕá=ä�ÓÕç��=ØßáVÔ�ܧç=ä/ä�ã�Ü$Ü$æsç=ÓVÒoá���ç=á=ܧçVä�ä�ã/ܧÜ�æsç=ÓÜ$ã¬Òo×$ä�Ú=ã�Ü/èYX�ã�ÞVקÖ3;¤ã�� Òoá-ã/Óßã/ÔµÒoáµÙ+ÛwÖ¤áVÖoÙgÖ¤áVØßä�ؼٿâ�Þ=×$Øßá=ä/ØßÞ=ÓÕãoÝ��«Ú=ØÕä�Ú �=ã/ä�קã�Òoܧã��-ÙgÚVãä/Ö¤ÛcÞ=ÓßãSBVؼٿâ àIâ�Ò�ænÒoä�ÙgÖ¤×(ÖoæZM�@[O\A�è]7 Ú=ã/á²Ö¤á=ÓÕâ ç=áVܧç=ä/ä�ã�Ü$Ü$æsç=ÓÎÜ$ã¬Òo×$ä�Ú=ã�Ü5Òo×$ã!קã/ÓßãC;oÒQáIÙÒ1�=Ø_^Xã/קã�áµÙ�ÒoÓßÔo֤קؼÙgÚ=Û ä¬Òoáwà�ã+ÒoÞVÞ=ÓßØÕã���ÝOÒoÜN�=ã/ܧä�×$Øßàhã���àµâ�X+ç�Òoá����Gç=ä)�oã/×1�a`&%Yè'��ÚVãä/Ö¤ÛcÞ=ÓßãSBVؼٿâ ÖoæeÙgÚ=ã�Ó ÒQÙ$Ùgã�×(ÒoÓÕԤ֤קؼÙgÚ=Ûb��ÒoÜ�Mc@PORdSA�ݤàVçVÙ�ØÕÙ(ÚeÒoÜ?à�ã/ã�á²Ü§ÚVÖ&�«á²Ù§Ö³Ò��=ÛcØÕÙÒQá ØßÛcÞ=Óßã/Ûwã/áIÙgÒQÙgØÕÖ¤á�קç=áVá=Øßá=ÔüØßá�Mc@POªÓßÖoÔ�O\A«Ù§ØßÛcãI�V#e%�è:F?Øßá=ÒoÓßÓ¼â¤Ýf��ã1ÒQÓßܧÖüÛwã/áIÙ§ØßÖ¤áÙ§ÚeÒQÙ¦ÙgÚ=ã¢ÞVק֤à=ÓÕã�Û Öoæ'ÒQÞ=Þ=קÖ<B`ØßÛwÒQÙ§Øßá=Ô Ö¤ÞVÙ§ØßÛwÒoÓf��ã/ØßÔ¤ÚµÙgã��6à=Øßá=Òo×$âcܧã�Òoקä�Ú�٧קã/ã�Ü!ÚeÒQÜàhã�ã/á.ä/Ö¤á=Ü$Ø9�=ã/קã��.àµâ6ܧãC;¤ã�קÒoÓGÒoçVÙ§Ú=֤קÜ/èhg`ã�ãc�Vi`ÝfjW%�Ý=æsÖ¤×�Øßá=Ü�Ù�ÒoáVä�ãoè=¿áuÙgÚ=ØÕÜ�ÞeÒoÞhã�×�Ýf�¦ã�ä/Ö¤á=Ü$Ø9�=ã/׫٧Ú=ã Þ=ק֤àVÓßã�ÛcÜ�Öoæ]*eá��=ØÕá=ÔwÖoÞVÙgØÕÛüÒoÓ�à=Øßá=Òo×$âüܧã¬ÒQקä�Ú

٧קã/ã�ܳØßá �«Ú=ØÕä�Ú ÙgÚ=ã1Òoä/ä�ã/Ü§Ü ä�Ö¤Ü�ÙªÙgÖ�ÒI�oã�â kml:�=ã�Þhã�á$�=Ü�ÖoáCÙ§Ú=ã�n�Þ=קã/ä�ã��=Øßá=Ô�Qã/âOÜ�«ÚVØßä�ÚI��ã/קã³×§ã�Òoä�Ú=ã��uØÕá�ÙgÚ=ãªÞ=ÒQÙgÚ�Ù§Ö(kml¬è'7 ãªÞhã�×$ÛwؼÙ!ÒQקà=ؼÙg×gÒQ×$âüÒoä�ä/ã�ܧܫÞ=×$Ö¤àeÒoàVØßÓßØ�åÙ§Øßã/ÜD@sØßá��=ã/Þ�ã/á��=ã/áIÙ?Ö¤á³ÙgÚ=ã¦Þ=קã/ä�ã��VØßá=Ôo�oã/âOÜEA?ÒoÜ���ã/ÓßÓYèp��Ú=ã¦ä�Ó ÒQܧܧØÕä¬ÒoÓµÖoÞVÙgØÕÛüÒoÓoà=ØßáeÒQ×$âÜ$ã¬Òo×$ä�Úw٧קã�ã+ä�Öoá=Ü$٧קç=ä�ÙgØßÖoáwàµâ+HªØßÓßàhã�×�Ù5Òoá��cJ.ÖO֤קãq� ; %hÒoá��c�ªáOç`ÙgÚT�VUW%Îä/֤ק×$ã�Ü$Þ�Ö¤á$�=ÜÙ§ÚIç=Ü�ÙgÖ¸ÙgÚVã³æsçVá��eÒoÛcã�áµÙ�ÒQÓ�ä¬ÒoÜ$ãqn�r 2 è�=¿á6ÙgÚ=ØÕÜD��Ö¤×s�+�¦ã Òoקãªä/Ö¤á=ä�ã/קá=ã��t�«Ø¼ÙgÚ�ÙgÚVã;QÒoÓÕç=ã�Üunwv ; è��D��Ö��IØßá$�=ܸÖoæ+Ö¤ÞVÙ§ØßÛwÒoÓ�Ùg×$ã�ã�Ü1ÒQקã�ä/Ö¤á=ܧØ��=ã�×$ã���Ý5áeÒQÛwã/ÓÕâ*Ö¤ÞVÙ§ØßÛwÒoÓ�¦Ö¤×$Ü$Ù¢ä�Òoܧã Ùg×$ã�ã�Ü4Òoá��T�¦ã�ØÕÔ¤ÚµÙgã�� Ò<;¤ã�קÒoÔ¤ã�ä¬ÒoÜ$ã�Ùg×$ã�ã/Ü�èY��Ú=ã�ØÕá=Þ=çVÙ§Ü�Öoæ?ÙgÚ=ã/ܧã�ÞVק֤à`å

`

Page 3: Optimal Binary Search Trees with Costs Depending on the Access

ÓÕã�ÛcÜ4ÒQקã¸ÒwáOçVÛ¸à�ã/× O Öoæ��oã�âOÜ�Ý�ÙgÚVãq;QÒoÓßçVãun�Ý ; � n�� O(Ý�Òoá���Òwä�ÖoÜ$Ù³ÒoÜ$ܧÖOä�ØßÒQÙgã��Ù§Ö¸ã¬ÒQä�ÚuÞhÖ¤Ü$ܧØßàVÓßã+ܧã��Iç=ã/á=ä�ã³æsÖ¤×$Ûwã���àµâ�ÒQÙ�ÛwÖoÜ$ÙGn�� ; �Qã/âOÜ�ÝÎÒoÓÕÓÎÖoæ;ÙgÚ=ã/Û �VØßÜ$Ù§Øßá=ä�Ù¬èFe֤ע٧Ú=ãK��ã/ØßÔ¤ÚµÙgã��lÒ<;¤ã/×gÒoÔoãwä�ÒoܧãcÛwØÕá=ØßÛcØ98�ÒQÙgØÕÖ¤áuÞ=ק֤àVÓßã�ÛuÝ'ã¬Òoä�Ú �oã�âCØßÜ Ò����=ؼÙgØÕÖ¤á`åÒQÓßÓÕâCÔoØ�;¤ã/á Òt��ã/ØßÔ¤ÚµÙ�è�+ܧçeÒoÓÕÓÕâoÝUܧç=ä�Ú ÒT�¦ã�ØÕÔ¤ÚµÙ(��Öoç=Ó9� ×$ã�eã/ä/Ù1ÙgÚ=ãwæsקã��Iç=ã/á=ä/âlÖoæÒQä�ä�ã/ܧÜ$Øßá=ÔuÙgÚ=ãK�oã�â¤è �¢à=ܧã/×s;¤ãcÙgÚeÒLÙ Ù§Ú=ã1Øßá=ÞVçVٳܧØ�8�ã1ԤקÖ3�«Ü³ãCB`ÞhÖ¤á=ã/áIÙ§Ø ÒoÓÕÓÕât�«ØÕÙgÚ n�ÝÒQÜ+ؼÙ�ØßÜGMc@PO������sA�è7 ãI�=ã�Ü$ä�×$Øßàhã6ÒoÓßÔo֤קؼÙgÚ=ÛcÜ æsÖo×�ܧÖoÓ�;OØßá=Ô.ÙgÚ=ãüÙ§Ú=ã6Þ=×$Ö¤à=Óßã/ÛwÜ�Öoæ�*eá��VØßá=Ô�Ù§Ú=ã�Ö¤Þ`å

Ù§ØßÛwÒoÓ'�¦Ö¤×§Ü�Ù²ä¬ÒoÜ$ãw٧קã�ã/ܲÒoá�� ��ã/ØßÔ¤ÚµÙgã�� Ò<;¤ã�קÒoÔ¤ãwä¬ÒoÜ$ãüÙg×$ã�ã�Ü/èT��Ú=ãüä�Ö¤ÛcÞ=ÓßãSB`ØÕÙ¿âCØßÜMc@PO ��� d)A�æsÖ¤×�àhÖoÙgÚüä¬ÒoÜ$ã�Ü�èN��Ú=ã4ãCBOÙgקҸܧÞeÒoä/ã¢á=ã/ã��=ã��uØÕÜDMc@PO ����� A�è���ØÕÛwã�Òoá��6Ü$ÞeÒoä/ãä/Ö¤ÛcÞ=ÓßãSBVؼÙgØÕã�Ü�Òo×$ã³Þ�Ö¤Ó¼âOá=Ö¤ÛcØ ÒoÓhØßá�Ù§Ú=ã³Ü§Ø98/ã³Öoæ(Ù§Ú=ã³Øßá=ÞVçVÙ¬è��Ú=ãüÖ¤ÞVÙgØÕÛüÒQÓ8àVØßáeÒo×�â*ܧã¬ÒQקä�ÚlÙg×$ã�ãüæsÖo×un r 2 Òoá�� �«Ø¼ÙgÚlçVá=ØÕæsÖ¤×$Û �oã�â Òoä/ä�ã�Ü$Ü

ä/Ö¤Ü$Ù§Ü�Ý�ÒoÜ+ä�Ö¤á=Ü$Ø9�=ã/קã���Øßá � ; ÝRUe%YÝÎØßÜ+ÒcÛwÖ5�=ã�Ó�æsÖo×+Ü$ØÕÙ§çeÒQÙgØÕÖ¤á=Ü«Øßá�«Ú=ØÕä�Ú-ÙgÚ=ã��oã�âOܪÒoקãØÕá Ù§Ú=ãüÛwÒoØßá*Ûcã�ÛcÖ¤×$âoèTHª×§ã�ÒQÙgã/×�;QÒoÓÕç=ã�Ü�ÖoæYn ÒQá��lÒo×$à=ØÕÙ§×gÒo×�â*Òoä�ä/ã�Ü$ܲä�Ö¤Ü�ÙgÜ�ä/Ö¤ç=Ó��ÛcÖ5�=ã�ÓhÙgÚ=ãªä�Òoܧã/Ü+ØÕá��«Ú=Øßä�Ú�ÖoÙ§Ú=ã�×6�OØÕá���ÖoæGÛwã/ÛwÖoקØßã/Ü!Òo×$ãªØßá ;¤ÖoÓ�;¤ã���èNFeÖ¤×!ãSB=ÒQÛwÞ=ÓÕãoÝ�«ÚVã�á.ÒoÓßÓZ�oã�â`Ü+Òo×$ãªÜ$٧֤קã��uØÕá�Ò(�=ØßÜs�ÎÝVÙgÚ=ã³ÒQä�ä�ã/ܧܫä�ÖoÜ$Ù�ÙgÖ1Ò¸ÔoØ�;¤ã/á�oã/â��=ã�Þhã�á��VÜ+ÖoáÙ§Ú=ãcÞ�Ö¤Ü$ØÕÙ§ØßÖ¤áCÖ¤á*ÙgÚ=ã��=ØßÜs�CÖoæ�Ù§Ú=ã+�Qã/â Þ=קãC;OØßÖ¤ç=Ü$ÓÕâ*Òoä/ä�ã/ܧܧã���è��Ú=ã�×$ã/æsÖ¤×$ãoÝ>*=á��=ØßáVÔÒQá Ö¤ÞVÙgØÕÛüÒQÓG٧קã�ã(�«ÚVã�á*ÒoÓßÓ]�oã�â`Ü Òo×$ã²Ü$٧֤קã��*ØÕáCÒ��=ØßÜs�/�¦Ö¤ç=Ó��Cä�Ö¤×$קã�Ü$Þ�Öoá�� ÙgÖ�ÙgÚVãä�Òoܧãuntr ; èL=¿á�ÙgÚVØßÜ4Ü$ØÕÙ§çeÒQÙgØÕÖ¤á�ÝÎÙgÚ=ã�Øßá=Þ=ç`٢ܧØ�8�ã¸ØÕÜLMc@PO d)A�Òoá���Ù§Ú=ã�ä/Ö¤ÛcÞ=ÓßãSBVؼٿâuÖoæÙ§Ú=ã1Þ=קÖoÞ�Ö¤Ü$ã�� ÒoÓßÔo֤קؼÙgÚ=Û ØßÜ1Mc@PORQSA�èKFe֤תãSB=ÒQÛwÞ=ÓÕãoÝ�Ù§Ú=ØßܪØÕÜ¢ÙgÚ=ã1ä¬ÒQܧã1æs֤ת֤ÞVÙ§ØßÛwÒoÓÜ$ã¬Òo×$ä�Ú=ØßáVÔ-Ü$Ù§×gÒQÙ§ã�Ô¤ØÕã�֤ܳá ܧ֤Ûcã²ÙgãCBOÙ�Øßá��VØßä�ã/ܳÜ$ÙgÖoקã�� Øßá*ܧã/ä�Ö¤á��=Òo×$âCÛcã�ÛcÖ¤×$â � ; ; %YègOØßÛcØßÓ ÒQקÓÕâoÝ�Øßá ܧ֤ÛcãCÛwÖQÙgØßÖoá ÞVÓ Òoá=áVØßá=Ô Þ=×$Ö¤à=Óßã/ÛwÜ/Ý�Ù§Ú=ã ä/Ö¤Ü$Ù.Öoæ�ÙgÚ=ã*á=ãCBOÙ.ÛwÖ3;oã�Vã�Þhã�á��=ܪÖoá�ÙgÚ=ã¸ÞVקã�;OØÕÖ¤ç=Ü¢Þh֤ܧؼÙgØÕÖ¤á�è ��ÚVã¸Ô¤ã�áVã�קØÕä¸ä¬ÒQܧã¸ä�ÒoáCÒoÓßÜ$Ö�àhã¸ç=ܧã����«Ú=ã�×$ãÙ§Ú=ã8ä�Ö¤Ü�Ù?ÖoæVÛwÖ3;OØßáVÔ+Ù§Ú=ã¦×$Ö¤àhÖoÙ��=ã�Þhã�á$�=ÜUÖ¤á קã/ܧ֤ç=×$ä�ã/ÜUç=ܧã���ØÕá Ù§Ú=ã¦ÓßÒoÜ$Ù>n³ÓßÖOä¬ÒQÙ§ØßÖ¤á=Ü/è�¦ã�ܧØ��=ã�Ü�ÞV×gÒoä�ÙgØßä�ÒoÓOÛwÖoÙ§Ø�;QÒQÙ§ØßÖ¤á=Ü/Ý3��ã�àhã�ÓÕØßã�;oã�ÙgÚ=ÒQÙUÜ$Ö¤Ûwã�ÖoæeÙgÚ=ã�ä�Ö¤á=ä/ã�ÞVÙ§Ü5Þ=קã/ܧã�áµÙ§ã��ØÕá6ÙgÚ=ØÕÜ�ÞeÒoÞhã�׫ÛwØÕÔ¤ÚµÙ�àhã ÖQæ?ØÕáIÙ§ã�×$ã�Ü$Ù+ØÕá�Ù§Ú=ã³Ô¤ã�áVã�×gÒQÓ;Ü$Ùgç$�Vâ6Öoæ(ܧã�Òoקä�ÚuÙgקã/ã�Ü/è��Ú=ã³æsÖ¤ÓÕÓßÖ3�«Øßá=Ô¸ÒoקãªÜ$Ö¤Ûwã³àeÒQܧØßä:�Vã�*eá=ؼÙgØÕÖ¤á=Ü�è,������������ �!��"�" ØÕÜ Ò.קÖOÖoÙ§ã�� ٧קã/ã$# Øßá��«Ú=ØÕä�Úlã�;oã�×$â á=Ö5�=ã$%VÝUÖoÙ§Ú=ã�׳ÙgÚeÒQá ÙgÚVã

×$Ö`ÖQÙ¬ÝXØÕÜ¢Ó ÒQà�ã/Óßã��'&("*)+�-,�./��&10¸Ö¤×2�+�134./�-,�./��&10oÝXØÕá ܧç=ä�Ú*Òc��Ò¬â-ÙgÚ=ÒQÙ³Òoáµâ-Ù �¦Ö6ܧØÕà=ÓßØÕá=Ô¤ÜÚ=Ò3;oã��=Ø_^Xã/קã�áµÙ�Ó Òoàhã�ÓÕÜ�èI7 Ú=ã�á5%.ÚeÒoÜ�áVÖ�ܧØÕà=ÓßØÕá=ԤܳØÕÙ�ØßÜ ä¬ÒoÓÕÓßã��lÒoá764�8&9�:,�./��&10oèt,; ����.�Öoæ<# ØßÜ�Ò�Ü$ã��Iç=ã/á=ä�ã ÖoæGá=Ö5�=ã�Ü=% �+>�?@?@?�> %�A�ÝVܧçVä�ÚuÙ§ÚeÒQÙB%<l�ØÕܦ٧Ú=ãªÞeÒo×$ã�áµÙ«ÖoæC%<l ��� è=¿álÙ§Ú=ØßÜ�ä¬ÒoÜ$ãoÝD% � ØßܲÒoáE���F,�"�G��H64�³ÖoæI%�A�Ý'�«Ú=ØßÓÕãJ%�A+ØßܸÒ50/"�GK,�"���0L���8�8ÖQæ-% � è�7 Ú=ã/á% �NMrO%�A5ÙgÚ=ã�â�ÒQקã¸ä�ÒoÓßÓÕã�� ; ��6 ; "��N���F,�"�G��H64�+Òoá�� ; ��6 ; "��N0/"�GK,�"���0L���8�nÝX×$ã�Ü$Þ�ã/ä/ÙgØ_;¤ã/ÓÕâ¤è,7P{å¿ÞeÒQÙ§Ú6ØßÜ�Ò¸Þ=ÒQÙgÚ�æsÖ¤×$Ûwã���àµâJP8á=Ö5�=ã�Ü/è ��ÚVãªá=ÖoÙ�ÒLÙgØßÖoáRQ @�#LA8קã�ÞVקã�Ü$ã�áµÙgÜ�Ù§Ú=ãªÜ§ã�ÙÖQæ;á=Ö5�=ã�ܦÖoæS# è�FeÖ¤×D%$TUQ @*# A�ÝIÙgÚVã4à=ØÕáeÒo×$â²Ù§×§ã/ã �=ãC*eá=ã��6ØÕáV# àµâüÒoÓßÓf�Vã�ܧä/ã�á��=ÒoáµÙgÜ

U

Page 4: Optimal Binary Search Trees with Costs Depending on the Access

ÖQæ-% ØÕÜ�ä¬ÒQÓßÓßã�� ÙgÚVã G � ���!��"�"�ÖQæ�# ��6K64� " 06ÒQÙN%VÝ8Òoá�� �=ã/á=ÖoÙgã��Êàµâ'#(@!% A�è ��Ú=ãU&("*)+�G � ���!��"�"¢ÖoæB%uØßܪÙgÚVãwà=ØÕáeÒo×�â-Ùg×$ã�ã1æs֤קÛcã��*ØßáU# àµâ Ù§Ú=ãwÓÕã/æøÙ³ä�Ú=ØÕÓ9�*ÖoæB%.Òoá�� ÒoÓßÓ?ÖoæؼÙgÜ:�=ã/ܧä/ã�á��eÒQáIÙ§Ü�è/g`ØÕÛwØÕÓ Òo×$ÓÕâoÝ �=ãC*eá=ã1ÙgÚ=ã �+�134./�=G � ��� ��"�"¢Öoæ %`èc��Ú=ãcÓßã�æøÙ Òoá�� ×$ØßÔ¤ÚµÙÜ$ç=àV٧קã�ã/Ü�ÖoæS%¸Òo×$ã+×$ã�Þ=×$ã�Ü$ã�áµÙgã��6àIâ #�� @!% A5Òoá��$#��]@ % A�Ý`×$ã�ܧÞhã�ä�ÙgØ_;¤ã�Ó¼â¤èN, à=Øßá=Òo×$â¸Ù§×§ã/ã�Vã�*eá=ã���Øßá # àµâ�Ò¸Ü$ç=à=ܧã�Ù«Öoæ Q @�#LA5ØßÜ!ä�ÒoÓßÓÕã��üÒ ; �����!�!��&�G � ���!��"�"¦Öoæ<# è�, ��6K64� ; ����.ØÕܪÒ6ÞeÒQÙ§Ú*Ü�Ù�Òo×�ÙgØÕá=Ô�ÒQÙªÙgÚVã²×§ÖOÖoÙ³Öoæ # Ý �«Ú=ØßÓÕã²ÒU��6K64���H&(" � ) ; ����.üÜ$Ù�ÒQ×$ÙgÜ ÒQÙ4ÙgÚ=ã1קÖOÖoÙÒQá��.ã/á��=Ü+ÒQÙ+ܧÖoÛwãªÓÕã¬ÒQæ(ÖoæC#�è

�;ã/Ù3k �+>@?@?@?�> k��� �à�ã6Ò.ܧã/Ù¸Öoæ�ã�ÓÕã�Ûcã�áµÙgÜ�ä¬ÒoÓÕÓßã����L"�� G�Ý]kmlJ� kml ��� è , ���������+�GK" ����,�.$�!��"�"5æsÖo×�3k �+>�?@?@?�> k��� ³ØÕܦÒ�à=ØßáeÒQ×$â²Ùg×$ã�ã�# Øßá+�«ÚVØßä�Ú�ã/ØÕÙgÚVã�× Q @*# A�ØßÜ8ã�ÛcÞVÙ¿â¤ÝÖo׳٧Ú=ã1Óßã�æøÙ Òoá��*קØßÔoÚIÙ³Ü$ç=àV٧קã�ã/Ü�Öoæ8ÙgÚVãw×$Ö`ÖoÙ ÒQקã1à=Øßá=Òo×$â-ܧã¬ÒQקä�Ú Ù§×§ã/ã�Ü�Ýp�«Ú=ã�×$ãüÒQÓßÓ�Qã/âOܳØßá�Ù§Ú=ã²Óßã�æø٢ܧçVàVÙg×$ã�ãcÒoקã�ܧÛwÒoÓßÓÕã�׫ÙgÚeÒoá Ù§ÚeÒQÙªÖoæ5Ù§Ú=ã¸×§ÖOÖoÙ�Ý �«Ú=ØßÓÕã�Ù§Ú=ãu�oã�â`Ü ØßáÙ§Ú=ã1קØÕÔ¤ÚµÙ�Ü$ç=àV٧קã�ãwÒo×$ãcÔoקã¬ÒLÙgã�×/è+, &(" 3L��& ; ����.6ØÕܳÒuÜ$ã��Iç=ã/á=ä�ãwÖoæD�Qã/âOÜq�«Ú=ØÕä�Ú ØÕܳÒÞ=ÒQÙgÚuØßá6Ü$Ö¤Ûwã³à=ØÕáeÒo×�â�ܧã�Òoקä�ÚuÙg×$ã�ãoè��Ú=ã�=ã/ܧä/קØßàhã�� ÛcØßá=ØÕÛwØ�8¬ÒQÙ§ØßÖ¤á*Þ=קÖoà=Óßã/ÛwܲÒQקã6ܧÖoÓ�;¤ã��Êàµâ �`â`á=ÒoÛwØÕä6Þ=קÖoÔ¤×gÒoÛ²å

ÛcØßáVÔüã��IçeÒLÙgØßÖoá=Ü�è:��Ú=ã²ä/֤ק×$ã�Ü$Þ�Ö¤á$�=Øßá=ÔI�Vã�ä�ÖoÛwÞh֤ܧؼÙgØÕÖ¤á=Ü+ã�ÛcÞ=ÓßÖ�âuÙgÚ=ã¸ä/Ö¤á=ä/ã�ÞV٧ܪÖoæÓÕã�ÔµÒQÓ;ÞeÒQÙgÚ.Òoá�� @�� >�� A¿å¿ÓÕã�ÔµÒQÓ�ÞeÒQÙ§Ú=Ü�èD��ÚVã�ÓßÒQ٧٧ã�׫Ûwã�Òoá=Ü�ÙgÚV֤ܧã�Óßã�Ô¤ÒoÓ�ÞeÒQÙ§Ú=Ü+Óßã¬ÒW�=Øßá=ÔÙ§Ö²Ò�Ü$ç=àVÙg×$ã�ã4æsÖoקÛcã���àµâwä�Ö¤á=Ü$ã�ä/çVÙgØ_;¤ã:�oã�âOÜ�èN7 ã+ÙgÚ=ã/áI�=ã�Ü$ä�קØÕà�ã4ä�ÚeÒo×gÒQä/Ùgã/קØ�8¬ÒQÙ§ØßÖ¤á=ÜæsÖo×8àhÖoÙ§ÚwÓÕã�ÔµÒoÓ=Òoá���@�� >�� A{å¿Óßã/ÔµÒoÓ=Þ=ÒQÙgÚ=Ü/è'��Ú=ã4ÒoÓßÔ¤ÖoקØÕÙ§Ú=ÛcÜUÒo×$ã�Ö¤à`Ù�ÒoØÕá=ã��càµâ1ä�Ö¤Û¸àVØßá`åØÕá=Ô�ÙgÚ=ã+�=ã�ä/Ö¤ÛwÞhÖ¤Ü$ØÕÙgØÕÖ¤á=Ü Òoá��*ÙgÚ=ãwä�ÚeÒoקÒoä/Ù§ã�קØ�8¬ÒQÙ§ØßÖ¤áVÜ�èI��Ú=ã��Vã�ä�ÖoÛwÞh֤ܧؼÙgØÕÖ¤á=Ü ÒoקãÞVקã�Ü$ã�áµÙgã�� Øßá gOã�ä/Ù§ØßÖ¤á `.Òoá�� ÙgÚ=ã�ä�Ú=Òo×gÒoä�Ùgã/קØ98�ÒQÙgØÕÖ¤á=Ü�Òoקã+�=ã/æsã/ק×$ã��lÙgÖ g`ã�ä�ÙgØÕÖ¤á UVègOã�ä/Ù§ØßÖ¤át!wÞVקã�Ü$ã�áµÙgÜ¢Òoá�Òoá=ÒoÓÕâOܧØÕÜ«ÖoæUÜ$Ö¤Ûwã ÞeÒoקÒoÛcã/Ùgã/קÜ+Öoæ?Ù§Ú=ã�٧קã/ãoÝÎØßá=ä/Óßç��VØßá=Ô²ÙgÚVãÙ§ØßÛcã�Òoá��1Ü$ÞeÒoä�ã«ä/Ö¤ÛwÞVÓßãCB`ؼٿâ�ÖoæhÙgÚVã«ÒoÓßÔ¤ÖoקØÕÙ§Ú=ÛcÜ�è���Ú=ã+ÒoáeÒoÓ¼âOܧØßÜ?ØßÜ�àeÒoÜ$ã��cÖ¤á1Ô¤ã�áVã�×�åÒLÙgØßáVÔ�æsç=á=ä�ÙgØÕÖ¤á=Ü�Òoá$�6ã�áIç=Ûcã�×gÒLÙgã�Ü:@�� >�� A{å¿ÓÕã�ÔµÒoÓÎÞeÒLÙgÚ=Ü/èhF(ØßáeÒoÓÕÓÕâoÝ5g`ã�ä�ÙgØßÖoá#�Þ=קã/ܧã/áIÙ§ÜÙ§Ú=ã³ä�Ö¤áVä�ÓßçVܧØßÖoá=Ü«Òoá��uܧ֤Ûcã Ò����=ؼÙgØÕÖ¤áeÒoÓhקã/ÛüÒo×s�IÜ�è

� ����� ���L Y�! " �!#'���'�����$#

�;ã�Ùonv ; àhã³Ò1ÔoØ�;¤ã/á�ØßáµÙgã/Ô¤ã�×6;QÒoÓÕç=ã³Òoá��$3k ��>@?�?@?�> k��% �Ҳܧã/Ù+Öoæp�Qã/âOÜ�Ýfkml�� kml ��� èFe֤תã�Òoä�Ú kml�Òoá��*Óßã/ÔµÒoÓUÞ=ÒQÙgÚ'& �+>�?@?@?�> & A¿Ý\�«Ú=ã/קã ; � P � nN� ; ÒQá�� kml�r(& A¿ÝGØÕÙØÕÜ�Ô¤Ø_;¤ã/á Ò-קã�ÒoÓ¦áVÖ¤á`å¿áVã�ÔµÒQÙ§Ø�;oã)�L"��',�6KG��+*�@�& �+>@?�?@?�> &4APA ÖQæ,& A ��"�&1��� �.-�"³Ù§Ö�& ��>@?@?@? & A�è={Ù�ä�Ö¤×$קã�Ü$Þ�Öoá��=Ü6ÙgÖlÙ§Ú=ã ä�Ö¤Ü�Ù�Öoæ קã�Òoä�Ú=ØßáVÔ/& A³ÙgÚ=×$Ö¤ç=Ô¤ÚzÙ§Ú=ã ÞeÒQÙ§Ú0& �+>@?�?@?�> & A¿è =¿áÒW���=ØÕÙ§ØßÖ¤áXÝhã�Òoä�Ú��oã�âTkml¢ØÕÜ4Ô¤Ø_;¤ã�á�Òüá=Ö¤á`å{á=ã�Ô¤ÒQÙgØ_;¤ã¸×$ã¬ÒoÓ21 "��134./�43(@[kmlEA�è:FeÖ¤×4ÒüÓßã/ÔµÒoÓÞ=ÒQÙgÚ5& �+>�?@?@?�> &76+Ýf�=ãC*eá=ã ØÕÙgÜ ; ����.�,�6KG��'ÒoÜ

!

Page 5: Optimal Binary Search Trees with Costs Depending on the Access

� @�& �+>@?�?@?�> & 66A�r ���� l � 6

*W@�&������ ��� l� ��� >@?@?�?�> &Wl)A @ ; A

�;ã/Ù2# àhã6Ò�à=ØÕáeÒo×$â*Ü$ã¬Òo×$ä�Ú Ù§×§ã�ãwæsÖ¤×3k �+>@?�?@?�> k��� Iè��¢ã�á=ÖQÙgã�àµâ k��l Ù§Ú=ã6קÖOÖoÙÞ=ÒQÙgÚ-Ù§Öc�Qã/âTkml/è ��Ú=ãq;oÒQÓßç=ã/Ü�ÛwÒeB ��� l � �� � @ k �l A 1Òoá$��� ��� l � � 3u@ kml)A�� � @[k �l A+Òoקãä�ÒoÓßÓÕã�� 1 64��G��-, �4GK" � ��"�" ,�6KG��?Òoá���1 "��134./�H" 0 � -�"�� �K3/" , �4GK"2�!��"�" ,�6KG���Ý�×$ã�Ü$Þ�ã/ä/ÙgØ_;¤ã/ÓÕâ¤è7 ÚVã�á Q @�# A�r��=ÝOÙ§Ú=ã¢ä/Ö¤Ü$Ù§Ü�Öoæ<# Òo×$ã �=ãC*eá=ã���ÒoÜD8�ã/קÖ=è>��Ú=ã �Iç=ã�Ü�ÙgØÕÖ¤á6ä�Ö¤áVܧØßÜ�ÙgܦÖoæ*=á��=ØßáVÔ1Ù§Ú=ãªÙg×$ã�ã # �«Ú=ØÕä�Ú.ÛcØßáVØßÛcØ98�ã/Ü�Ö¤áVã ÖQæ(Ù§Ú=ã�Ü$ã³Ù �¦Ö�ÒQà�Ö3;¤ã³ä/Ö¤Ü$Ù§Ü�ÝÎÒoÜG�=ã/ܧØß×$ã���è, ÛcØßá=ØÕÛwØ�8�ØÕá=Ô Ù§×§ã/ã ØÕÜ�ä¬ÒoÓÕÓßã��6 ; � ���V��& è�¢à=Ü$ã�×s;oã�Ù§ÚeÒQÙ+ܧç=à`Ùgקã/ã�Ü+Öoæ�ÒQáuÖoÞVÙgØÕÛüÒoÓhÙg×$ã�ã Òoקã³á=ÖQÙ�áVã�ä�ã/ܧܧÒoקØÕÓÕâ6Ö¤Þ`ÙgØßÛwÒoÓ�ÝOæsÖ¤×

ÒQáIâ n�� 2 è ��Ö¤á=ܧØ��=ã�× ÙgÚ=ãwãCBVÒoÛcÞ=Óßã1ÚeÒ<;OØßáVÔ�n r ; Ý]O r U`Ý]�«ØÕÙ§Ú �Qã/â ä�Ö¤Ü�ÙgܲÒoÜÔoØ�;¤ã/á.àµâF(ØßÔ¤ç=×$ã ; @�Ò�A!Òoá���ÚeÒ<;OØßá=ÔwÒoÓßÓZ��ã/ØßÔ¤ÚµÙ§Ü+ã��IçeÒoÓ;ÙgÖ ; è

ÓÕã�ÔµÒoÓXÞeÒQÙgÚVÜ k � k d k Q k � k d k � k Q k d k � k d k Q k Q k � k Q k d�Qã/â�ä�ÖoÜ$ÙgÜ 2 2 2 2 ` U ` U ; @�Ò�A! k �" " " "�# k d @sàmA

" " " " # k QF?ØÕÔ¤ç=×$ã ; ÑN4>B=ÒQÛwÞ=ÓÕãªÖoæ?Òoá�Ö¤ÞVÙgØÕÛüÒQÓ�Ùg×$ã�ã:�«ØÕÙ§Ú�á=Ö¤á`å{Ö¤ÞVÙgØÕÛüÒQÓXܧçVàVÙg×$ã�ã�Ü/è��Ú=ã�٧קã�ã�ÖQæ F(ØßÔ¤ç=×$ã ; @sàmA(ØßÜ?à�ÖoÙ§Ú(��ÖoקÜ$Ù¦Òoá$�1Ò3;oã�קÒoÔ¤ã«ä¬ÒoÜ$ã�Ö¤ÞVÙ§ØßÛwÒoÓYÝLà=çVÙ # @[k d AØÕÜ�á=ÖoÙ8Ö¤ÞVÙ§ØßÛwÒoÓVØÕácÒoáµâ²ä¬ÒoÜ$ãoè$��Ö¤áVܧã��Iç=ã/áµÙgÓÕâoÝ`Ù§Ú=ãG�=ã�ä/Ö¤ÛwÞhÖ¤Ü$ØÕÙgØÕÖ¤á²ã�ÛcÞ=ÓÕÖ\âoã��cØßá²ÙgÚVã

�`â`á=ÒoÛwØÕä!Þ=×$Ö¤Ô¤×gÒQÛwÛcØßá=Ô�ܧ֤ÓÕçVÙgØÕÖ¤á²ÖoæÎÙgÚVã+ÖoÞVÙgØÕÛüÒoÓOà=ØÕáeÒo×$â�ܧã�Òoקä�Ú1Ùg×$ã�ã�Þ=×$Ö¤à=Óßã/ÛÌæsÖ¤×n/r 2 �=Ö`ã/Ü¢á=ÖoÙ¢ÒoÞ=Þ=Ó¼â�ÙgÖüÙ§Ú=ã¸Þ=×$ã�ܧã/áµÙ³ä¬ÒoÜ$ãoè1X�Ö3�¦ã�;oã�×�Ý'Ü$Þ�ã/ä�Ø ÒQÓ]�IØßá$�=Ü¢Öoæ5ÞeÒQ×$ÙgØßÒoÓÜ$ç=àV٧קã�ã/Ü-ÒQקãCÖ¤ÞVÙ§ØßÛwÒoÓYÝ�ÛwÒ��IØßá=Ô Ø¼Ù6Þh֤ܧÜ$Øßà=ÓÕã�ÙgÖ Ü§Ö¤Ó_;¤ã Ö¤çV×uÛcØßáVØßÛcØ98¬ÒLÙgØßÖoá ÞVק֤à`åÓÕã�ÛcÜ�àµâ ä�Ö¤á ;oã�á=ØÕã�áµÙgÓ¼â �=ã/ä�Ö¤ÛcÞ�ÖoܧØßáVÔ.ÙgÚVã�Û ØßáµÙgÖ.ܧÛwÒoÓßÓÕã�׳ܧç=àVÞ=ק֤àVÓßã�ÛcÜ�Ý?Óßã¬ÒW�=Øßá=ÔÙ§Ö²Ùgã�ä�ÚVá=Ø(�Iç=ã/Ü4ܧØÕÛwØÕÓ ÒoצÒoÜq� ; ÝfUW%�è�,!Ù«ÙgÚ=ØÕÜ+ÞhÖ¤ØÕáIÙ6��ã á=ã�ã���Ò��$�=ØÕÙ§ØßÖ¤áeÒQÓ�á=ÖQÙ�ÒQÙ§ØßÖ¤á�èF?ØÕקÜ�Ù¬Ý;ØßáµÙ§×§Ö5�=ç=ä�ã+n Ò����VØÕÙgØÕÖ¤áeÒoÓ]�oã�â`Ü 3k�� ����>@?@?@?�> k�� � � IÝ;ä¬ÒoÓÕÓßã�� 0 � �%�N� �L"�� G�ÝÒQÓßܧÖüÜgÒQÙ§ØßÜ$æøâOØÕá=Ô�kml � kml ��� Ý\O �'& � OR�wn�èq45Òoä�ÚCÖoæ5ÙgÚ=ã/ܧãK�oã�â`ܳÚeÒQÜL��ã/ØßÔ¤ÚµÙ 2 è

#

Page 6: Optimal Binary Search Trees with Costs Depending on the Access

��ÚVãD�oã�â¸ä�ÖoÜ$ÙgÜ�×$ã�ÓßÒQÙgØ_;¤ã¦Ù§Ö¢ÞeÒQÙ§Ú=ÜUä/Ö¤áµÙ�ÒoØÕá=Øßá=Ôo�=ç=ÛcÛ�â��oã�â`Ü8Òo×$ã6�=ãC*eá=ã��wÒQÜ?æsÖ¤ÓßÓÕÖ3�«Ü�è�;ã�Ù,& �+>@?�?@?�> &4AGà�ã³Ò²Óßã/ÔµÒoÓ�ÞeÒQÙgÚ�ÚeÒ<;OØßáVÔwÒLÙ�Óßã�ÒoÜ$Ù«Ö¤áVã:�=ç=ÛcÛ�â��Qã/â¤Ý ; � P � n � ; è��ÚVã�á

*W@�& �+>@?@?�?�> &4APA�r

���������� ���������

2 > �«Ú=ã�á5& ��>@?@?@?�> & A?Òoקã³ÒQÓßÓ �=çVÛwÛ�âc�oã�â`Ü @ `�A

*W@�&�l >@?@?@? & A A > �«Ú=ã�á�� & � ; Ü$ç=ä�Ú.Ù§ÚeÒQÙ,& �+>@?@?@?�> &�l� � ÒQקã�=ç=ÛcÛ�â��Qã/âOÜ�Ýhà=çVÙ,&Wl >@?�?@? &4AUÒo×$ãªá=ÖoÙ @ U A

� > ÖoÙgÚVã�×s�«ØÕܧã @P!.A

�¢ã/á=ÖoÙgã�� r(3k �+>@?@?@?�> k�� � � IÝ� r�3k ��>@?@?@?�> k IÝ�� � r�3k ����>@?@?�?�> k�� � � IÝ� � r 3k ���+>@?�?@?�> k � �Òoá���� � r � �� l � � 3(@[kml)A�è�;ã/Ù � >�� àhã²Ò6ÞeÒoØÕ×4Öoæ8ØÕáIÙ§ã�Ô¤ã/קÜ/Ý 2 � � � � � O?èq, ÞeÒQÙ§Ú'& �+>@?@?�?�> & � ØßÜu@�� >�� A �&(" 3L��&.�«Ú=ã/á.ÙgÚVã�קã³ãSBVØÕÜ$Ù§Ü�Ò1à=ØÕáeÒo×$âüܧã�Òoקä�ÚuÙgקã/ã # ÚeÒ<;OØßá=Ôcá=Ö5�=ãªÜ§ã�Ù�� ä/Ö¤áµÙ�ÒoØÕá=Øßá=Ô

Ù§Ú=ã ÞeÒQÙgÚ5& ��>@?@?@? & � Òoá��.ܧç=ä�Ú-Ù§ÚeÒQÙ+ã�ؼÙgÚ=ã/×,��r � Òoá$� & � ØÕÜ�Ò1Óßã�ÒQæ(Öoæ'�ªÝÎÖ¤×�& � ÚeÒQÜÒuä�Ú=ØßÓ�� k��2T�� � ÜgÒLÙgØßÜ�æøâOØßá=Ô Q @�#(@ k��sAsA�r�� � èI=¿á ÖoÙgÚ=ã/×��¦Ö¤×s�=Ü�Ý�ÒQá @�� >�� A¿å{Óßã/ÔµÒoÓÞ=ÒQÙgÚ�ØßÜ�Öoá=ãªÓßã�Ò��=ØßáVÔ�ÙgÖcҲܧç=à`Ùgקã/ã³ä�Ö¤áµÙ�ÒQØßá=ØÕá=Ô²ãCBVÒoä�ÙgÓÕâwÙgÚ=ã1�Qã/âOÜ�ÖQæ�� � Ý=ØÕá�Ҳ٧קã/ãæsÖoקÛcã���àµâ�ÒoÓßÓ �oã/âOÜ+Öoæ�� è�;ã/Ù & �+>@?@?�?�> & � àhã«Òoá/@�� >�� A¿å¿ÓÕã�ÔµÒQÓ`ÞeÒLÙgÚ�è��¢ã/á=ÖoÙ§ã!àµâ2# � @�& �+>�?@?@?�> & � A?Òoá1Ö¤ÞVÙ§ØßÛwÒoÓÜ$ç=àV٧קã�ã�æsÖ¤×$Ûwã��²àµâ�ÙgÚVã�á=Ö?�Vã�Ü�Öoæ�� � Ý��«Ú=ã�×$ã,& �+>@?�?@?�> & � ØÕÜ?ÙgÚ=ã�Þ=ÒQÙgÚ²ÓÕã¬Ò��=ØÕá=Ô4Ù§ÖªØÕÙgÜ×$Ö`ÖQÙ¬è��«ã�Þ=×$ã�Ü$ã�áµÙ«àµâ � � @�& �+>@?�?@?�> & � A�ÙgÚ=ãu@nÖ¤ÞVÙ§ØßÛwÒoÓ A?ä/Ö¤Ü$Ù!ÖoæS# � @�& �+>�?@?@?�> & � A�è'��ÚeÒLÙØÕÜ�Ý � �� @�& �+>�?@?@?�> & � A(ä¬Òoá1àhã!ØßáµÙ§ã�קÞVקã/Ù§ã��cÒoÜUÙ§Ú=ã�Ö¤ÞVÙ§ØßÛwÒoÓIä�Ö¤Ü�Ù�Ùg֪ܧã�Òoקä�Ú1ÙgÚVã!ܧç=à`Ùgקã/ã� � ÝhÔ¤Ø�;oã�áuÙgÚeÒQÙ & ��>@?@?@?�> & � ØßÜ�Ù§Ú=ã�ÞeÒLÙgÚ-ÓÕã¬Ò��VØßá=Ô1ÙgÖcØÕÙ�è�0�ÖoÙ§ã�Ù§ÚeÒQÙ=# �� @�& �+>@?�?@?�> & � A�VÖ`ã/ܪá=ÖoÙ³ä�ÖoáIÙgÒoØßá Ù§Ú=ã1á=Ö?�Vã�ܪÖoæ+& �+>�?@?@?�> & � Ý;Ú=Ö3��ãC;¤ã�׳ÙgÚVãcä/Ö¤Ü$Ù³ÖQæ�ؼÙ:�=ã�Þhã�á$�=Ü�ÖoáÙ§Ú=ØßܳÞeÒLÙgÚ�è�=¿á Ù§ã�קÛcܳÖoæ�Ù§Ú=Øßܳá=ÖQÙ�ÒQÙ§ØßÖ¤á�Ý'Ò�ܧÖoÓßçVÙ§ØßÖ¤á ÙgÖ�ÙgÚVãwÜ�Ù�ÒQÙ§ã�� ÛcØßáVØßÛcØ98¬ÒLÙgØßÖoá

ÞVק֤à=ÓÕã�ÛcÜwØÕÜcÙ§Ú=ã-Ü$ç=àV٧קã�ã-Öoæ #���f@ k�� � ��> k�� � � �+>�?@?@?�> k�� ��� A�Ý�ÚeÒ<;`ØÕá=ÔlÒQÜüקÖOÖoÙ1ÙgÚVãä�ÚVØßÓ9� Öoæok�� ��� è �¢à=Ü$ã�×s;oã-ÙgÚ=ÒQÙwÙ§Ú=ãuÞeÒQÙgÚÊÓßã�Ò��=ØßáVÔCÙ§Ö Ù§Ú=ã.ÓßÒQ٧٧ã�ײÙg×$ã�ãuØßܲæsÖ¤×$Ûwã��Ü$Ö¤Óßã/ÓÕâüàIâ��=ç=ÛcÛ�â��Qã/âOÜ�èFeÖ¤×G�=ã�Ùgã�×$ÛwØÕá=ØßáVÔ1Ù§Ú=ã:;QÒoÓßç=ã³Öoæ(ÙgÚ=ã Ö¤ÞVÙ§ØßÛwÒoÓXä/Ö¤Ü$Ù � � @�& �+>@?@?@?�> & � A�Ým�¦ã��=ã�ä/Ö¤Û1åÞhÖ¤Ü$ã4ÙgÚ=ãªä/֤ק×$ã�Ü$Þ�Ö¤á$�=Øßá=Ô²ÞVק֤à=ÓÕã�Û ØßáµÙ§Ö¸ÙgÚ=ã¢Ü$ç=à=Þ=×$Ö¤à=ÓÕã�ÛcÜ!Öoæ�*eá��=ØÕá=Ô�Ù§Ú=ãªÖ¤ÞVÙ§ØßÛwÒoÓ

ä/Ö¤Ü$Ù§Ü � � �� � @�& d >@?�?@?�> & � > k��sA�Òoá�� � � � @�& d >@?@?@?�> & � > k�� A�Ý=æsÖ¤×�ã�Òoä�Útk�� T�� � èN��Ú=ã��oã/âk���ØÕÜ!ÙgÚ=ã³ä�Ú=ØÕÓ9��Öoæ4& � Øßá�Ù§Ú=ãªÙg×$ã�ã�Ü/èDgOã�ã�F?ØßÔoç=קã�``è��Ú=ãcæsÖ¤ÓßÓÕÖ3�«Øßá=ÔI�VâOáeÒQÛwØÕäcÞVק֤ԤקÒoÛcÛwØÕá=Ô6ã��IçeÒQÙ§ØßÖ¤áVÜ�ÒoÞVÞ=ÓÕâ Ù§Ú=ã+�Vã�ܧä/קØÕà�ã�� �=ã�å

Page 7: Optimal Binary Search Trees with Costs Depending on the Access

ä/Ö¤ÛcÞ�Ö¤Ü$ØÕÙ§ØßÖ¤á=Ü!Òoá���ä�Ö¤ÛcÞ=çVÙ§ãªÙgÚ=ã³Ö¤ÞVÙ§ØßÛwÒoÓXä/Ö¤Ü$Ù§Ü�;oÒQÓßç=ã/Ü�è

ÉÌËÎÍLÐ��������eÐ�Ç�� �� ���������nË����

� �� @�& �+>�?@?@?�> & � A r����� ����2 > �«Ú=ã/á �]r � è �4ÙgÚ=ã/×s�«ØÕܧãoÝ @ #�A

ÛwØÕá � � � � \ÛwÒeB � � �� � @�& d >@?@?@?�> & �4> k�� A >� � � @�& d >�?@?@?�> & �4> k��sA B� *�@�& �+>@?�?@?�> & �4> k��sA > @ � AæsÖo׫ÒoÓßÓ 2 � � � � � O*Òoá�� @�� >�� A¿å{Óßã/ÔµÒoÓXÞ=ÒQÙgÚ=Ü,& �+>@?@?@?�> & � ÝZnIv ; è

ÉÌÇ�������¬Ç`Ï�����ÇIÍ����ÎÇ������=Ð�Ç �! ����!����"��nË����

� �� @�& �+>�?@?@?�> & � A r����� ����2 > �«Ú=ã/á �]r � è �4ÙgÚ=ã/×s�«ØÕܧãoÝ @$#�A

ÛwØÕá � � � � � � �� � @�& d >@?�?@?�> & � > k��sA<� � � � @�& d >�?@?@?�> & �4> k��sA �� � � � *�@�& �+>@?�?@?�> & � > k��sA > @ i A

æsÖo׫ÒoÓßÓ 2 � � � � � O*Òoá�� @�� >�� A¿å{Óßã/ÔµÒoÓXÞ=ÒQÙgÚ=Ü,& �+>@?@?@?�> & � ÝZnIv ; è=¿á Ö¤×s�=ã�×cÙgÖ ;¤ã�×$ØÕæøâ ÙgÚ=ã.ä�Ö¤×$קã/ä/ÙgáVã�ܧÜ6ÖQæªÙgÚ=ã ÒQà�Ö3;¤ã.ã��IçeÒQÙ§ØßÖ¤áVÜ�Ý«á=ÖoÙ§ã.ÙgÚ=ÒQÙ�ؼæ

& �+>@?@?�?�> & � ØÕÜ�Òoáb@�� >�� A¿å¿ÓÕã�ÔµÒQÓ�ÞeÒQÙgÚzÒoá�� � �&% � � ÙgÚ=ã/á & d >@?@?@?�> & �4> k��1ØÕÜwàhÖoÙ§Ú@�� > %(' ; A¿å¿ÓÕã�ÔµÒQÓ�Òoá$� @)% >�� A¿å¿ÓÕã�ÔµÒQÓYèU�+ܧØßáVÔCÙ§Ú=ØßÜ�ænÒoä/Ù�Ý5Ù§Ú=ãI�VâOáeÒoÛcØßäüÞ=ק֤Ôo×gÒoÛcÛwØÕá=Ôã��IçeÒQÙgØÕÖ¤á=Ü«ä¬ÒQá.àhãªÖ¤àVÙgÒoØßá=ã���àIâ�Ü�Ù�Òoá$�eÒo× �uØßá$�=ç=ä/Ù§ØßÖ¤áXè��Ú=ã³ÒQÓßÔ¤Ö¤×$ØÕÙ§Ú=ÛwÜ5æsÖ¤×6*=á��=ØßáVÔ²Ö¤ÞVÙgØÕÛüÒQÓm�¦Ö¤×$Ü$Ù«ä¬ÒQܧã³Òoá����¦ã�ØÕÔ¤ÚµÙgã��-Ò<;¤ã/×gÒoÔoãªä¬ÒoÜ$ã

àVØßáeÒo×�â�Ü$ã¬Òo×$ä�Ú.Ùg×$ã�ã/Ü�ä�Òoá�á=Ö3�±à�ã:�Vã�ܧä/קØÕà�ã���è��Ú=ã1ØÕá=Þ=çVÙ³ä/Ö¤á=ܧØÕÜ$٧ܪÖoæ!ÒQá*ØÕáµÙgã�Ôoã�×�n � 2 Ý'Ò6ܧã�Ù 3k ��>@?@?@?�> k��� üÖoæ �Qã/âOÜ�Ý�kml �kml ��� ݪÒoá�� Ò �Qã/â ä�ÖoÜ$Ù *�@�& �+>@?�?@?�> &4APAüæsÖ¤×�ã¬Òoä�Ú Óßã/ÔµÒoÓ P{å¿Þ=ÒQÙgÚ�Ý ; � P � n � ; è

,�ÓÕÙ§ã�קá=ÒQÙgØ_;¤ã�Ó¼â¤ÝeÙgÚVã�ØßáVÞ=çVÙ�ä¬Òoá�ä/Ö¤á=Ü$ØßÜ$Ù4Öoæ5Ò1æsç=á=ä/Ù§ØßÖ¤á/�«Ú=Øßä�Ú-ã�áeÒoàVÓßã�Ü+ÙgÖ�ä/Ö¤ÛcÞ=çVÙgãÙ§Ú=ã��oã�â³ä�Ö¤Ü�ÙgÜ *W@�& ��>@?@?@?�> & A[A�Ý3�«Ú=ã�áVã�;¤ã/×?á=ã/ã��=ã���è>=¿á³ÙgÚVã�Ó ÒQÙ$Ùgã�×Xä¬ÒoÜ$ãN�¦ã8ÒoܧÜ$ç=ÛcãUÙgÚeÒQÙ

#

Page 8: Optimal Binary Search Trees with Costs Depending on the Access

1y

2y

ky

x

T (x )l

l

2y ky x lT ( ) ,i,l-1

L T (x )l R

2y ky x lT ( ) ,l, j ,... , ,...

F?ØßÔ¤çVקã1``Ñ���ÚVãq�=ã/ä�Ö¤ÛcÞh֤ܧؼÙgØßÖoá6Öoæ # � @�& �+>@?@?�?�> & � AÙ§Ú=Øßܦä�Ö¤ÛcÞ=çVÙgÒQÙgØÕÖ¤áüä�Òoá6àhãL�=Ö¤á=ã4Øßáüä/Ö¤á=Ü�Ù�ÒoáµÙ�ÙgØÕÛwãQè>=¿á�Ò��$�=ØÕÙ§ØßÖ¤á�ÝIØÕáüÙgÚ=ão��ã/ØßÔ¤ÚµÙgã��Ò<;oã�×gÒQÔ¤ã³ä¬ÒoÜ$ã�Þ=×$Ö¤à=ÓÕã�Û ã�Òoä�Ú/�oã/âIkml«ØÕÜ«ÒoÓßÜ$ÖcÔoØ�;¤ã/á-Ò²á=Öoá`å¿á=ã/ÔµÒQÙ§Ø�;¤ãL�¦ã�ØÕÔ¤ÚµÙ�3u@[kmlEA�è��Ú=ã¦ÒoÓÕԤ֤קؼÙgÚ=ÛcÜXÜ�Ù�Òo×�Ù'àµâ1�=ã�*eáVØßá=Ô�ÙgÚVãh�=çVÛwÛ�â �oã�â`Ü 3k�� ����>�?@?@?�> k�� � � Iè �+ܧØßáVÔ@ `�A 'b@[!.A�Ý�ä�Ö¤ÛcÞ=çVÙ§ã�ÙgÚ=ã �oã/â-ä�Ö¤Ü�ÙgÜ *W@�& �+>@?@?@?�> &4APA�ÝXæsÖo×4ã¬ÒQä�Ú*ÓÕã�ÔµÒQÓ P{å{ÞeÒQÙ§Ú$& �+>@?�?@? &4A�«Ø¼ÙgÚ ÒQÙ¸Óßã¬ÒQÜ$Ù²Ö¤áVã��=ç=ÛcÛ�â �oã/âoÝ ; � P � n$� ; è �¢ãC*eá=ã 3(@[kml A�r 2 æs֤׸ã�Òoä�Ú

O$� ; � & � O$� n�è�FeÖ¤×�ã�Òoä�Ú @�� >�� A¿å{Óßã�Ô¤ÒoÓFP{å¿Þ=ÒQÙgÚ5& �+>�?@?@?�> & A�ÒQá�� 2 � � � � � O?Ýä/Ö¤ÛcÞ=çVÙgã � � @�& �+>�?@?@?�> & A[A�àµâ�@ #�A ' @ � A�Òoá�� @ #�A�' @ i A�ÝV×$ã�ܧÞhã�ä�ÙgØ_;¤ã�Ó¼â�æsÖ¤×�Ù§Ú=ãL�¦Ö¤×§Ü�Ùä�Òoܧã1ÒQá��T�¦ã�ØßÔoÚIÙ§ã��*Ò<;¤ã/×gÒoÔ¤ã²ä�Òoܧã�Þ=ק֤àVÓßã�ÛcÜ�è:,�ÓßÓGקã��OçVØßקã�� Óßã/ÔµÒoÓ(Òoá�� @�� >�� A¿å{Óßã/ÔµÒoÓÞ=ÒQÙgÚ=Ü�Òoקã+Ô¤ã/á=ã�קÒQÙgã���ç=ܧØÕá=Ô���Ú=ã�Ö¤×$ã�ÛcÜ ; Òoá��I`OÝ`×$ã�ܧÞhã�ä�ÙgØ_;¤ã�Ó¼â¤è���Ú=ãY*eáeÒoÓÎÜ$Ö¤ÓßçVÙ§ØßÖ¤áØÕÜ � ���f@ k�� � �4>@?@?@?�> k�� ��� A�è�=¿á6ÙgÚ=ã³á=ãSB`Ù+Ü$ã�ä/Ù§ØßÖ¤áI�¦ã�ä�Ú=Òo×gÒoä�Ùgã/קØ98/ã+@�� >�� A{å¿ÓÕã�ÔµÒoÓhÞeÒQÙ§Ú=Ü�ÝçVܧØßáVÔcÞ=Òo×$Ù§Øßä�çVÓ Òo×!Öo× �=ã/קØßáVÔcÜ$ä�Ú=ã�Ûcã�Ü/è={Ù¦ØßÜ8ܧØÕÛwÞ=ÓÕã!ÙgÖ�ÛwÖ5�=ØÕæøâ�ÙgÚ=ã�ÒoÓÕԤ֤קؼÙgÚ=ÛcÜ?Ù§Ö¸Ò<;¤Ö¤Ø��üä/Ö¤ÛwÞVçVÙ�ÒQÙ§ØßÖ¤áVÜN�«Ø¼ÙgÚ��=ç=ÛcÛ�â

�Qã/âOÜ�è ,4á6Ø��=ã¬Ò�ØßÜ�Ù§Ö²ØßÛcÞ�Ö¤Ü$ã+Ù§ÚeÒQÙD�«ÚVã�á=ãC;¤ã�×Gk�Òoá���kml�ÒQקãL�=çVÛwÛ�â+�oã�âOÜ�ÒQá���k

�ØÕÜ«Ò²Þ=ק֤Þhã�×+ÒoáVä�ã�Ü�Ùg֤׫Öoæpkml�ÙgÚ=ã/á�� � & è

i

Page 9: Optimal Binary Search Trees with Costs Depending on the Access

�¢á=ã�ä�Ö¤ç=Ó��/�¦Ö¤á��Vã�×o�«ÚVã/ÙgÚVã�×¢ØÕÜ+ؼÙ4ÞhÖ¤Ü$ܧØßàVÓßãªÙgÖwØßÛcÞ=קÖ3;¤ãªÙ§Ú=ØßÜ�ÒoÓßÔo֤קؼÙgÚ=Ûuèh��ÚVã� 64�F64�H64�8� ,����!� ; �+���F,�� ; &("?àIâu�³áIçVÙ§Ú��"UW%ÎÛwÒ��=ã�ØÕÙ5ÞhÖ¤Ü$ܧØßàVÓßã!ÙgÖ1�=ã/ä�×$ã¬ÒoÜ$ã�ÙgÚVã+áIç=Û�à�ã/×ÖQæ'ØÕÙgã/×gÒQÙ§ØßÖ¤áVÜ8æs×$Ö¤Û Mc@PO Q A8Ù§ÖuM�@[O dSA�Ý`æs֤צä�Ö¤á=Ü�Ùg×$ç=ä/Ù§Øßá=Ô1ÒoáüÖ¤ÞVÙgØÕÛüÒQÓhàVØßáeÒo×�âcܧã¬ÒQקä�Ú٧קã/ãoè �+áVæsÖ¤×$Ù§ç=áeÒQÙ§ã�Ó¼â¤Ý!ÙgÚVã�Þ=קØÕá=ä�ØÕÞ=Óßã�=ÖOã�Üüá=ÖoÙ�ÚVÖ¤Ó9�AæsÖo×�n � 2 Ý«ÒoÜüÜ$Ú=Ö3�«á àµâÙ§Ú=ã�æsÖ¤ÓÕÓßÖ3�«ØßáVÔwãSB=ÒQÛwÞ=ÓÕãoè �;ã�Ù 3k ��>@?@?@?�> k ��� d wàhã�Ù§Ú=ã¸Ô¤Ø_;¤ã�á Ü$ã/ÙªÖQæN�oã/âOÜ/Ý(ÒQÓßÓ\�«ØÕÙ§ÚçVá=ØÕæsÖ¤×$Û �¦ã�ØÕÔ¤ÚµÙgÜ�èN��Ú=ã ä�ÖoÜ$ÙgÜ+Òo×$ã1�=ã�*eáVã���ÒQÜ!æsÖ¤ÓßÓÕÖ&�«Ü/Ñ

*W@[k ������>@?@?@?�> k � A�r *W@[k �����+>�?@?@?�> k d A�r ?@?@? r *�@ k ����� A�r 2 Ý*W@[k ��>@?�?@?�> k � > k ��� d A�r *�@ k ��>@?@?@?�> k � ANr ?@?@? r *W@[k � A�r 2 Ý*W@[k d >@?�?@?�> k � > k ��� d > k ����� A�r 2 Ý�«ÚVØßÓßãwÒoáµâ*ÖoÙgÚVã�×��oã/â ä�ÖoÜ$Ù¸ØÕÜ�ã��IçeÒoÓ¦Ù§Ö ; è��Ú=ãwܧ֤ÓÕçVÙgØÕÖ¤á*Öoæ�àhÖoÙgÚlÛcØßáVØßÛcØ98¬ÒLÙgØßÖoá

ÞVק֤à=ÓÕã�ÛcÜ�æsÖ¤× ÙgÚ=ãc�oã/âOÜ 3k ��>@?�?@?�> k ����� �ØßÜ ÙgÚ=ãü٧קã/ãüæs֤קÛcã�� àIâ*ÙgÚVã�ܧØÕá=Ô¤ÓßãwÞeÒQÙ§Úk �����+>@?@?@?�> k � è'7 Ú=ã/á-Ò��$�=Øßá=Ô²Ù§Ú=ã1�oã/âIk ��� d ÝVÙgÚVã ÖoÞVÙgØÕÛüÒoÓhÙg×$ã�ãªæsÖ¤× 3k �+>@?�?@?�> k ��� d ØÕÜ?ÙgÚVã!ÞeÒQÙ§ÚKk ��>@?@?@?�> k�6 > k�6 � d > k�6 ��� ݤÛcã¬ÒoáVØßá=Ô4Ù§ÚeÒQÙUÙ§Ú=ã�Þ=×$Øßá=ä/ØßÞ=ÓÕãh�=ÖOã�Ü�áVÖoÙ5ÒoÞ=ÞVÓÕâæsÖo× n�� 2 è�=¿á*ænÒoä/Ù�Ý?ØÕÙ��=ÖOã�Ü á=ÖoÙ�Ú=Ö¤Ó��lÒoÓÕܧÖ�æsÖ¤×qn r 2 ç=á��=ã/×�á=Öoá ç=á=ؼæsÖ¤×§Û �oã/âä/Ö¤Ü$Ù§Ü�èF?ØÕáeÒoÓÕÓÕâ¤ÝVØÕÙ��¦Ö¤ç=Ó9�.à�ã1�¦Ö¤×$Ù§Ú-Ûcã�áµÙgØÕÖ¤á=ØßáVÔ1Ù§ÚeÒQÙ+ÙgÚ=ã Þ=×$Ö¤Þ�Öoܧã��.ÛwÖ5�=ã/ÓGä�Òoá�ÒQÓßܧÖ

Ú=Òoá��=ÓÕãuçVá=ܧç=ä/ä�ã/ܧÜ$æsçVӢܧã�Òoקä�Ú=ã/Ü�è �!ÒQܧØßä�ÒoÓßÓ¼â¤Ý5ÙgÖCÙgÚ=ãuãCB`ØÕÜ$ÙgØÕá=Ô OU� n �Qã/âOÜüÖQæ4ÙgÚVã٧קã/ãoÝ���ãuÒ��$� O �bn$� ; á=ãC� á=Ö5�=ã�Ü/è ��Ú=ã/ܧãuÒo×$ã6ä¬ÒoÓÕÓßã�� 3L� ; G¸ÒQá�� ä�Ö¤×$קã�Ü$Þ�Öoá��Ù§ÖcÙ§Ú=ã�ãSBOÙgã�×$áeÒoÓGá=Ö5�=ã�Ü/Ý�Ø�è�ãQèÕÝÎç=á=Ü$ç=ä�ä/ã�Ü$Ü$æsç=ÓUÜ$ã¬Òo×$ä�Ú=ã�Ü/èG�(Öwã¬Òoä�Ú�Ô¤ÒoÞ-ؼ٫ØßÜ+Ô¤Ø�;oã�á�ÒQáÒQקà=ؼÙg×gÒQ×$âL�¦ã�ØÕԤڵ٬ݤÒQÜ(æsÖ¤×��oã�âOÜ�è���Ú=ãh�oã/â�ä�ÖoÜ$ÙgÜ(ÖoæeÒY�oã�â�Ö¤×GÔµÒoÞ & A=Òoקã8קã��=ã�*eáVã���ݵÜ$ÖÒQÜ�ÙgָܧÒQÙgØÕÜ$æøâ1ÙgÚVã4æsÖ¤ÓßÓÕÖ3�«Øßá=Ô ä�Ö¤á$�=ØÕÙ§ØßÖ¤á=Ü/è'={æ & ��>@?@?@?�> & AGÒo×$ã¢ÒoÓÕÓR�Qã/âOÜ!ÙgÚVã�á�ÙgÚVã ;QÒoÓßç=ã*W@�& �+>@?@?�?�> &4APAcØÕÜüãCBVÒoä�ÙgÓ¼âAÒQÜ�ãCB`Þ=ÓßÒoØßá=ã��zØßá ÙgÚ=ØÕÜüÜ$ã�ä/Ù§ØßÖ¤áXèb��ÚeÒQÙ6ØÕÜ�Ý�ã/ØÕÙgÚVã�×wÙgÒ��oã/áæs×$Ö¤Û Ù§Ú=ã�Øßá=ÞVçVÙ1֤ײä�ÖoÛwÞ=ç`Ùgã�� àµâ @ ` ' !.A�è �4Ù§Ú=ã�× �«Øßܧã @sØ A *W@�& �+>@?@?@?�> & A[A+r � Ý�«ÚVã�á=ãC;¤ã�×1ÒQáIâ ÒoÛcÖ¤á=Ô)& �+>�?@?@?�> & A � ØÕÜ�Ò.ÔµÒoÞ�Ý(Ö¤×�@sØßØ A *W@�& �+>@?@?�?�> &4APAqr 2 Ý(Øßá ä¬ÒoÜ$ãÙ§ÚeÒQÙ & A?ØßÜ+ÒwÔµÒQÞ�Òoá��-ÒoÓßÓ & �+>@?@?�?�> &4A � Òo×$ãq�Qã/âOÜ�èY��Ú=ã/áT��ã�ÒoÞ=Þ=Ó¼â6ÙgÚ=ã�ÒoÓÕԤ֤קؼÙgÚ=ÛcÜ-$çVÜ$ÙY�=ã�Ü$ä�×$Øßàhã���è

� � ���(���( �� �:�N���o�<��� � ������ ���� �$#

=¿á Ù§Ú=ØßÜ¢Ü$ã�ä�ÙgØßÖoá��¦ãK�=ã�Ü$ä�×$Øßàhãcä�Ú=Òo×gÒoä�Ùgã/קØ98�ÒQÙgØÕÖ¤á=Ü4æsÖo×¢Óßã/ÔµÒoÓUÒQá�� @�� >�� A{å¿ÓÕã�ÔµÒoÓGÞeÒQÙ§Ú=Ü�è��Ú=ÒQÙ5ØßÜ/ÝoæsÖ¤×�ܧã��Iç=ã�á=ä/ã�ܦÖoæZ�oã/âOÜN�«Ú=Øßä�ÚcÒo×$ã�ÞeÒQÙ§Ú=Ü�Øßá²Ü$Ö¤Ûwã�à=ØßáeÒQ×$â�٧קã/ãoÝIÒoá��u�«Ú=ØÕä�ÚÓÕã¬Ò�� Ù§Ö Ü$ç=àV٧קã�ã/Ü.æsÖ¤×$Ûwã�� àIâ ä/Ö¤á=Ü$ã�ä�ç`ÙgØ�;oã �Qã/âOÜ�ݳ×$ã�ܧÞhã�ä�ÙgØ_;¤ã�Ó¼â¤è ��Ú=ã æsÖ¤ÓßÓÕÖ3�«Øßá=Ô

j

Page 10: Optimal Binary Search Trees with Costs Depending on the Access

�Vã�*eá=ؼÙgØÕÖ¤á6ØßÜ«ç=Ü$ã/æsç=Ó�è�;ã/Ù���� � èu,4á*Ö¤× �Vã�קØÕá=Ô & ��>@?@?@?�> &76±ÖQæ¦Ù§Ú=ãK�oã/âOÜ Öoæ�� ØÕܪä¬ÒoÓÕÓßã�� �N�������V���

�«ÚVã�á1ã¬Òoä�Ú &WlUØßÜUã/ØÕÙ§Ú=ã�×UÛcØßáVØßÛwÒoÓµÖ¤×UÛwÒeB`ØßÛwÒoÓIØßá &Wl >@?�?@?�> & 6 Iè'=¿á¸ÙgÚVØßÜUä�ÒoܧãQÝOÓßÒoàhã�Óã�Òoä�Ú5&�l�Ý ; � &N��� ÝÎÒoÜ �N���cÖ¤× �V���¤Ý=×$ã�ܧÞhã�ä�ÙgØ_;¤ã�Ó¼â¤è��Ú=ã³æsÖ¤ÓÕÓßÖ3�«Øßá=Ô�ä�ÚeÒo×gÒQä/Ùgã/קØ�8�ã�Ü«ÓÕã�ÔµÒoÓXÞeÒQÙgÚVÜ�è �GÇIËÎÍ\Ç"� eÑN,±ÞeÒQÙ§Ú.ØÕÜ�Óßã�Ô¤ÒoÓ�ØÕæ(Òoá$�.Ö¤áVÓÕâ�ؼæGØÕÙ«ØßÜ«Ò²ÛcØßá`å{ÛüÒ&BüÖo× �=ã/קØßáVÔ=è� ��6K6 )�Ñ,�;ã/Ù & �+>@?@?�?�> & 6 àhã¸ÒwÓßã�Ô¤ÒoÓ'ÞeÒQÙgÚXè ��Ú=ã/á�ÙgÚ=ã/קã�ãSB`ØßÜ$٧ܪÒüà=ØÕáeÒo×�â�ܧã¬ÒQקä�Ú

٧קã/ãJ#�Ý�Ü$ç=ä�Ú ÙgÚeÒQÙ & �+>@?�?@?�> &76ÌØßܲÒ�ÞeÒLÙgÚ Öoæ=# è�={æ�ؼٲØßÜ�á=ÖoÙ1Ò�ÛcØßáOå¿ÛwÒeB*Ö¤× �Vã�×�åØÕá=Ô-Ù§Ú=ã�×$ã6ãCB`ØßÜ�ÙgÜ²Ò �Qã/â/& �«Ú=ØÕä�Ú ØÕÜ�á=ã/ØÕÙ§Ú=ã�×�Ù§Ú=ã6ÛcØßá=ØÕÛüÒoÓ?á=Ö¤×�Ù§Ú=ã�ÛwÒeB`ØßÛwÒoÓ5Öoæ & > & ���+>�?@?@?�> &76, IÝ � ��� '�`Oè'={æ�& ��� ØßÜUÒ³ÓÕã/æøÙ?ä�Ú=ØßÓ��²Øßá # ÙgÚ=ã/á!& � & ���+>@?@?@?�> &76+ÝØÕÛwÞVÓÕâOØßá=Ô�Ù§ÚeÒQÙ4& ØÕÜ?Ò+ÛüÒ&B��oã/âoè g`ØßÛcØßÓßÒoקӼâ¤Ý & ��� ä�Òoá¸á=ÖQÙUàhã!Ò�×$ØßÔ¤ÚµÙ(ä�Ú=ØßÓ���ÝLà�ã/ä¬Òoç=Ü$ãؼÙ>�¦Ö¤ç=Ó��cØÕÛwÞVÓÕâ³ÙgÚeÒLÙ & ØÕÜ�ÒªÛwØÕá(�oã�â¤è���Ú=ã�ä/Ö¤áµÙgקÒ��=Øßä�ÙgØÕÖ¤á²ØßÛcÞ=ÓßØÕã�Ü'ÙgÚeÒLÙ & �+>�?@?@?�> &76ØÕÜ«Ò²ÛwØÕá`å¿ÛwÒeBwÖ¤× �Vã�קØÕá=Ô=è��Ö¤á ;oã�קÜ$ã�Ó¼â¤ÝÎÓßã�Ù & �+>�?@?@?�> &76Êà�ã³Ò¸ÛcØßáOå¿ÛwÒeBcÖ¤× �Vã�קØÕá=Ô=è>7 ãªä�Öoá=Ü$٧קç=ä�Ù+Ò¸à=ØßáeÒQ×$â

٧קã/ã2# ܧç=ä�Ú ÙgÚ=ÒQÙ & �+>@?@?@?�> &76 ØßÜ4ÒüÞeÒQÙ§Ú�Öoæ8ØÕÙ�èLFeÖ¤×�ã¬Òoä�Ú$�$Ý ; � � ��� ÝXÓßã�Ù & à�ãã/ØÕÙ§Ú=ã�×�Ù§Ú=ãªÓßã�æøÙ!Ö¤×�קØßÔoÚIÙ�ä�Ú=ØßÓ���Öoæ & � ØßáJ# Ý=Òoä/ä�Ö¤×s�=ØßáVÔ�ÙgÖ(�«Ú=ã�ÙgÚ=ã/×,& ØÕÜ!Ò¸ÛcØßá�Ö¤×ÛwÒeB��Qã/â¤ÝI×$ã�ܧÞhã�ä�ÙgØ_;¤ã�Ó¼â¤è]={ÙUæsÖ¤ÓßÓÕÖ3�«Ü'Ù§ÚeÒQÙ #ÊØÕÜ?Ò�à=ØßáeÒQ×$â ܧã�Òoקä�ڸ٧קã�ãQè ��Ö¤á=Ü$ã��Iç=ã/áIÙ§ÓÕâoÝ& �+>@?@?�?�> & 6zØßÜ«Ò²ÓÕã�ÔµÒoÓXÞeÒQÙgÚXè� ��Ú=ã³æsÖ¤ÓÕÓßÖ3�«Øßá=Ô�Ö¤× �=ã/קØÕá=Ô²ØßÜ+ÒoÓÕܧֲÖoæ(ØßáµÙgã/קã/Ü$Ù¬èFeÖ¤×�� � � ÒQá�� 2 � � � � � O � n�Ý�Òoá Ö¤× �=ã/קØÕá=Ô����«Öoæ�� ØßÜüä¬ÒoÓÕÓßã��

@�� >�� A{å����F, � 0/"�, �«Ú=ã�áXÑ

� ����� �� � ����� ÙgÚ=ã/�oã�â`ÜüÖoæ���� � Òo×$ã.ØÕáÊØÕá=ä�×$ã¬ÒoÜ$Øßá=ÔCÖ¤×s�=ã�×$Øßá=Ô*Øßá���� Ýh�«Ú=ØÕÓßã6ÙgÚ=ÖoܧãuÖoæ��� � �� Òoקã³ØÕá/�Vã�ä�×$ã¬ÒoÜ$Øßá=ÔcÖ¤×s�=ã�×$Øßá=Ô �

� ��� � Mr��qr�� k T � � Òoá����� � �� Mr��qr�� k � ��� T �cè!5Ç��!���"eÑN, @�� >�� A{å¿ØÕá=ä�å �=ã�äªÖ¤×s�=ã�×$Øßá=Ô1ØÕÜ�á=ã�ä/ã�ܧܧÒoקØÕÓÕâ�Ò²ÛcØßá`å{ÛüÒ&B�Ö¤×s�=ã�×$Øßá=ÔVè� ��6K6 )�Ñ �'Òoàhã�Ó�ÙgÚVã��Qã/âOÜ+Öoæ#�$� � ÒQÜ+ÛcØßáXÝ=Òoá��uÒoÜ«ÛwÒeB�Ù§Ú=Ö¤Ü$ã�Öoæ%��� � �� è&

;<2

Page 11: Optimal Binary Search Trees with Costs Depending on the Access

��Ú=ã á=ãSB`٫٧Ú=ã�Ö¤×$ã�Û ä�ÚeÒQ×gÒoä�Ùgã�×$Ø98/ã�Üq@�� >�� A¿å¿ÓÕã�ÔµÒQÓXÞeÒQÙ§Ú=Ü�è �GÇIËÎÍ\Ç�� ��Ñ FeÖ¤× �or � Ò�ÞeÒQÙ§Ú ØÕÜc@�� >�� A{å¿Óßã/ÔµÒoÓUؼæ!ÒQá�� Ö¤áVÓÕâ ؼæ�ؼÙ�ØÕÜ ÒuÛcØßá`å{ÛüÒ&BÖo× �=ã/קØßáVÔ=ècFeÖ¤× � � � Ý(ÒuÞ=ÒQÙgÚ ØßÜ+@�� >�� A¿å¿ÓÕã�ÔµÒQÓUØÕæ�Òoá�� Ö¤á=ÓÕâ�ØÕæ¦ØÕÙ³ØßÜ Ò @�� >�� A¿å¿ØÕá=ä�å �=ã�äÖo× �=ã/קØßáVÔ=è� ��6K6 )�Ñ 7 Ú=ã/á/�:r � ÙgÚVãüקã/ܧç=Ó¼ÙgÜ�æsÖoÓßÓßÖ3�«ÜªæsקÖoÛ ��Ú=ã�Ö¤×$ã�Û ; è ��Ö¤á=ܧã��Iç=ã�áµÙgÓ¼â¤Ý��¦ãÒQܧܧçVÛwãªÙgÚVק֤ç=ÔoÚ=Ö¤çVÙ�Ù§Ú=ã³Þ=קÖOÖoæGÙgÚeÒQÙ�� � � è@ r��wA�Ñ ��Ú=ã�Ø��=ã¬Ò1Öoæ(ÙgÚ=ã Þ=קÖOÖoæ(ÖoæUáVã�ä�ã/ܧÜ$ØÕÙ¿â.ØßܫܧØÕÛwÞ=ÓÕãoè ��Ö¤á=Ü$Ø9�=ã/קØßáVÔüÒoá.Òo×$à=ؼå

Ù§×gÒo×�â�@�� >�� A{å¿Óßã/ÔµÒoÓhÞeÒQÙ§Ú�Ý$�¦ã Ü$Ú=Ö3� Ù§ÚeÒQ٫ؼÙ!ÜgÒLÙgØßÜ *eã�Ü!Ù§Ú=ã:�=ãC*eá=ØÕÙ§ØßÖ¤á6ÖQæ?ÒQá @�� >�� A{å¿ØÕá=ä�å�Vã�ä³Ö¤× �Vã�קØÕá=Ô=è�¦â Úµâ`ÞhÖoÙ§Ú=ã�Ü$ØßÜ�Ý2& ��>@?@?@?�> &76ÌØßÜ²Ò @�� >�� A{å¿Óßã/ÔµÒoÓ8ÞeÒQÙ§Ú�è ��ÚVã�á ÙgÚ=ã/קã6ØßܸÒ�à=ØßáeÒQ×$â

Ü$ã¬Òo×$ä�Ú-Ùg×$ã�ã # ÝhÚ=Ò3;OØÕá=Ô � ÒoÜ+ØÕÙgÜ«á=Ö5�=ã ܧã�Ù¬Ým�«Ú=ã�×$ã & ��>@?@?@?�> &76 ØÕÜ+ÒwÞeÒQÙ§Ú.ÖQæ�ØÕÙ�Ý�&76Ù§Ú=ã³ænÒQÙgÚ=ã/׫Öoæ?Ü$Ö¤Ûcã�k�� T � � Òoá��uÙgÚ=ã³Ü$ç=àVÙg×$ã�ã #(@ k��sA!ä�ÖoáIÙgÒoØßáVÜ+ãSBVÒoä/Ù§ÓÕâ6ÙgÚVãq�Qã/âOÜÖQæ � � è �;ã/Ù�� r & ��>@?@?@?�> &76, Iè�7 ãcÞ=קÖ3;oãwÙgÚ=ÒQÙ & �+>@?�?@?�> & 6±ÜgÒLÙgØßÜ *eã�ܳÙgÚVãcÙ§Ú=קã/ãÒQà�Ö3;¤ã ä�Öoá��=ØÕÙ§ØßÖ¤áVÜ!æs֤׫Òoá @�� >�� A{å¿ØÕá=ä�å �=ã�äªÖ¤×s�=ã�×$Øßá=ÔVèhF(ØßקÜ�Ù¬Ý=ä/Óßã�ÒoקӼâ�� � � � � �� ègOã�ä�Öoá���ÝVÜ$ç=Þ=Þh֤ܧã+ÙgÚ=ã/קã+ãCB`ØßÜ�ÙgÜ�Ò��Qã/â!&�l=T�� � �ÌÜ$ç=ä�ÚüÙgÚ=ÒQÙ2&�l � &Wl ��� æsÖ¤×5Ü$Ö¤Ûwã; � & � � è g`ØÕá=ä�ã2#ÌØßÜ¢Ò�à=ØßáeÒQ×$â.ܧã¬ÒQקä�Ú Ùg×$ã�ãoÝ;ؼ٢æsÖ¤ÓÕÓßÖ3�«Ü�Ù§ÚeÒQÙ &Wl ��� ØßÜ4Ò��oã/â�ÖoæÙ§Ú=ãcÓßã/æøÙ�ܧçVàVÙg×$ã�ãüÖQæ &�l/è/g`Øßá=ä/ã &Wl�ØÕÜ ÒoálÒoáVä�ã�Ü�ÙgÖ¤×�Öoæ & 6�Ýp��ã+�Iá=Ö3� ÙgÚeÒQÙ�k�� ÒQÓßܧÖàhã�ÓÕÖ¤á=Ԥܢ٧Ö6ÙgÚ=ØÕܪܧç=àV٧קã/ãoÝ'ä�Ö¤áµÙ§×gÒ��=ØÕä/Ù§Øßá=ÔIk�� � &�l/Ý;ØßÛcÞ=ÓßØÕã���àµâ$&Wl2T � èuX+ã�á=ä/ãáVÖ Ü$ç=ä�Ú & ä¬ÒQáAãCB`ØÕÜ$Ù¬è ��Ö¤á=Ü$ã��Iç=ã�áµÙ§ÓÕâ¤Ý!Ù§Ú=ã/�oã/âOÜ�ÖQæ � ��� Òo×$ãuØÕáÊØÕá=ä�×$ã¬ÒoÜ$Øßá=ÔÖo× �=ã/קØßáVÔ Øßá & �+>@?�?@?�> &76+è g`ØÕÛwØÕÓ Òo×$ÓÕâoÝN�¦ã Þ=×$Ö&;oã-ÙgÚ=ÒQÙüÙ§Ú=֤ܧã-Öoæ � �� ��� æsÖ¤×$Û Ò�Vã�ä�×$ã¬ÒoÜ$Øßá=Ô6Öo× �=ã/קØßáVÔ=èL��Ú=ØÕ× ��Ý�Ü$ç=Þ=Þh֤ܧã¸Ù§ÚeÒQÙ � � � Mr �6Òoá�� k MT �üè �¢ã/á=ÖoÙgãàµâ'& A¦ÙgÚ=ãcÛwÒeB`ØßÛwÒoÓ>�Qã/â Öoæ � ���wè ��ÓÕã¬Òo×$ÓÕâoÝ4&4A-� k èc7 ã1Ùg×�â ÙgÖuÓßÖOä¬ÒQÙ§ãK�oã/âk Øßá # èbg`ç=Þ=Þh֤ܧã�Ù§ÚeÒQÙ+k ØßÜwÒ �=ã/ܧä�ã/á��eÒoáµÙuÖoæ &4A¿è ��Ú=ã/áwk à�ã/ÓßÖ¤áVÔ¤ÜcÙ§Ö ÙgÚVã×$ØßÔ¤ÚµÙüܧç=àV٧קã/ã�� Öoæ &4A¿è ��Ö¤á=Ü$ã��Iç=ã�áµÙ§ÓÕâ¤ÝI#(@ k��sAwØÕÜ�ÒoÓÕܧÖlØÕá��¸è ={æ Ptr � ÙgÚ=ã/ák T:# @ k��sA�Ý�Òwä/Ö¤áµÙgקÒ��=Øßä�ÙgØÕÖ¤á�èh7 ÚVã�á P�� � �¦ã �Iá=Ö3� ÙgÚeÒQÙ�&4A >@?@?@?�> &76 ØÕÜ4ÒcÞeÒQÙ§ÚÖQæ��¸è(��ã�ä�Òoç=ܧãN# ØßܳÒ�à=ØÕáeÒo×$â-ܧã�Òoקä�ÚCÙg×$ã�ã1Òoá�� Ù§Ú=ã1ÛüÒeB`ØÕÛüÒoÓÕØÕÙ¿â6ÖQæ &4A¦ØÕá � ØÕÙæsÖoÓßÓßÖ3�«Ü+ÙgÚeÒQÙ & A ����>@?�?@?�> & 6 T � �� è ��Öoá=ܧã��OçVã�áµÙgÓ¼â¤Ý'à�ã/ä¬ÒoçVܧã¸ÙgÚVãu�oã/âOܳÖoæ�� �� � �ÒQקã Øßáw�Vã�ä�×$ã¬ÒoÜ$Øßá=Ô Ö¤×s�=ã�×$Øßá=Ô ØÕá & �+>�?@?@?�> &76+Ýo�¦ã ä�Öoá=ä�ÓÕç��=ã�ÙgÚ=ÒQÙ & A ��� ØßÜ�Ò ×$ØßÔ¤ÚµÙä�ÚVØßÓ9�XÝ�à=ç`Ù & A � d >�?@?@?�> &76 > k��«Òoקã�ÒoÓßÓ'Óßã�æøÙ4ä�ÚVØßÓ9�Vקã�áXèL��ã/ä¬Òoç=Ü$ã k � &4A ���+>@?@?@?�> &76 > k��ؼÙ5æsÖ¤ÓßÓÕÖ&�«Ü�Ù§ÚeÒQÙ k Û¸ç=Ü�Ù�àhã�ÓÕÖ¤á=Ô³ÙgÖ #(@ k��sA�è���Ú=ã4ÓßÒQ٧٧ã�×5ä�Ö¤áµÙ§×gÒ��=ØÕä/Ù§Ü�ÒoÔ¤ÒoØßá1ÙgÚ=ã+ænÒoä/ÙÙ§ÚeÒQÙB# @[k�� A¦ä�ÖoáIÙgÒoØßáVÜ�ãCBVÒoä/Ù§ÓÕâ � � èNX+ã�á=ä/ã�k ØÕÜ!á=ÖoÙ+Òu�=ã/ܧä�ã/á��eÒoáµÙ�Öoæ & A�èN0+ã�ØÕÙ§Ú=ã�×ä�Òoá(k àhã!Òoá1ÒQá=ä�ã/Ü$ÙgÖo×UÖoæ & A{è'��ã/ä¬Òoç=Ü$ã�Øßá�Ù§Ú=ØßÜ(ä¬ÒoÜ$ãoÝ &4AÎà�ã/ÓßÖ¤á=ÔoÜ(ÙgÖ�ÙgÚ=ã!ÓÕã/æøÙ(ܧç=à`Ùgקã/ã�ÊÖoæ]k ÝeØßÛcÞ=ÓÕâOØßáVÔ�ÙgÚeÒLÙ�k�� � k àhã�ÓÕÖ¤á=Ô¤Ü�Ù§Ö���ÝÎÒ1ä�Ö¤áµÙ§×gÒ��=ØÕä/Ù§ØßÖ¤á�è>��Ú=ã�×$ã�ÛwÒoØßáVØßá=ÔÞhÖ¤Ü$ܧØßàVØßÓßؼٿâ�ØÕܳ٧ÚeÒQÙ�k ØÕÜ áVã�ØÕÙ§Ú=ã�×�Òt�Vã�ܧä/ã�á��=ÒoáµÙ²á=Ö¤×�ÒoálÒQá=ä�ã/Ü$ÙgÖo×�Öoæ &4A¿èI=¿á Ù§Ú=ØßÜ

; ;

Page 12: Optimal Binary Search Trees with Costs Depending on the Access

ä�ÒoܧãQÝ'Óßã/Ù %6àhã²ÙgÚ=ã²á=ã�Òoקã/Ü$Ù ä�ÖoÛwÛcÖ¤áCÒoá=ä/ã�Ü�Ùg֤׳ÖoæNk Òoá�� & A{è%�¢ã�á=ÖQÙgã²àµâ � Òoá$�� ÙgÚ=ã³ÓÕã/æøÙ+Òoá��uקØÕԤڵ٫ܧç=à`Ùgקã/ã�Ü�Öoæ %`Ýh×$ã�Ü$Þ�ã/ä/ÙgØ_;¤ã/ÓÕâ¤è ={æ>k ØÕÜ+ØÕá �ÊÙgÚ=ã/á &4A?Û¸çVÜ$Ù+à�ãØÕá �¸Ý;ä�Ö¤áµÙ§×gÒ��=ØÕä/Ù§Øßá=Ô &4AB�bk èq��Ú=ã²ÖoÙgÚVã�תä¬ÒQܧã1ØßÜ k ØÕá �rÒQá��$& A8Øßá ��Ý;ÛwÒ��IØßá=ÔؼÙ4ØÕÛwÞhÖ¤Ü$ܧØßàVÓßã¢ÙgÚVã¸ÒoÜ$ܧç=ÛcÞVÙgØÕÖ¤átk � k ��� èY��Ú=ã/קã/æsÖoקã�Ù§Ú=ã¸ÒoÓ¼Ùgã/קáeÒQÙ§Ø�;oã Ù§ÚeÒQÙYk ØßÜáVã�ØÕÙ§Ú=ã�×�Òq�=ã/ܧä/ã�á��eÒQáIÙ«áVÖ¤×!Òoá�Òoá=ä�ã/Ü$Ù§Ö¤×!Öoæ &4A;ä¬ÒQá6ÒoÓßÜ$Ö�á=ÖQÙ!ÖOä�ä�çV×�è$��Ö¤á=Ü$ã��Iç=ã/áIÙ§ÓÕâoÝ� � � Mr ��ØÕÛwÞ=ÓÕØßã/ÜGk T �cèL��Ú=ã¸ÞVקÖOÖoæUÙgÚ=ÒQÙ � �� � � Mr ��ØßÛcÞ=ÓÕØßã�Ü�k � ��� T �ØÕܫܧØßÛcØßÓßÒo×�è ��Ö¤á=Ü$ã��Iç=ã/áIÙ§ÓÕâoÝ�& ��>@?@?@?�> &76 ØÕÜ�ÒQá @�� >�� A¿å{Øßá=ä�å �=ã/ä Öo× �=ã/קØßáVÔ=ÝÎܧã/Ù$ÙgÓÕØßá=Ô²ÙgÚVãÞVקÖOÖoæ?ÖQæ?á=ã/ä�ã/ܧܧؼٿâ¤è@ � r1A�Ñ���Ú=ã¦Ø9�=ã�Ò�Öoæ=Ù§Ú=ã8Þ=קÖOÖoæ=ÖQæ=ÙgÚ=ã¦ä�Ö¤á ;oã�קÜ$ã!ØßÜ(ÒoÜ'æsÖ¤ÓßÓÕÖ3�«Ü�è ��Ö¤á=ܧØ��=ã�×(Ò�Ü$ã/Ù?Öoæ

�Qã/âOÜ � Òoá��üÒ Ü$ç=à=ܧã�Ù!ÖoæXØÕÙ5æsÖ¤×$ÛwØÕá=Ô Òoá @�� >�� A{å¿ØßáVä�å �Vã�ä«Ö¤× �Vã�קØÕá=Ô & �+>@?�?@?�> & 6 Iè>7 ãä/Ö¤á=Ü�ÙgקçVä/Ù8Ò¢à=ØÕáeÒo×$â Ü$ã¬Òo×$ä�Úc٧קã�ã #ÊæsÖ¤×�� ܧç=ä�Ú²Ù§ÚeÒQÙ & �+>@?@?@?�> & 6� +ØÕÜUÒoá/@�� >�� A¿å{Óßã/ÔµÒoÓÞ=ÒQÙgÚuÖoæC#�èg`çVÞ=Þ�Öoܧã¸ÙgÚ=ÒQÙ & �+>@?@?@?�> &76 ØÕÜ¢Òoá @�� >�� A{å¿ØßáVä�å �Vã�ä�Öo× �=ã/קØßáVÔ=Ý 2 � �B� � � OR�wn�è��Öoá=Ü$٧קç=ä�Ù5Ò4à=ØÕáeÒo×$âªÙ§×§ã/ã # � ÒoÜGæsÖ¤ÓßÓÕÖ&�«Ü/è]��ÚVã!ܧã��OçVã�á=ä/ã & �+>@?�?@?�> & 6*ØßÜ(Ò4ÞeÒQÙ§Ú¸Öoæ8# � ÝÜ$ç=ä�Ú�ÙgÚ=ÒQÙ &

�ØÕÜ�Ò Óßã/æøÙ8Ö¤×8קØÕÔ¤ÚµÙ8ä�Ú=ØßÓ��üÖoæ &

� � Ý`Òoä�ä/Ö¤× �=ØÕá=Ô�Ù§Ö��«ÚVã/ÙgÚVã�× & � � & � ��� Ö¤×&

�� &� ��� ݤ×$ã�Ü$Þ�ã/ä/ÙgØ_;¤ã/ÓÕâ¤è # � ÒQÓßܧÖ4ä�Ö¤áµÙ�ÒQØßá=Ü�Ò¢Ü$ç=àV٧קã�ãB# � @ k��sA�ݵÚeÒ<;`ØÕá=Ô³Òoá1Òo×$à=ØÕÙ§×gÒo×�â×$Ö`ÖQÙ'k�� T�� � ÝIÒoá��1ÜgÒQÙ§ØßÜ�æøâ`ØÕá=Ô4Ù§Ú=ã!æsÖ¤ÓßÓÕÖ3�«Øßá=Ô�Þ=ק֤Þhã�×�Ù¿âhÑ # �[@ k�� A(ØßÜUÒ¢à=ØßáeÒQ×$â�ܧã¬ÒQקä�Ú٧קã/ã6ä�Ö¤áµÙ�ÒQØßá=ØÕá=Ô�ãCBVÒoä�ÙgÓ¼âlÙgÚ=ãI�Qã/âOÜ1Öoæ � �� è F?Øßá=ÒoÓßÓ¼â¤Ý?ÛwÒ��Qã�k�� ÙgÚ=ã6ÓÕã/æøٲ֤ײ×$ØßÔ¤ÚµÙä�ÚVØßÓ9� ÖQæ+& 6+Ý;Òoä�ä/Ö¤× �VØßá=Ô�Ù§Ö�«ÚVã/ÙgÚVã�× &76 T � �� Ö¤× & 6 T � Ý�×$ã�ܧÞhã�ä�ÙgØ_;¤ã�Ó¼â¤è(��ÚVãä/Ö¤á=Ü�ÙgקçVä/ÙgØÕÖ¤ácÖoæ�# �OØßÜ�ä/Ö¤ÛcÞ=Óßã�Ùgã��Xè �;ã/Ù � r & �+>@?@?@?�> &76, IèNgOØßá=ä/ã & �+>@?�?@?�> & 6 ØßÜ5ÒQá@�� >�� A{å¿ØßáVä�å �Vã�ä«Ö¤× �Vã�קØÕá=Ô=ݵؼÙ�æsÖ¤ÓßÓÕÖ&�«ÜUÙ§ÚeÒQÙ � � � � r��=è'X+ã�á=ä/ã�Ù§Ú=ã�Þ=ÒQÙgÚ!& �+>�?@?@?�> &76ÒQá���# @[k��sA�Òoקã(�VØßÜ[-$ÖoØßáµÙ¬èL��ÚVã¸Ó ÒQÙ$Ùgã/×4ä�ÖoÛwÞ=ÓÕã/Ù§ã�Ü4Ù§Ú=ã²Òo×$Ô¤ç=Ûcã�áµÙ¢ÙgÖüܧÚ=Ö3� ÙgÚeÒQÙ-# �

ØÕÜ!Ò�àVØßáeÒo×�â1Ùgקã/ãoèhJ.Ö¤×$ã�Ö3;¤ã/×�Ý$�¦ãL�«ØßÓÕÓÎä�Ö¤á=ä/Óßç��Vã4ÙgÚeÒLÙ!ØÕÙ�ØßܦØßáüænÒoä�Ù�Ò�àVØßáeÒo×�âcܧã¬ÒQקä�Ú٧קã/ãoè 7 ØÕÙ§Ú Ù§Ú=ØßÜcÞ=ç=×$Þ�ÖoܧãoÝ�Óßã/Ù$% ��> % d à�ã/�oã�âOÜ�Öoæ # � Ý % � àhã�ÓßÖoá=Ô¤ØßáVÔCÙ§Ö*Ù§Ú=ã-ÓÕã/æøÙÜ$ç=àV٧קã�ã �AÖoæ % d è$��Ö¤á=Ü$Ø9�=ã/×�ÙgÚ=ã³Þh֤ܧÜ$Øßà=ØÕÓßØÕÙ§Øßã/Ü�Ñ

� �4GK"��oÑD% �+> % d T �cègOØßá=ä/ã & �+>�?@?@?�> &76ÌØßܲÒoá @�� >�� A{å¿ØßáVä�å �Vã�äüÖo× �=ã/קØßáVÔ=Ý�àµâ/�;ã�ÛcÛüÒ ; ØÕÙ²ØÕܸÒ�ÛcØßá`å{ÛüÒ&BÖo× �=ã/קØßáVÔ=è'�¦âK��ÚVã�Ö¤×$ã�Û ; ؼÙ5Û¸ç=Ü�Ù¦àhã�Ò ÓÕã�ÔµÒoÓVÞeÒQÙgÚXè�X�ã/á=ä�ã-% � àhã�ØßáVÔ ØÕá � ØßÛcÞ=ÓßØÕã�Ü% � � % d è

� �4GK"��µÑD% � T�� � Òoá$� % d T �üègOç=Þ=Þh֤ܧã & 6 r % d è���Ú=ã/ák��¦Û�ç=Ü$Ù«àhã4ÙgÚVãªÓßã/æøÙ!ä�Ú=ØßÓ���Öoæ &76�èN�¦âüÙ§Ú=ãªä�Öoá=Ü$٧קç=ä�ÙgØßÖoáÖQæB# �ßÝ>�¦ã�ä�Ö¤áVä�Óßç$�=ãüÙgÚ=ÒQÙN% d T � �� è X+ã�á=ä/ã % � � % d è g`ç=Þ=ÞhÖ¤Ü$ã�á=Ö3� % d Mr &76+è�8â �!Òoܧã ; Ý\��ãcä�Öoá=ä�ÓÕç��=ã1ÙgÚeÒQÙ & 6 � % d è�g`ç=Þ=ÞhÖ¤Ü$ã & 6 T � �� è+��Ú=ã/á % � � &76+ÝØÕÛwÞVÓÕâOØßá=Ô % � �7% d è6,4ÓÕÙ§ã�×$áeÒQÙgØ_;¤ã/ÓÕâ¤Ýeä/Ö¤á=Ü$Ø9�=ã/× &76 T � è6=¿á.ÙgÚVØßÜ«ä¬ÒoÜ$ãoÝ�ØÕæ % d T �

; `

Page 13: Optimal Binary Search Trees with Costs Depending on the Access

Ù§Ú=ã�á % d > &76*Û¸ç=Ü�Ù�ÒoÞVÞ�ã�Òo×?ØÕá�ØßáVä�קã�ÒoܧØÕá=Ô4Öo× �=ã/קØßáVÔ=Ýoàhã�ä�Òoç=ܧã & �+>@?�?@?�> & 6CØßÜ?ÒoáI@�� >�� A¿åØÕá=ä�å �=ã�ä²Öo× �=ã/קØßáVÔ=èuX�ã/á=ä�ã$% d � &76+ÝGÒ�ä/Ö¤áµÙgקÒ��=Øßä�ÙgØÕÖ¤á�è%��Öoá=ܧã��OçVã�áµÙgÓ¼â¤Ý % d T � �� è��Ú=ÒQÙ+ØßÜ�Ý % � � % d è� �4GK"��¤ÑD% � T � Òoá�� % d T � �� è��ÚVØßÜUä�Òoܧã�ä�Òoá1á=ÖoÙ�ÖOä�ä/ç=×�ݵàhã�ä�Òoç=ܧã«Ø¼ÙUØßÛcÞ=ÓÕØßã�Ü'ÙgÚ=ÒQÙ % d ØßÜ?ÒL�=ã�Ü$ä�ã�á$�eÒoáµÙ�ÖQæ�% � è'��Ú=ØßÜä/Ö¤áµÙgקÒ��=Øßä�ÙgÜ�% � à�ã/ÓßÖ¤á=ÔoØßá=Ô¸Ù§Ö1Ù§Ú=ã³Óßã�æø٫ܧç=àV٧קã/ã�Öoæ % d è� �4GK"��eÑD% �+> % d T�� � ègOØßá=ä/ã # @ k��sA�ØßÜ«Ò1à=ØÕáeÒo×$âüܧã�Òoקä�ÚuÙgקã/ãoÝ % � à�ã/Øßá=Ô1ØÕá �ÊØßÛcÞ=ÓßØÕã�Ü % � � % d èFeקÖoÛ ÙgÚ=ã�Òoà�Ö3;oã!ä¬ÒoÜ$ã�Ü/Ý���ã�ä¬Òoá�ä�Ö¤á=ä/Óßç��Vã¦ÙgÚ=ÒQÙ % � àhã�ÓÕÖ¤á=Ô¤ØÕá=Ô«ÙgÖI#�� @ % d A;ØßÛcÞ=ÓßØÕã�ÜÙ§ÚeÒQÙ2% � � % d Ý'æsÖ¤×�Òoáµâ% ��> % d T�� � � � è/g`ØÕÛwØÕÓ Òo×$ÓÕâoÝ�ØÕÙ ä¬ÒQá àhãüÞ=×$Ö&;oã�� Ù§ÚeÒQÙ2% �àhã�ÓÕÖ¤á=Ô¤ØÕá=Ô�ÙgÖ:#��'@ % d A¸ØÕÛwÞ=ÓÕØßã/ÜN% � � % d è ��Ö¤á=Ü$ã��Iç=ã/áIÙ§ÓÕâoÝ=# �8ØßÜcÒCà=Øßá=Òo×$â ܧã¬ÒQקä�Ú٧קã/ãwä/Ö¤áµÙ�ÒoØÕá=Øßá=Ô6Ù§Ú=ã+�Qã/âOÜ Q @*# � A1r � � � � è �;ã/Ù � � r ��� Q @�# � A�è�7 ãcá=Ö3�

ØÕá=ä�ÓÕç��=ã6ØÕá5# � ã�Òoä�Ú �Qã/â Öoæ � � ݦÒoܸæsÖ¤ÓÕÓßÖ3�«Ü�è ={æ�� � � r �*Òoá�� � � 2 ÙgÚ=ã/áØÕá=ä�ÓÕç��=ãck T � � Øßá # � Ü$ÖCÒoÜ & � àhã�ä/Ö¤Ûcã�ܸÙgÚVã�קØÕÔ¤ÚµÙ²ä�Ú=ØßÓ��lÖoæGk è g`ØÕÛwØÕÓ Òo×$ÓÕâ¤Ý'ؼæ� ��� �� r ��Òoá�� � �bOR�wnuÙ§Ú=ã�á�k � ��� T � ��ØßÜ4Øßá=ä/Óßç��=ã���Øßá # �XØßá�Ü$ç=ä�Ú*Òc�!Ò¬âÙ§ÚeÒQÙ�& � ØßÜ!Ù§Ú=ã Óßã/æøÙ«ä�ÚVØßÓ9��Öoæ]k � ��� èh0�ÖQÙgãªÙgÚeÒLÙ+Ù§Ú=ã�Òoà�Ö3;oã Ù �¦Öwä/Ö¤á��=ؼÙgØÕÖ¤á=Ü«ä¬Òoáuá=ÖoÙÖOä�ä/ç=×+ܧØßÛ�ç=ÓÕÙgÒoá=ã�Öoç=ܧӼâ¤èD0+ãCBOÙ¬ÝÎæs֤׫ã¬ÒQä�Ú �oã�â-Öoæ � ��á=ÖoÙ«â¤ã�Ù¢ØßáVä�Óßç$�=ã��.Øßá�ÙgÚ=ã³Ùg×$ã�ãoÝØÕá=ä�ÓÕç��=ãwØÕÙ�Òoä�ä/Ö¤× �=ØÕá=Ô-Ù§Ö-ÙgÚ=ãüקç=ÓÕã�ܸÖoæ«àVØßáeÒo×�â*ܧã¬ÒQקä�Ú Ùg×$ã�ã�ØÕá=ܧã/×$ÙgØÕÖ¤á�è �'ã�Ù2#rà�ãÙ§Ú=ã+*=áeÒoÓ5Ùgקã/ã�ܧÖ-Ö¤àVÙ�ÒQØßá=ã���è gOØßá=ä/ã$# �UØÕÜ�Ò-àVØßáeÒo×�âCܧã�Òoקä�Úl٧קã�ãQÝ # ØßÜ�ܧÖ=è/,4ÓÕܧÖ=Ý# �'ØÕܳÒ�Þ=Òo×$Ù§Ø ÒoÓ(ܧç=àV٧קã/ãwÖoæD# è ��Óßã�ÒoקӼâ�Q @*# ALr � ÒQá�� & �+>@?@?�?�> & � ØßܳÒ6ÞeÒQÙ§ÚCÖoæ# �ßè ��Ö¤á=ܧã��Iç=ã�áµÙgÓ¼â¤Ý'Øßá-Ö¤× �=ã/×4ÙgÖüܧÚ=Ö3� ÙgÚeÒQÙ & �+>@?�?@?�> & 6 ØßÜK@�� >�� A¿å{Óßã/ÔµÒoÓYÝÎؼ٢קã/ÛüÒQØßá=ÜÖoá=ÓÕâ1ÙgÖ²ÞVקÖ3;¤ã¢Ù§ÚeÒQÙ # � @[k�� A�r � � èN4 �Iç=Ø�;QÒoÓÕã�áµÙgÓ¼â¤ÝOÙgÚeÒQÙ # @[k��sANrE# � @[k��sA�è g`ç=Þ=ÞhÖ¤Ü$ãÙ§Ú=ã�ä/Ö¤áµÙg×gÒQ×$â¤è���Ú=ã/á #(@ k��sA³á=ã�ä/ã�ܧܧÒoקØÕÓÕâ ä�Ö¤áµÙ�ÒQØßá=Ü�ܧ֤Ûcã��oã�â %5T � �ßè g`ç=Þ=ÞhÖ¤Ü$ã% T�� è ��ÚVã³æsÖoÓßÓßÖ3�«ØÕá=Ô²ÒoÓ¼Ùgã�×$áeÒQÙ§Ø�;¤ã/Ü�ãCB`ØßÜ�Ù¬è

� �4GK"���� �$� � Mr �=è�8â�ÙgÚ=ãu�Vã�*eá=ؼÙgØÕÖ¤áCÖoæ:@�� >�� A{å¿ØßáVä�å �Vã�ä¸Ö¤×s�=ã�×$Øßá=ÔVÝ;ØÕÙ¢æsÖ¤ÓÕÓßÖ3�«Ü4Ù§ÚeÒQÙ:k T��wèu��ÚeÒQÙ³ØÕÜ�Ýk ØÕܪÒ6Þ=ק֤Þhã�׳ÒQá=ä�ã/Ü$ÙgÖo× ÖQæhk���ØÕá:# èuX+ã�á=ä/ãoÝC% Mr k èKg`ØÕá=ä�ã(k ØßÜ�ÙgÚ=ã1ÛwÒeB`ØßÛwÒoÓ�Qã/â1Öoæ� ÝIØÕÙ�æsÖoÓßÓßÖ3�«Ü %V� k è>��Ú=ã�ácÙgÚ=ã«à=ØÕáeÒo×$â¸Ü§ã¬ÒQקä�Úw٧קã/ã�ØÕá=ܧã/×$ÙgØÕÖ¤á1Þ=קÖOä�ã��=ç=×$ã�¦Ö¤ç=Ó��wáVÖoÙ�ØÕá=ä�ÓÕç��=ã�%�ØÕácÙ§Ú=ã«×§ØÕÔ¤ÚµÙ¦Ü$ç=àV٧קã�ã�Öoæ k è �¢ácÙ§Ú=ã�ÖQÙgÚ=ã/צÚeÒQá���Ý k���àhã�ÓÕÖ¤á=Ô¤ÜÙ§Ö²ÙgÚ=ã³×§ØÕԤڵ٫ܧç=à`Ùgקã/ã�ÖQæ]k Ý=ÒoÜ�k � k���è X�ã/á=ä�ã % MT�Q @*# @ k�� A A�è� �4GK"���� �$� � r �=è={æ �]r 2 ÙgÚ=ã/á � r �=ݤä/Ö¤áµÙg×gÒW�=Øßä�ÙgØßáVÔ % T�� èp7 Ú=ã�á � � 2 Ý7& � ØÕÜ(Ù§Ú=ã�×$ØßÔ¤ÚµÙUä�ÚVØßÓ9�ÖQæ�k ݤàµâ³ÙgÚVã�ä�Öoá=Ü$٧קç=ä�ÙgØßÖoá�Öoæ # è>X�ã�áVä�ã %V� k ÝQØßÛcÞ=ÓÕâOØÕá=Ô!ÙgÚeÒLÙ?ÙgÚVã¦à=ØÕáeÒo×�â³Ü§ã¬ÒQקä�Ú٧קã/ã ØÕá=ܧã/×$Ù§ØßÖ¤áuÒoÔµÒQØßá6ä�Öoç=Ó9��á=ÖoÙ+ØÕá=ä�ÓÕç��=ã %1ØßáR# �>@[k A�èNX�Ö3�¦ã�;¤ã/×ok�� TUQ @�# �>@[k AsA�è

; U

Page 14: Optimal Binary Search Trees with Costs Depending on the Access

��Ú=ÒQÙ+ØßÜ�Ý % MT:Q @*# @[k�� A A�è��Ö¤áVܧã��Iç=ã/áµÙgÓÕâoÝ�%$T�� ØÕÛwÞ=ÓÕØßã/Ü8Ù§ÚeÒQÙ�%²ØßÜ�á=ÖQÙ�ØßáJ# @[k�� A�èhg`ØÕÛwØÕÓ Òo×$ÓÕâ¤Ý��¦ãªÞ=×$Ö&;oã

Ù§ÚeÒQÙV% T � �� ÒQÓßÜ§Ö ØÕÛwÞVÓßØßã/Ü Ù§ÚeÒQÙV%Cä¬Òoá á=ÖQÙ1à�ã�Øßá # @ k��sA�è ��Ú=ã�×$ã/æsÖ¤×$ã # @ k��sA�ØßÜæsÖoקÛcã��CãCBVÒoä�ÙgÓÕâCàµâ Ù§Ú=ãK�oã/âOÜ�Öoæ � � è+X�ã�áVä�ã!& �+>@?�?@?�> & 6±ØßܳÒQá @�� >�� A¿å{Óßã/ÔµÒoÓUÞeÒLÙgÚ�Ýä/Ö¤ÛcÞ=Óßã�ÙgØßáVÔ¸ÙgÚ=ã³Þ=×$Ö`ÖoæGÖoæ]��Ú=ã/֤קã/Û ``è�

� � �������I�'�< � ��� � #'� ��� #

=¿á�ÙgÚVØßÜ�ܧã/ä/Ù§ØßÖ¤á��ã³ä/Ö¤ÛwÞVçVÙgã³Ü§ÖoÛwãªÛcã¬ÒoÜ$ç=קã/ܫקã�ÓßÒQÙgã��6ÙgÖ1ÙgÚ=ã³Þ=×$Ö¤à=Óßã/Û.è]7 ã³Ü$ÙgÒo×$Ùàµâ ä/Ö¤ÛwÞVçVÙgØÕá=ÔCÒ*ä/Ö¤ç=Þ=ÓÕã6Öoæ¢Ôoã�á=ã/×gÒoÓ�Ûcã¬ÒoÜ$ç=קã/ÜüÒQá��ÊÓßÒQÙgã/׸ç=Ü$ãuÙ§Ú=ã�Û Ù§Ö �Vã��=ç=ä/ãÜ$Ö¤Ûcã�ÞeÒQ×gÒoÛcã/Ù§ã�קܫØÕÛwÞhÖ¤×$ÙgÒoáµÙ�æs֤׫ÙgÚ=ã Þ=קÖoà=Óßã/Û.Ñ8áIç=Û¸àhã�×+ÖoæUÜ�Ùgã�ÞVÜ4Þhã�×$æsÖoקÛcã��-àµâÙ§Ú=ã�ÒoÓßÔ¤ÖoקØÕÙ§Ú=ÛuÝ=ܧÞeÒQä�ã�ä/Ö¤ÛcÞ=ÓßãSBVؼٿâ¤ÝeÜ$Ø98�ã�Öoæ?Ù§Ú=ã�ØÕá=Þ=çVÙ�Òoá$�-áIç=Û¸àhã�×�ÖoæG@�� >�� A¿å{Óßã/ÔµÒoÓÞ=ÒQÙgÚ=Ü/è'7 ão*eקÜ�Ù�ä�Ö¤ÛcÞ=çVÙ§ã4ÙgÚVãªÒoàhÖ&;oãªÛwã�ÒoܧçVקã�Ü�ãCBVÒoä/Ù§ÓÕâüÒoá��6ÓßÒQÙgã/×�Ô¤Ø_;¤ã¢ÒQá6ã¬ÒoÜ$Øßã�×Ù§Ö.Ôo×gÒoÜ$ÞlÒoÞ=ÞVקÖ<B`ØßÛwÒQÙgØÕÖ¤á�è���Ú=ã+*eá=ÒoÓ5קã�Ü$ç=ÓÕÙ�Øßܪ٧ÚeÒQÙ���ãwÞeÒ¬â M�@PO ��� d)A¢ÙgØÕÛwãcÒoá$�Mc@PO ����� A!ܧÞ=Òoä�ãQè7 ã1ÛüÒ��Qã²Ú=ã¬Ò<;IâCç=Ü$ãwÖoæ¦Ô¤ã/á=ã�קÒQÙgØÕá=Ô�æsç=á=ä�ÙgØßÖoá=ܪÙgÖ�Ö¤àVÙgÒoØßá Ö¤çVתקã�Ü$ç=ÓÕÙ§Ü�è�Hªã�á`å

ã/×gÒQÙ§Øßá=Ô æsç=á=ä�ÙgØßÖoá=ܦ×$ã�Þ=×$ã�Ü$ã�áµÙ+Ò�Ü$ã��Iç=ã�áVä�ã �� �� ��� �!ÒoÜ�Ò�ä�Ö¤ÛcÞ=ÓÕãCBIå ;QÒoÓÕç=ã��1æsç=á=ä�ÙgØßÖoá�Z@!% ATr � �� � � �L% � @sÙ§Ú=ØßÜwÖ¤Þhã�×gÒLÙgØßÖoáAØßÜüÒoÓßÜ$Ö ä�ÒoÓßÓÕã��ÊÙ§Ú=ãU%LåYÙgקÒoá=Ü$æsÖoקÛcA�è �«ã�ä/ç=×�å×$ã�á=ä/ã�Ü/Ý5Ù§ÚeÒQÙ²ØÕÜ�ÝUã��IçeÒQÙgØÕÖ¤á=ܸ٧ÚeÒQÙ(�Vã�*eá=ã��� �� uàIâ קã/Ó ÒQÙ§Øßá=ÔuÙgÚ=ã+;oÒQÓßç=ã/ܸÖoæ� �-æsÖ¤×�VØ�^�ã�קã/áµÙ1O?Ý;Òo×$ã¸ÙgקÒoá=Ü$æsÖoקÛcã�� Ö¤áCàhÖoÙgÚ Ü$Ø9�=ã/ܪܧÖuÒoÜ¢ÙgÖ6ÖoàVÙ�ÒoØÕá ÒoáCã��IçeÒLÙgØßÖoá�ÙgÚeÒQÙ�Vã�*eá=ã/Ü��Z@!% A�èK,�æøÙ§ã�׳ܧÖoÓ�;OØßá=Ô6æsÖ¤×��Z@!% A�Ý;ÙgÚVã1Ù§×gÒoáVÜ$æsÖ¤×$ÛüÒQÙ§ØßÖ¤á ØÕܪקãC;¤ã�×$ܧã�� Òoá�� ÙgÚVã;QÒoÓÕç=ã�Öoæ � �*ØÕÜcÖoàVÙ�ÒoØÕá=ã��Xè ={ÙcØßÜ1Þh֤ܧÜ$Øßà=ÓÕã�ÙgÖCÙgקÒoá=Ü$æsÖo×§Û Û¸ç=Ó¼ÙgØ�å¿Øßá$�=ãCB ܧã��OçVã�á=ä/ã�ÜØÕáµÙgÖ�Û�ç=ÓÕÙ§Ø�;QÒoקØßÒQÙgã�Ôoã�á=ã/×gÒQÙ§Øßá=Ô æsç=á=ä/Ù§ØßÖ¤áVÜ�èNFeÖ¤×8ÛwÖ¤×$ão�Vã/Ù�ÒQØßÓßÜ8קã�æsã�×8ÙgÖ�Ù§Ú=ã4àhÖ`Ö��càµâgOã��=Ô¤ãC�«Øßä)��Òoá$�TF?ÓßÒ&-$Ö¤ÓÕã/Ù1� ; `e%

�«ã/Ù§Ú=Øßá���Óßã/ÔµÒoÓVÞ=ÒQÙgÚ=ÜUÙ§Ú=ØßÜ]�!Ò¬âhÑUØßáVÜ$Ùgã�Ò��²Öoæ�ä�Ö¤áVܧØ9�Vã�קØÕá=ԳҢܧã��Iç=ã�á=ä/ã�ÖQæ�&WlUÛwØÕá`åÛwÒeB;QÒoÓÕç=ã�Ü/Ýhä/Ö¤á=Ü$Ø9�=ã/×�ÙgÚ=ÒQÙ�Ù§Ú=ã ØßáµÙgã/×s;QÒoÓ;ÙgÖ���Ö¤×s��Ö¤á�ÝhØßá=ؼÙgØ ÒQÓßÓÕâT� ; > OZ%YÝÎØßÜ+קã��=ç=ä/ã��nlÙgØÕÛwã/Ü�Ý8àµâÊã/ØÕÙ§Ú=ã�×1ØßáVä�קã/Ûwã/áµÙgØßáVÔ*ؼÙgÜ1Óßã�æøÙ1ÓßØÕÛwؼÙ@nÛcØßá ;QÒoÓÕç=ã3A¸Ö¤×u�=ã/ä�×$ã�Ûcã�áµÙgØÕá=ÔؼÙgÜ�קØßÔoÚIÙ�ÓßØÕÛwؼÙq@nÛwÒeB/;QÒoÓßç=ã<A�è X�ã�áVä�ãoÝR��ã¸Ú=Ò3;oã1Òüܧã��Iç=ã�á=ä/ã1Öoæ5Øßá=ä/קã/Ûwã/áI٧ܪÒoá���ÒÜ$ã��Iç=ã/á=ä�ã�ÖoæG�=ã/ä�×$ã�Ûcã�áµÙgÜ/Ý'�«Ú=ã�×$ã�ÙgÚ=ãwܧç=Û Öoæ�ÙgÚVã�Ü$Ù§ã�Þ=ܸØÕÜun�è/7 ãüä¬ÒoálØ��=ã�áµÙ§ØÕæøâÙ§Ú=ã6Óßã/ÔµÒoÓ¦ÞeÒQÙgÚ �«Ø¼ÙgÚlÙ§Ú=ã�ÞeÒoØß×�Öoæ+ܧã��OçVã�á=ä/ã�Ü�@nÒoä�ä/Ö¤ç=áµÙgØÕá=ÔCÒoÓÕܧÖ�æsÖ¤×�Ù§Ú=ã�æsÖ¤×$Û Øßá�«ÚVØßä�Ú6ÙgÚ=ã�â6Òo×$ã¢ÛcØ_B`ã��mA�è'={æ���ã Òo×$ã¢ØßáµÙ§ã�קã/Ü$Ù§ã���ØßáüÙ§Ú=ã³ÒoÛcÖ¤ç=áµÙ�Öoæ\�¦Ö¤×s�wÙgÖu�VÖ=Ý$�¦ãä/Ö¤á=Ü$Ø9�=ã/צÙgÚ=ÒQÙ!ÒLæøÙgã�×8ÙgÚ=ãLnwÜ$Ù§ã�Þ=Ü!Òoקão�=Ö¤á=ãQÝ5�¦ã �¦Ö¤× �cØßácÙgØßÛcã«Þ=קÖoÞ�Ö¤×�ÙgØÕÖ¤áeÒoÓ=Ù§Ö�ÙgÚVãÜ$Ø98/ã ÖQæ(Ù§Ú=ã³ØßáµÙgã/×s;QÒoÓ�ÓÕã/æøÙ¬è gOã�ã�F?ØßÔoç=קã1UVè

; !

Page 15: Optimal Binary Search Trees with Costs Depending on the Access

������������������������������������������������������������ Data interval

Access path

z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z z zx x x x x xx

Increasing accesses Work here Decreasing accesses

wwwwwwwwwww

F(ØßÔ¤ç=×$ãuUVÑ:=¿áµÙgã/קÞ=×$ã/Ù§Øßá=Ô�Óßã/ÔµÒoÓUÞ=ÒQÙgÚ=Ü/è��8ÒoקØßÒoà=ÓÕã�Ü %VÝ\k Òoá��'3 ä�Öoקקã/ܧÞhÖ¤á��CÙgÖ6ÙgÚVã�IçeÒQáIÙ§ØÕÙ§Øßã�Ü!Ù§Öwàhãªä�Öoç=áµÙgã��Xè

��Ú=ã²Ôoã�á=ã/×gÒQÙ§Øßá=ÔüæsçVá=ä/Ù§ØßÖ¤á�Ù§Ö�à�ã²çVܧã��CÚeÒQÜ4ÙgÚ=×$ã�ã(;QÒo×$Ø Òoà=ÓÕã�ÜI%VÝ k'Ý 3�è �'ã�Ù¢ÙgÚVã;QÒo×$Ø ÒoàVÓßã %wä/Ö¤ç=áµÙ4Ù§Ú=ã³ÙgÖoÙgÒoÓ;ܧØ�8�ã Öoæ?Ù§Ú=ã�ÒQק×gÒ¬â @[O\A�Ýfk ä/Ö¤ç=áµÙ4Ù§Ú=ã³ÙgÖoÙgÒoÓ;áIç=Û¸àhã�×+ÖoæÒQä�ä�ã/ܧÜ$ã�Ü @ n�AUÒoá$�!3ÊÙgÚ=ã!Ù§ÖoÙ�ÒoÓVÒoÛcÖ¤ç=áµÙ�Öoæm�¦Ö¤× �ÎèD�¢ç=×UÔ¤ã/á=ã�קÒQÙgØÕá=Ô¢æsç=á=ä�ÙgØÕÖ¤á²ØßÜUÙ§ÚOçVÜ

�+@ % > k > 3:A r �� � � � � � �� � � � � � %

� k � 3 �

Ü$ç=ä�Ú�ÙgÚeÒQÙ«ØÕáuÒoá�ÒoקקҬâ6ÖoæpO ã�ÓÕã�Ûcã�áµÙgÜ�ÙgÚVã�קã Òo×$ã�� � � � � � �=Ø_^Xã/קã/áIÙ«ÓÕã�ÔµÒQÓ�ÞeÒQÙ§Ú=Ü�Öoæ'nÜ�Ùgã/Þ=ÜY�«ÚVØßä�ÚuÓßã¬ÒW��Ù§ÖcÒoá.ØÕáµÙgã�× ;QÒoÓ�Öoæ(ܧØ�8�ã��@[�«ÚVØßä�Úuä�Ö¤Ü�ÙgÜoM�@��A A�è�GÖ+�Qã�ã/Þ-ä�Öoç=áµÙ�ÖQæ(Ù§Ú=ã³Ü§Ø98/ã³Öoæ(Ù§Ú=ã ÒoקקҬâ @nØÕá %�A«ÒQá��uÙ§Ú=ã³áIç=Û¸àhã�׫Öoæ(Ü$Ùgã/Þ=Ü @nØßá

kRAªÒQٳ٧Ú=ã1ÜgÒoÛcã¸ÙgØÕÛwãQÝ ��ãcä�Ö¤áVܧØ9�Vã�תÙgÚ=ãcáIç=Û¸àhã�׳Öoæ¦ã�ÓÕã�Ûcã�áµÙgÜ�$Üs�OØÕÞ=Þhã�� �uØßá ÙgÚVãä/Ö¤á=Ü$ã�ä�ç`ÙgØ�;oã�ØÕá=ä�×$ã�Ûcã�áµÙgÜY@sܧã/ãoF(ØßÔ¤ç=×$ã�U A�è', ܧØÕá=Ô¤Óßã�Øßá=ä/קã¬ÒQܧØßáVÔªÜ$Ùgã/ÞwØÕÜUקã/Þ=קã/ܧã/áIÙ§ã��àµâ�Ù§Ú=ãªæsç=á=ä�ÙgØßÖoá

�R@!% > kRA rk�%; ' % r k�% � k�% d � k�% Q � ?@?@?

; #

Page 16: Optimal Binary Search Trees with Costs Depending on the Access

Ù§ÚeÒQÙ�ØßÜ�ÝOÖ¤á=ã¢Òoä�ä/ã�ܧÜ�ØÕÜ�Þhã�×�æs֤קÛcã���@ kRA¦ÒQæøÙ§ã�×¦Ü �IØßÞ=ÞVØßá=Ô¸Ö3;oã�×!Ö¤áVã¢Ö¤×�ÛcÖ¤×$ã�ã/Óßã�Ûcã�áµÙ§ÜÖQæ?ÙgÚVã¸Òo×$×gÒ¬â @ %��­Ü)A�è���Ú=ã�×$ã�ØÕÜ4ÒQÙ+ÓÕã¬ÒoÜ�Ù4Ö¤áVã�ã/Óßã�Ûcã�áµÙ�Ým�«ÚVØßä�Ú-ØÕÜ+Ù§Ú=ã�ÒoקקÒ�â�ã/Óßã/Ûwã/áIÙä/Ö¤ÛcÞeÒoקã���è�, ܧã��OçVã�á=ä/ã�Öoæ]8�ã/קÖcÖ¤×�ÛwÖoקãªØßáVä�קã�ÒoܧØÕá=ÔcÒoä�ä/ã�Ü$ܧã�Ü�ØßÜ�×$ã�Þ=×$ã�ܧã/áµÙgã��-àIâ

� � @ % > kRA r;

; ' � @!% > kRAr ; ���R@!% > kRA ���R@ % > kRA d ���R@ % > kRA Q � ?@?�?

ÒQá��6ÙgÚ=ã³ÜgÒQÛwãªæsÖ¤×$Û¸ç=Ó ÒQÜ�Ú=Ö¤Ó��6æsÖ¤×���@ % > kRANr �R@ % > kRA�Òoá$��� �3@ % > kRAhr � �&@!% > kRA�è ,Ü$ã��Iç=ã/á=ä�ã�Öoæ?ØÕáµÙgã�×$ÛwØÕá=Ô¤ÓÕã��6ØßáVä�קã�ÒoܧØÕá=Ô1Òoá��/�=ã/ä�קã�ÒoܧØÕá=ÔwÒoä�ä/ã�ܧÜ$ã�Ü�ä�Ö¤×$קã�Ü$Þ�Öoá��=Ü«ÙgÖ

��� � @ % > kRA r;

; ' @ �R@ % > kRA ����@ % > kRA Ar ;

; ' d��� ÒQá��üÙgÚVã *eáeÒoÓhܧã��Iç=ã�á=ä/ã³Öoæ;ã�ÓÕã�Ûcã�áµÙgÜ�Öoæ�ÙgÚVã¢Ü§ã�Ù6�«Ú=ã/קãL�¦ã¢ÚeÒ<;¤ã4Ù§Ö �¦Ö¤× �cØßܦקã�ÞVקã�åÜ$ã�áµÙgã��-àµâ

;; ' 3 % r ; � 3-%I��3 d % d ��3 Q % Q � ?�?@?

@ �«Ú=ã�×$ãu��ã²ä/Ö¤ç=áµÙ³Ö¤á=ã²ç=áVØÕÙªÖoæN�¦Ö¤× �.Øßá$3 Òoá��CÖ¤á=ã²ã/Óßã�Ûcã�áµÙªÖQæ8Ù§Ú=ã1Òo×$×gÒ¬â-ØÕá:% A�è�¢á�ÙgÚ=ã³ÖoÙ§Ú=ã�׫ÚeÒQá���ÝÎÒ1ܧã��Iç=ã/á=ä�ã�ÖoæUã/Óßã/Ûwã/áIÙ§Ü��«Ú=ã�×$ã��¦ãq�VÖcáVÖoÙ+ÚeÒ<;¤ã³ÙgÖK��Ö¤×s��ØßÜÜ$ØßÛcÞ=ÓÕâ ;�� @ ; '5% ANr ; � %I� % d � ?�?@? è7 ãcÒoקã²Ü�ÙgØßÓÕÓ(ÛcØßÜ$ܧØÕá=Ô6ܧ֤Ûcã¸àhÖ¤× �Vã�תä�Öoá��=ØÕÙ§ØßÖ¤áVÜ�è ={æ �¦ãwÒQקã²ØßáµÙ§ã�קã/Ü$Ù§ã��*Øßá�ÙgÚVã

Ù§ÖoÙ�ÒQÓ�áIç=Û¸àhã�׫Öoæ?Òoä�ä/ã�ܧÜ+ÞeÒQÙ§Ú=Ü«ÙgÚeÒQÙ«Ü�Ù�Òo×�ÙG�«ØÕÙgÚ6Ù§Ú=ã³ä�Ö¤ÛcÞ=Óßã�Ùgã³Òo×$×gÒ¬â6ÒQá��.ã/á��uç=ÞÒLÙ�Ò4Ô¤Ø_;¤ã/á/@�� >�� A'ØßáµÙgã/×s;QÒoÓ @nØ�è�ãQè?ØßáVä�å �Vã�ä�Öo× �=ã/קØßáVÔ¤Ü)A�ÝoÙgÚ=ã/á(��ã�ÚeÒ<;¤ã«ÒoÓÕÓOÙ§Ú=ã�ã/Óßã�Ûcã�áµÙ§ÜÙ§Ö1ãCB`Þ=קã/ܧÜ+ÙgÚ=ã:*eáeÒQÓ�æs֤ק۸çVÓ ÒVÝ5�«Ú=Øßä�ÚuØßÜ

���&@ % > k > 3:A r ;; ' d���

;; '/3-%

�«ÚVØßä�Ú�ä/Ö¤ç=áµÙgÜ4ÒwáIç=Û¸àhã�×+Öoæ�ØÕá=ä�×$ã¬ÒoÜ$Øßá=ÔcÖ¤×Y�=ã�ä/קã¬ÒQܧØßáVÔüÜ$Ù§ã�Þ=Ü4Þ=Óßç=Ü�Ò�*=áeÒoÓ'ä�ã/áIÙ§×gÒoÓÜ$ã�Ô¤Ûcã�áµÙ�èDg`ØÕá=ä�ã1�¦ã�Ü$ç=Û %��­Ü4ÒoÓÕÖ¤á=ÔcÒoÓÕÓXÙgÚ=ØÕÜ�Þ=קÖOä�ã/ܧÜ/ÝZ�¦ã�Ú=Ò3;oã�ØÕá %cÙgÚVã�ÓÕã�á=ÔoÙ§Ú�ÖoæÙ§Ú=ãü×$ã�Ü$ç=ÓÕÙ§Øßá=Ô-ÒoקקÒ�âoèt7 ã6Ò����lÒoá k Þhã�×�Ü�Ùgã/Þ Ü§ÖT�¦ã�ÚeÒ<;¤ã6ØÕá k Ù§Ú=ã�áIç=Û¸àhã�×�ÖoæÜ�Ùgã/Þ=Ü�è/F?ØÕáeÒoÓßÓ¼â¤Ý �¦ãüÚ=Ò3;oãüØÕá 3 ÙgÚVãüܧØ�8�ãcÖoæ�Ù§Ú=ãK*eáeÒoÓ5ܧã/Ô¤Ûcã�áµÙ¬èI,!Ù ÙgÚ=ãwã�á��XÝ]�¦ãÜ$ã�ÓÕã�ä/Ù�ÙgÚ=Öoܧã�ÞVקÖOä�ã�Ü$ܧã/ÜL�«Ú=Øßä�Ú-Ù§ç=קá-Ö¤çVÙ+ÙgÖ�ÚeÒ<;oã(O ã/Óßã/Ûwã/áIÙ§Üu@!% � A�Ý n.Ü�Ùgã/Þ=ÜK@[k � A�ÝÒQá��.ÓÕã¬Ò��6Ù§ÖwÒQá.ÒQק×gÒ¬â6ÖQæ?Ü$Ø98�ã� � ' �� �� ; @�3�� � � ��� A�èX+Ö&�¦ã�;oã�×/Ý`ÙgÚVØßÜ�ØßÜ?á=ÖoÙ�ÙgÚVã+ä/֤ק×$ã�ä�Ù8æsÖoק۸ç=ÓßÒ4ØÕæm�¦ã+Òoקã�ØÕáIÙ§ã�×$ã�Ü$Ù§ã��cØßá²ÙgÚVã!ÙgØßÛcã!Ö¤×

Ü$ÞeÒoä/ã�ä�Ö¤ÛcÞ=ÓßãSB`ØÕÙ¿â¤èp��Ú=ã�×$ã¬ÒoÜ$Ö¤á²ØßÜ?Ù§ÚeÒQÙ]��ã�ÚeÒ<;oã«Ù§Ö¢ä�ÖoÛwÞ=ç`Ùgã�Ù§Ú=ã�ÒoàhÖ3;¤ã�Ûcã¬ÒoÜ$ç=קã/ÜáVÖoÙ!Ö¤áVÓÕâwØÕæ �¦ãªÜ$ÙgÒo×$Ùh�«ØÕÙgÚ�Ù§Ú=ã¢Ö¤×$ØßÔ¤ØÕáeÒoÓÎÒo×$×gÒ¬â¤Ý`à=çVÙ«ÒQÓßܧÖ�æsÖ¤×!ÒoáµâwÞ�ÖoܧܧØÕà=Óßã�֤קØÕÔ¤Øßá=ÒoÓÜ$ç=à=ØÕáIÙ§ã�× ;oÒQÓYè

; �

Page 17: Optimal Binary Search Trees with Costs Depending on the Access

��Ú=ã/קãwÒoקã²Ù �¦Ö-ØÕÛwÞhÖ¤×$ÙgÒoáµÙ¢ä�Òoܧã/Ü�Ú=ã/קãoè�F?ØÕקÜ�Ù¬Ý'ØÕæ¦Òoá*ØßáµÙgã/×s;QÒoÓUÚ=ÒoÜ�ØÕá=ä�×$ã¬ÒoÜ$Øßá=ÔÒQá��c�=ã/ä�×$ã¬ÒoÜ$Øßá=Ô�ä�Ö¤ÛcÞ�Öoá=ã�áµÙgÜ/ÝOÙ§Ú=ã�á���ãY�=Ö�á=ÖoÙ8ÚeÒ<;¤ã+ÙgÖ Þ�ã/×$æsÖ¤×$Û Ò��=Ø_^Xã/קã/áIÙ¦ä�ÖoÛ1åÞVçVÙ�ÒQÙ§ØßÖ¤á1æsÖ¤×8ÒoÓÕÓ=ÙgÚ=ã�Þ�Ö¤Ü$ܧØÕà=Óßã«Ö¤×$ØßÔ¤ØÕáeÒoÓ=Ü$ç=à=ØßáµÙ§ã�×s;QÒoÓÕÜ�è�FeÖ¤×5ØÕá=Ü$ÙgÒoá=ä�ãQÝVÜ$ç=Þ=Þh֤ܧã+ÙgÚeÒQÙOTr ;32�2 ÒQá�� n+rb``è ��Ú=ã Óßã�Ô¤ÒoÓ�ÞeÒQÙ§Ú.ÔoØ�;¤ã/á.àµâ �V`�#`Ý #�#e%�æsÖo×+ãSBVÒoÛwÞVÓßãoÝ`ÙgÚeÒQÙ«âOØßã/Ó9�=ÜÙ§Ú=ã1ܧç=àVØßáµÙgã/×s;QÒoÓY�V` � Ý #W!�%UÙ§Ö/�¦Ö¤× �-Ö¤á �VÖ`ã/Ü áVÖoÙ1�=ã�Þhã�á$� Ö¤áCÙgÚ=ã1Ö¤×$ØßÔ¤ØÕáeÒoÓGØßáµÙgã/×s;QÒoÓ� ; Ý ;32�2 %�è'��Ú=ão*eáeÒoÓhܧç=àVØßáµÙgã/×s;QÒoÓ��V` � Ý #W!�%m�¦Ö¤ç=Ó��6á=ÖoÙ¦á=ã�ã���Ù§Ö�àhã¢×§ã/ä�Ö¤ÛcÞ=çVÙ§ã���ؼæ�ÙgÚVãÖoקØßÔoØßáeÒoÓ¦ØßáµÙgã/×s;QÒoÓ6��ÒoÜT� ;<2 Ý j 2 %«Øßá=Ü�Ùgã�Ò���è ={æ�Ý�Ö¤á ÙgÚVãuÖQÙgÚ=ã/×cÚ=Òoá���ݦà�ÖoÙ§ÚAÒQä�ä�ã/ܧÜ$ã�ÜÒLÙ:`�#cÒoá�� #�#wÒo×$ã�ØÕá=ä�×$ã¬ÒoÜ$Øßá=ÔcÙgÚ=ã/á-ÙgÚ=ã�*eáeÒoÓ'Ü$ç=à=ØßáµÙ§ã�×s;QÒoÓGØßÜ � # � Ý ;32�2 %�ÝZ�«ÚVØßä�Ú�ä/ã�×�åÙgÒoØßáVÓÕât�=ã�Þhã�á��VÜ�Ö¤áCÙgÚ=ã1ØÕá=ØÕÙ§Ø ÒoÓGØßáµÙgã/×s;QÒoÓY� ; Ý ;32�2 %�è�X�ã�áVä�ãoÝp��ãcÛ¸ç=Ü�٠ܧç=Û Ö3;¤ã/×�ÒQÓßÓÓÕã�ÔµÒQÓXÞeÒQÙ§Ú=ÜD�«ØÕÙ§Ú�á=Ö1קã�Ô¤Òo× ��Ù§Ö1Ù§Ú=ãªØßáVØÕÙgØßÒoÓhܧç=à=ØÕáµÙgã�× ;QÒoÓßÜ/Ý=ãCB`ä�ã/ÞVÙ«æsÖ¤×!ÙgÚV֤ܧãL�«Ú=ØÕä�ÚÚ=Ò3;oã�Öoá=ÓÕâüØßá=ä/קã¬ÒQܧØßáVÔcÖo×�Ö¤á=ÓÕâc�=ã�ä/קã�ÒoܧØÕá=Ôwä/Ö¤ÛcÞ�Ö¤áVã�áµÙgÜ/è7 ã+Òoקã�á=Ö3�Êקã�Ò��Vâ¸Ù§ÖªÜ$Ù�ÒLÙgã�ÙgÚ=ã�Ôoã�á=ã/×gÒoÓ=æsÖ¤×$Û¸ç=ÓßÒ�æsÖ¤×?Ù§Ú=ã�ä�Ö¤ÛcÞ=ÓÕãCB`ØÕÙ§Øßã�Ü/è�g`ØÕá=ä�ã

�¦ã1Òo×$ã(�=ØßÜ$קã/ÔµÒo× �VØßá=ÔüÙ§Ú=ã²ØßáVØÕÙgØßÒoÓ'Òoá�� *=áeÒoÓUã/á��=ܪÖoæ�Ù§Ú=ã1ÒoקקҬâ¤Ý �¦ã²×§ã/Þ=קã/ܧã�áµÙ³ÙgÚVãÜ$ã��Iç=ã/á=ä�ã ÖoæªÒoä�ä/ã�ܧÜ$ã�Ü -$ç=Ü�Ù�àµâ�� � �3@ % > kRA�èbX+Ö3��ãC;¤ã�×/Ý+æsÖo×cÙ§Ú=ã-ä�Òoܧã�ÖQæªÖ¤á=Ó¼â Øßá`åä/קã�ÒoܧØÕá=Ô�Öo×��=ã�ä/קã¬ÒQܧØßáVÔ�ã�ÓÕã�Ûcã�áµÙgÜ��¦ã�Ú=Ò3;oã+٧ֳܧç=àVÙ§×gÒoä�Ùh�«Ú=ÒQÙN��ã+ÚeÒ<;¤ã�Ò����=ã���Òoá$�×$ã�Þ=ÓßÒoä�ãcØÕÙ³àµâ Ò6æs֤ק۸çVÓ Ò�ÙgÚeÒLÙ�ÒQÓßÓßÖ3�«ÜªÙgÖuä�Öoá=ܧØ��=ã�×�ÒoÓßÓUÙ§Ú=ãcÞ�Ö¤Ü$ܧØÕà=Óßã1ØßáVØÕÙgØßÒoÓ?×$ØßÔ¤ÚµÙãSBOÙgקã/Ûwã/Ü/@sæsÖ¤× �?A�Òoá�� ÒQÓßÓ8Þ�Ö¤Ü$ܧØÕà=ÓßãwØßá=ؼÙgØ ÒQÓ�Óßã/æøÙ�ãCBOÙg×$ã�Ûcã�Ü/@øæsÖ¤× �IA�è�=¿álÙgÚ=ãüä¬ÒoÜ$ãÖQæ�Øßá=ä/קã/Ûwã/áIÙ§Ü�@øÙgÚ=ã+�=ã�ä/קã/Ûwã/áI٧ܸÒo×$ãwÜ$ØßÛcØßÓßÒo×)A�Ý�ÙgÚ=ØÕÜ�ØÕÜ ÖoàVÙ�ÒoØÕá=ã�� àµâ Ü$ç=àVÙ§×gÒoä�ÙgØßáVÔ� �3@!% > kRA8æs×$Ö¤Û � � �3@ % > kRA�Òoá��üÙ§Ú=ã�áuÒ��$�=Øßá=Ô � �&@ % > kRA � @ ; ':% A�Ý=ܧØÕá=ä�ã4Ù§Ú=ØßÜ�ÒoÓßÓÕÖ3�«Ü8Ù§ÖÒW���uÒoá�ÒoקàVØÕÙgקÒo×$âwáIç=Û¸àhã�×�Öoæ %��­Ü�ÙgÖ²ÙgÚVãª×§ØßÔoÚIÙ�Ý=Òoä/ä�Ö¤çVáIÙ§Øßá=Ô¸æsÖo×�ÒoÓßÓ�Þ�ÖoܧܧØÕà=Óßã4Þ�Ö¤Ü$ؼåÙ§ØßÖ¤áVÜ!Öoæ;ÙgÚVãªÜ§ã��Iç=ã/á=ä�ã ØßáVܧØ9�Vã�ÙgÚVã³ÒoקקÒ�âoèNF?Øßá=ÒoÓßÓ¼â¤ÝOÒQæøÙgã/×�Ҹܧã��Iç=ã�á=ä/ã�ÖQæ(ØÕá=ä�×$ã¬ÒoÜ$Øßá=ÔÒQá��c�=ã/ä�×$ã¬ÒoÜ$Øßá=Ô�Ü$Ùgã/Þ=Ü�Ý`ÙgÚ=ã/קã+ØßܦÒ�*eáeÒQÓhä/ã�áµÙgקÒoÓhܧã�ÔoÛwã/áIÙ¦Ö¤á��«Ú=Øßä�Úc�¦ão�¦Ö¤×s�hè���ÚVãæsÖoק۸ç=ÓßÒ¸ØßÜ�c@!% > k > 3LA r � ��� � @[k > &$A ' � � @ % > kRA ��� � @ % > kRA ;

; ' % ' � � @ % > kRA ���� � @ % > kRA

;; '5%�� ;

; '/3-%�«ÚVØßä�ÚuØßÜ�ã��IçeÒQÓ'Ù§Ö

�+@ % > k > 3:A r � ;; ' d���

� `�% � @ ; ' % A; ' �� �� ;; '/3-%

; #

Page 18: Optimal Binary Search Trees with Costs Depending on the Access

����� �������� ����������������GÖ*ä�Ö¤ç=áµÙ1ÙgÚVã�Ù§ÖoÙ�ÒQÓ�ÒoÛcÖ¤ç=áµÙ1ÖoæY��Ö¤×s� ÙgÖ��=ÖVÝ �¦ã.ä/Ö¤á=Ü$Ø9�=ã/×1Ù§ÚeÒQÙ1ã�Òoä�Ú �=Ø_^Xã/קã/áIÙÜ$ç=à=ØÕáIÙ§ã�× ;oÒQÓN@�� >�� A¦Öoæ'ÙgÚ=ã³ÒQק×gÒ¬âüקã¬ÒQä�Ú=ã���ÙgÚ=×$Ö¤ç=Ô¤Ú�Ò(�VØ�^�ã�קã/áµÙ«Óßã�Ô¤ÒoÓ�Þ=ÒQÙgÚ�Û¸ç=Ü�Ù«à�ãÞVקÖOä�ã�Ü$ܧã���è:�(ÖüÞ=קÖOä�ã/ܧܪܧçVä�Ú*ØÕáµÙgã�× ;QÒoÓYÝf�¦ã¸Û¸ç=Ü�Ùªä�Ö¤áVܧØ9�Vã�×¢ÒQÓßÓ'ØÕÙ§Ü4Þh֤ܧؼÙgØßÖoá=Ü+æs×$Ö¤Û�+ÙgÖ � Ý?Òoá��lä/Ö¤ÛcÞ=çVÙgãcÙgÚ=ã���ÖoקÜ$Ù�å¿ä�ÒoܧãwÖ¤×�ãSBVÞhã�ä�Ùgã��`å¿ä�Òoܧã6ä/Ö¤Ü$Ù¸ÒQÙ�ã�Òoä�ÚlÞh֤ܧؼÙgØÕÖ¤á�è�GÖ ä�ÖoÛwÞ=ç`Ùgã�Ü$ç=ä�Ú ä�Ö¤Ü�Ù¬Ý'�¦ã6á=ã�ã�� Ù§Ú=ã6ä�ÖoÜ$Ù²Öoæ«Ü$Ö¤Ûcã�ܧç=àVØßáµÙgã/×s;QÒoÓßÜ/è H³Ø_;¤ã/álÙgÚeÒQÙÙ§Ú=Ö¤Ü$ãªÜ§ç=à=ØÕáµÙgã�× ;QÒoÓßÜ�ÒQקãªÒoÓÕקã�Ò��Vâwä�Ö¤ÛcÞ=çVÙ§ã���Ý$�¦ãL�¦Ö¤× �cM�@ � ''� �� ; A8ÙgÖ²Ü$Ö¤Ó�;oã4ÙgÚVãÜ$ç=à=ØÕáIÙ§ã�× ;oÒQÓ1@�� >�� A�Ô¤Ø�;oã�á Ò�Þ=×$ã�;OØßÖoç=ܸÓßã/ÔµÒoÓ¦ÞeÒQÙgÚ ÖQæ�ÓÕã�á=ÔQÙgÚ n�è X+ã�á=ä/ãoÝN�«ÚeÒQÙu�¦ãÚ=Ò3;oã¸ÙgÖ6ä/Ö¤ÛwÞVçVÙgã¸ØÕÜ�Ù§Ú=ã²Ü§ç=Û Öoæ � ' � @� ; æsÖ¤×4ÒoÓßÓ � � � æs֤עÒQÓßÓGÓßã�Ô¤ÒoÓ(Þ=ÒQÙgÚ=Ü4ÖoæÓÕã�á=ÔQÙgÚtnI�«ÚVØßä�ÚuÓßã¬ÒW��Ù§Ö²ÙgÚ=ã³Ü§çVà=ØßáµÙgã/×s;QÒoÓ @�� >�� A�è��Ú=ã/קã�æs֤קãªÙgÚVã¢ÙgÖoÙgÒoÓ�ÒoÛcÖ¤ç=áµÙ�ÖQæ]�¦Ö¤× �wØßÜ�Ù§Ú=ã³ä�ÖOã��cä�ØÕã�áµÙ«Öoæ % � k � Øßá�ÙgÚVã¢æsç=á=ä�å

Ù§ØßÖ¤á#(@!% > kRA r � �

� 3@ % > k > ; A r �� � � � � � �

� � � � � � � %� k �

��ÚVØßÜ�ØÕÜ�ä/֤ק×$ã�ä/Ù�ÝVÜ$Øßá=ä/ã � � � � � � � ØÕܦÙgÚVã4ÙgÖoÙgÒoÓhÒoÛcÖ¤ç=áµÙ!Öoæ\�¦Ö¤×s�cÙ§Ö(�=Ö¸Ö¤á�Òoá6Òo×$×gÒ¬âcÖoæÜ$Ø98/ã�OCÒQá��.ÓÕã�ÔµÒQÓ�ÞeÒQÙ§Ú=Ü«Öoæ?ÓÕã�á=ÔQÙgÚtn�è7 ã:�=ã�×$Ø�;oã¢ÙgÚ=ã³ÒoàhÖ3;¤ãªæsÖ¤×$Û¸ç=Ó Ò1�«ØÕÙ§Ú6קã�Ü$Þ�ã/ä/Ù«ÙgÖ 3 Òoá���ã�;QÒoÓÕçeÒQÙgã4ØÕÙ�ÒLÙ 3 r ; Ý

Ù§Ö1Ö¤àVÙ�ÒQØßá# @ % > kRA r

%@ ; '5% A d � ;

; ' d��� � `�% � @ ; '5% A; ' �� �

�GÖc*eá���Ù§Ú=ã�ä/Ö`ã��cä�Øßã/áµÙ¢ÙgÚeÒLÙ¢ä�Öoקקã/ܧÞhÖ¤á��=Ü�ÙgÖck ��Øßá # @ % > kRA�Ý�á=ÖoÙgØÕä�ã³ÙgÚeÒLÙ4ÙgÚVãä/Ö`ã��cä�Øßã/áµÙ+æsÖo× ;�� @ ; ' ��kRA!ØßÜ �L�QèhX+ã�á=ä/ã# � @ % A r

%@ ; '5% A d � ` � % �

@ ; '5% A � �`�% �����

@ ; '5% A ����� �ÒQá���ÙgÖ¸ÖoàVÙ�ÒoØÕáwÙ§Ú=ã¢ä�ÖOã��cä/Øßã�áµÙ�Ù§ÚeÒQÙ!ä/֤ק×$ã�Ü$Þ�Ö¤á$�=Ü!ÙgÖN% � Øßá$# � @ % A�Ý=á=ÖoÙ§Øßä�ã+ÙgÚeÒLÙ�ÙgÚVãä/Ö`ã��cä�Øßã/áµÙ�Öoæ ;�� @ ; ':% A 6 ��� ØßÜ! � � 66#" Ý=Òoá$�üÙgÚeÒLÙ�ÙgÚVã¢ä�ÖOã��cä�ØÕã�áµÙ�Öoæ<% � ØÕáR%%$'@!% A¦ØßÜÙ§ÚeÒQÙ«Öoæ % � ��� Øßá&$'@!% A�è$��Öoá=ܧã��OçVã�áµÙgÓ¼â¤ÝÎÙgÚ=ãªÙgÖQÙ�ÒoÓ;ÒQÛwÖ¤çVáIÙ«ÖQæ]�¦Ö¤× �6ØÕÜ�ãCBVÒoä�ÙgÓÕâ

# � � � r ` � � On � ; � � ` � On � ` ��«ÚVØßä�Ú�æsÖ¤×8Øßá=Ü�Ù�ÒoáVä�ã¢Ü$Ú=Ö3�«Ü!ÙgÚeÒQÙ¦æsÖ¤×6n+r ; ÙgÚ=ã4ÒoÛwÖoç=áµÙ!Öoæ\�¦Ö¤× �cØßÜD# ��� �1r O Q � U 'O � UVèo�(Ö�ÖoàVÙ�ÒoØÕá ÒwÛcÖ¤×$ã�ã¬ÒQÜ$âuÙgÖ�ÚeÒQá��=Óßã æs֤קÛ�ç=Ó Òu��ã²ÞhÖ¤ØÕáIÙ�Ö¤çVÙ�ÙgÚeÒLÙ-# @ n > O\A�r

; i

Page 19: Optimal Binary Search Trees with Costs Depending on the Access

� @[O ��� dSA�è J.Ö¤×$ã ÞVקã�ä/ØßÜ$ã�ÓÕâoÝ`WO ��� d@ n � `�A�� � # � � � � ` ����� O ��� d

@ n � ; A��ÚVÖ¤Ó9�=Ü«æsÖ¤× 2 � n�� O ' ; èY��Ú=ØßÜ�ä¬Òoá-à�ã�ä�Ú=ã�ä)�Qã��Càµâ-ØÕá��=ç=ä�ÙgØßÖoá-Ö¤á n�èY7 ã�×$ã�ä�ÒoÓßÓÙ§ÚeÒQÙGO � r O�@[O ' ; A�@PO ' `�A ?@?@? @PO ' n � ; A�è0+ÖoÙgØÕä�ãwÙ§ÚeÒQÙ���ãüÚeÒ<;¤ã�ÓÕã/æøÙ�ÒoܧØ��=ãwÙ§Ú=ãüä�Òoܧã�ÖQæ�8�ã/קÖQå{Óßã�áVÔoÙgÚlÜ$ã��Iç=ã/á=ä�ã/Ü�ÝN�«Ú=ã�×$ã

àhÖoÙ§Ú ã�á��=ܪÖQæ8Ù§Ú=ã²ØßáVØÕÙgØßÒoÓ;ܧçVà=ØßáµÙgã/×s;QÒoÓUÛ�ç=Ü$Ùªàhã²ä�Öoá=ܧØ��=ã�×$ã�� @ná=ÖQÙªÖ¤á=Ó¼âuÙ§Ú=ã²×§ØÕÔ¤ÚµÙ$åÛcÖ¤Ü�Ù�Öo×�Óßã/æøÙ§ÛwÖoÜ$ÙSA�è X�ã�áVä�ãoÝÎÙgÚVã�Þ=×$ã�;OØßÖoç=Ü+ÒoáeÒoÓ¼â`Ü$ØßÜG�=ÖOã�Ü«á=ÖoÙ�ÒoÞVÞ=ÓÕâ�Ù§Ö�n+r 2 è =¿áÙ§Ú=ØßÜ�ä�Òoܧã1�¦ã Ú=Ò3;oã

� �e@!% > 3LA�r ;; '5%

;; '/3-%

;; '5%

�«ÚVØßä�ÚuÔ¤Ø�;oã�Ü�Ý #� � �qr ORQ � � � O d � `=� O � UVè

����� ������ �� �#������ ��������� ������ �� ��������������7 ã ä�Öoá=ܧØ��=ã�×�Ü$ÞeÒoä/ã*áVÖ&�³è 7 ã ÚeÒ<;¤ã ÙgÖ Ü�ÙgÖ¤×$ã Ö¤á=ã�ä/ã�ÓßÓ+æsÖ¤×�ã�Òoä�Ú �VØ�^�ã�קã/áµÙ�Òoä�åä/ã�Ü$ܪÞeÒQÙgÚXè1X�ã�áVä�ãoÝ;ØÕá=Ü$Ù§ã¬Ò�� ÖQæ5à�ã/Øßá=Ô�ØÕáµÙgã�×$ã�Ü�Ùgã��CØÕá-ÙgÚ=ã�ܧØ98/ã¸Öoæ5ÙgÚVã *eáeÒoÓ(ä�ã/áIÙ§×gÒoÓÜ$ã�Ô¤Ûcã�áµÙ§Ü�Ýf��ã6-$ç=Ü�Ù+ä�Ö¤ç=áµÙ+ÙgÚ=ã/Øß×�áIç=Û¸àhã�×/è���Ú=ØßÜ«ØÕÜ�ã��Iç=Ø�;QÒoÓÕã�áµÙ«ÙgÖ

� @ % > kRA r �+@[k > % > ; A r �� � � � � � �� � � � � � %

� k �

�«ÚVØßä�ÚuØßÜ� @ % > kRA r

;; '5% � ;

; ' d��� � `�% � @ ; '5% A; ' �� �

�«ÚVØßä�ÚuÔ¤Ø�;oã�Ü� � � � r ` � � O n � � ` � On � ; �

�«ÚVØßä�ÚuØßÜ � @PO ����� A�è Ju֤קã³Þ=×$ã�ä�ØÕܧã/ÓÕâ¤Ý`WO �����@ n � ; A�� � � � � � � ` � O �����

n��ÚVÖ¤Ó9�=Ü!æsÖo× ; � nR� O ' ; è��Ú=ãªÜ$Ø98/ã¢Öoæ;ÙgÚVã¢Øßá=ÞVçVÙ!Þ=×$Ö¤à=ÓÕã�Û ÚeÒoÜ!ãSBVÒoä/Ù§ÓÕâcÙgÚ=ãªÜ§ÒoÛwã�ä�Ö¤ÛcÞ=ÓÕãCB`ØÕÙ¿âoè�FeÖ¤×�ã�Òoä�Ú

ÞhÖ¤Ü$ܧØßàVÓßãªÓßã/ÔµÒoÓ�ÞeÒQÙgÚuÖoæ(Óßã/á=ÔoÙgÚtn6Ö¤×�Óßã/ܧÜ/Ý���ã ÚeÒ<;¤ã�ÒoáuÒoä�ä/ã�Ü$Ü�ä/Ö¤Ü$Ù�è

; j

Page 20: Optimal Binary Search Trees with Costs Depending on the Access

����� ������� � ����� ��� � ���F(ØßáeÒoÓÕÓÕâoÝ$��ã�ä�Ö¤ÛcÞ=çVÙ§ã�ÙgÚVã�ÙgÖQÙ�ÒoÓ'áIç=Û¸àhã�×�Öoæo@�� >�� A¿å¿ØÕá=ä�å �=ã�ä Ö¤×s�=ã�×$Øßá=Ô¤Ü+Øßá-Òoá Òo×$×gÒ¬âÖQæ Ouã�Óßã/Ûwã/áµÙgÜ�è�=¿ácÙgÚ=ØÕܦä�ÒoܧãQÝ`Öoç=צÖoקØßÔoØßáeÒoÓVØßáµÙgã/×s;QÒoÓeÜ$ÙgÒo×$Ù§Ü!ÒQÙ5Ù§Ú=ã4×$Ö`ÖoÙ�ÝIÒoá��wÚ=ã�á=ä/ãÙ§Ú=ã � �e@[k > % > ; A��=ã�*=á=ã���àhã/æsÖoקã ØßÜ�ÒoÞ=Þ=×$Ö¤Þ=קØßÒQÙgãQÝeØßá=Ü�Ùgã�Ò��-Öoæ �c@ k > % > ; A�è=��Ü$Øßá=Ô1ÙgÚVãܧÒoÛcã�Ùgã/ä�Ú=á=Ø �OçVã�Ü«ÒoÜ�ÒQà�Ö3;¤ãQÝ$�¦ã *eá��M � � � Ý5�«Ú=Øßä�Ú�ØÕܦ٧Ú=ã4ÙgÖQÙ�ÒoÓháIç=Û¸àhã�×!Öoæ'ØÕá=ä�å �=ã�äÖo× �=ã/קØßáVÔ¤Ü�Öoæ'n�Ü�Ùgã�ÞVÜ�èX+Ö&�¦ã�;oã�×/Ý=ÙgÚ=ã/קã¢ØÕÜ�Ö¤á=ão*eáeÒoÓhÞ=קÖoà=Óßã/Û.è>7 ÚVã�á��¦ã¢ä�Ö¤áVܧØ9�Vã�קã���ÙgÚ=ã4Óßã�Ô¤ÒoÓÎÞeÒQÙgÚVÜ

ÓÕã¬Ò��VØßá=Ô6ÙgÖ.ã¬Òoä�Úw@�� >�� AªØßáµÙ§ã�×s;QÒoÓ�Ý'ã¬Òoä�ÚlÞ=ÒQÙgÚ �!ÒoÜ�ä�Ö¤çVáIÙ§ã�� Ù �«ØÕä�ãQè/��ÚVãüקã�ÒoܧÖoá ØßÜÙ§ÚeÒQÙ'ÙgÚVã¦ÓßÒoÜ$ÙGä�ÖoÛwÞeÒQקØßÜ$Ö¤á³ä�Ö¤çVÓ9� à�ã¦Ò � � OüÖ¤×GÒ � ��k²ä�Ö¤ÛcÞhÖ¤á=ã�áµÙ(ÖoæVÙ§Ú=ã8ܧã��Iç=ã/á=ä�ãQè��ÚVØßÜD��ÒoÜ«ä�Ö¤×$קã�ä�Ù+Øßá�ÙgÚVãªÞ=קãC;`ØÕÖ¤ç=ܫܧã/ä/Ù§ØßÖ¤á�àhã�ä¬ÒQç=ܧã³àhÖoÙgÚ�ä¬ÒQܧã�Ü«ÓÕã¬Ò��6ÙgÖK�=Ø_^Xã/קã/áIÙ*=áeÒoÓ8ØßáµÙgã/×s;QÒoÓßܳÙgÖt��Ö¤×s�CÖ¤á�è�gOØßá=ä/ã+�¦ã�Òo×$ãüØßáµÙ§ã�קã/Ü$Ù§ã�� Øßá*ÙgÚ=ãüáOçVÛ¸à�ã/×�Öoæ!ÞeÒQÙgÚVÜÚVã�קãQÝ �¦ã(�=Ø�;OØ��=ã�Ù§Ú=ã�ÙgÖQÙ�ÒoÓGàµâ.Ù �¦Ö @nãSBVä/ã�ÞVÙ:�«ÚVã�á n/r 2 A�è ��Ú=ã²×$ã�ܧçVÓÕÙ¬ÝZ;QÒoÓßØ��uæsÖ¤×n � 2 ÝeØßÜ

M � � � r ` � � � O n � r ` � � O��n �

@nÒoá��tM � � �hr ; A�Ý��«Ú=ØÕÓßã¢Ø¼æ]�¦ã Òoקã³á=ÖoÙ«ØÕáµÙgã�×$ã�Ü�Ùgã��.Øßátn�Ý$�¦ã ÚeÒ<;¤ã

M � r���� �M � � � r @ U � � ; A � `

� � �+�� �<����<��� � � �(��� #

7 ãcÚeÒ<;¤ãc�Vã�ܧä/קØÕà�ã��lÒoÓÕԤ֤קؼÙgÚ=ÛcÜ4æsÖ¤×:*eá$�=Øßá=ÔuÖ¤ÞVÙ§ØßÛwÒoÓUà=ØÕáeÒo×�â ܧã�Òoקä�Ú Ù§×§ã/ã�ܳæsÖ¤× ÒÔoØ�;¤ã/á ܧã�Ù 3k ��>@?@?@?�> k��� cÖoæ �Qã/âOÜ:�«Ú=ã�áCÙgÚ=ã²ä/Ö¤Ü$Ù¢Öoæ8ã¬Òoä�Ú��oã�â kml:�=ã/Þ�ã/á��=֤ܳá�ÙgÚVã@ n � ; A '+ÞeÒQÙ§Ú.ÓÕã¬Ò��VØßá=Ô²ÙgÖKkml�è ��Ú=ã�ÞeÒo×gÒQÛwã�Ùgã�×Yn6ØßÜ+Ò1Ô¤Ø�;oã�á.ÒoקàVØÕÙgקÒo×$âüØßáµÙgã/Ô¤ã�×+ØßáÙ§Ú=ã�קÒoá=Ô¤ã ; � n � O?èY��Ú=ã¸Ö¤Þ`ÙgØßÛwÒoÓÕØÕÙ¿âwקã/æsã/קÜ+ÙgÖ6Ò1Ùgקã/ã�ÚeÒ<;OØßáVÔ�ã�ؼÙgÚ=ã/×�ÛcØßá=ØÕÛüÒQÓ�¦Ö¤×$Ü$Ù¦ä¬ÒoÜ$ã4Ö¤×��¦ã�ØßÔoÚIÙ§ã��6Ò<;oã�×gÒQÔ¤ã�ä�Òoܧã�ä�Ö¤Ü�Ù¬è'��ÚVã4ä�ÖoÛwÞ=ÓÕãCB`ØÕÙ¿â¸Öoæ�àhÖoÙgÚwÒoÓÕԤ֤קؼÙgÚ=ÛcÜØÕÜpM�@PO ��� dSA�è]={Ù(ܧÚ=Öoç=Ó9��à�ã8á=ÖoÙ§ã���Ù§ÚeÒQÙ(ÒoÓ¼ÙgÚ=Ö¤çVÔ¤Ú Ù§Ú=ã8ä�Ö¤ÛcÞ=ÓßãSB`ØÕÙ¿âªØÕÜ?Òoá ãCB`ÞhÖ¤á=ã/áIÙ§Ø ÒoÓØÕátn�Ý=ØÕÙ«ØÕÜ�Þ�ÖoÓÕâOá=Ö¤ÛcØ ÒoÓhØßá6Ù§Ú=ã³Øßá=Þ=ç`٫ܧØ98/ãoÝeØÕá�ænÒQä/ÙYM�@[O\A¦Ù§ØßÛcã�Ü!ÙgÚVã ØÕá=Þ=çVÙ«Ü$Ø98/ãoè,�Ü1�¦ãcÞ�Ö¤ØÕáµÙgã��*Ö¤çVÙ:�«Ø¼ÙgÚ*Òoá*ãCBVÒoÛcÞ=Óßã1ÒLÙªÙgÚ=ã1ã�á$� ÖoæDg`ã�ä�ÙgØÕÖ¤á ``Ý;ÙgÚ=ã1ÛcÖ¤á=ÖQå

Ù§Ö¤á=ØÕä�ØÕÙ¿â¸Þ=קØÕá=ä�ØÕÞ=Óßã�Öoæ �ªáOç`ÙgÚ��"UW%Z�=ÖOã�Ü8á=ÖoÙ8Ú=Ö¤Ó��wæsÖ¤×�ÙgÚVã�ä�ÒoܧãLn � 2 è'��Ú=ã/קã/æsÖoקãoÝ`ØÕÙÜ$ã�ã/ÛwÜ]�=Ø �cä�çVÓÕÙGÙgÖ4ØÕÛwÞVקÖ3;¤ã5ÙgÚ=ØÕÜ?ÒQÓßÔ¤Ö¤×$ØÕÙ§Ú=Û.è<�ªá ÙgÚ=ã¦ÖoÙgÚVã�×?Ú=Òoá���ÝoÒoÜ?Ûcã�áµÙgØÕÖ¤á=ã���Øßá

` 2

Page 21: Optimal Binary Search Trees with Costs Depending on the Access

Ù§Ú=ã«ÜgÒoÛcã«Ü§ã/ä/ÙgØÕÖ¤á�ÝIÙgÚ=ã+ÒoÓÕÔ¤Ö¤×$ØÕÙgÚVÛÌä�Òoáüàhã«ãCBOÙgã/á��=ã��+�«ØÕÙgÚVÖ¤çVÙ8Þ=קÖoà=Óßã/ÛwÜUÙ§Ö�ÚeÒQá��=ÓßãÒQÓßܧÖ1ç=áVܧç=ä/ä�ã�Ü$Ü$æsç=ÓGܧã�Òoקä�ÚVã�Ü�è,�á�Ö¤Þhã�á�Þ=ק֤àVÓßã�Û±ØÕÜ;ÙgÖ �Vã�;OØßÜ$ã¦Ô¤ÖOÖ5��Ö¤áOå¿ÓßØÕá=ã5ÒoÞ=ÞVקÖ<B`ØßÛwÒQÙgØÕÖ¤á³ÒoÓßÔo֤קؼÙgÚ=ÛcÜ�Ý\ÒoÜGØßÜ

�VÖ¤á=ã!æsÖ¤×UÙ§Ú=ã«ä¬ÒoÜ$ã nKr ; ØÕá/� ; ; %YÝ��«Ú=ã/קã+ÒªÓßØÕá=ã¬Òo×(ÙgØßÛcã!ÒQÓßÔ¤Ö¤×$ØÕÙ§Ú=Û �«ØÕÙgÚcÒªä�Öoá=Ü$ÙgÒoáµÙÒ<;oã�×gÒQÔ¤ã�ÒQÞ=Þ=קÖ<B`ØßÛwÒQÙ§ØßÖ¤áª×§ÒQÙgØÕÖ+ØÕÜGÒoä�Ú=ØßãC;¤ã���èNJ.ÖoÙ§Ø�;QÒQÙ§ã�� àIâ+� ; ; %�ÝQÒ����=ؼÙgØßÖoáeÒoÓo×$ã�Ü$ç=ÓÕÙ§ÜÖoá�Ù§Ú=ØßÜ«Þ=×$Ö¤à=ÓÕã�Û Ú=Ò3;oã�àhã�ã/á.ÖoàVÙ�ÒoØÕá=ã���×$ã�ä�ã/áµÙgÓÕâ � � Ý #&%Yè

� ��� �:� �:�� ,� #

� ; %�4�è>0�è>H³ØÕÓßàhã�×$Ù ÒQá�� 4�è'F�è]J.ÖOÖ¤×$ãoÝ �8Òo×$Ø ÒoàVÓßã�å{Óßã/á=ÔoÙgÚCà=ØÕáeÒo×�âCã�á=ä/Ö?�=ØÕá=Ô=Ý��-"�&�&� �KG��H" ����"�,�.������� @ ; j #Wj A�Ý`Þ=Þ�èmj�U�U\å j � i`è

�a`e%1�ªè �4è�X+ç1Òoá��(,�è �4è��Gç=ä)�Qã�×�Ý �¢ÞVÙ§ØßÛwÒoÓµä�Ö¤ÛcÞ=çVÙ§ã�×UÜ$ã¬Òo×$ä�Ú¸Ùg×$ã�ã�Ü5ÒQá�� ;QÒoקØßÒoà=ÓÕã�åÓÕã�á=ÔoÚIÙwÒoÓÕÞ=ÚeÒoàhã/Ù§Øßä�ÒoÓ�ä/Ö?�=ã/Ü�Ý ������� 86 � �+����&I64� � ;L; &9� " 0 � ���*.8" �V���!� ,�G � @ ; j�# ; A�Ý=Þ=ÞXèZ# ; !Qå #�U ``è

�VUW% �¸è�4«èm�ªáIçVÙ§Ú�Ý��¢ÞVÙgØÕÛ¸ç=Û�à=ØßáeÒQ×$â�Ü$ã¬Òo×$ä�Úu٧קã/ã�Ü�Ý � ,�� � � �@)@64���V��� � , � @ ; j�# ; A�ÝÞVÞ�è ; !Qå `�#`è

�"!�% �¸è�4�è��ªáIçVÙgÚXÝ��S.8" � �+� 6 ) � 6�� ; � �H"�� � ��6 3�� � �%�N���/3 ����� � ��0L� � "��8� ��& � & �3/64�+����. �²Ýf, ���VØßܧÖoá`å 7 ã�Ü$Óßã/âoÝ��+ã�Ò��=ØÕá=Ô=ÝfJ/,�Ý ; j � iVÝm`Qá��uã��Xè ; j�#�UVè

�a#e% �¸èW4�è��ªáIçVÙgÚXÝ��S.8" � �+� 6 ) � 6�� ; � �H"�� � ��6 3�� � �%�N���/3 � � � 64���!���/32����0 � " ����,�.�����/3oÝf,o���=ØÕܧ֤á`å 7 ã/ܧÓÕã/â¤Ý��«ã¬ÒW�=Øßá=ÔVÝfJt,�Ý ; j�#�UVè

� � %�4�è'g�è �'Òoàhã�×/Ý��³è ��è>J.ØßÓÕØ9�=Ø��ç*Òoá$� ,�èp,�è��(ã�Ü$ܧֵÒ`Ý gOÙgקÒQÙgã/Ô¤Øßã/Ü�æsÖ¤×(g`ã¬Òo×$ä�Ú=ØßáVÔ�«Ø¼ÙgÚ �¢Ø_^Xã/קã/áIÙh,4ä/ä�ã/Ü§Ü ��Ö¤Ü�ÙgÜ/Ý � ��6K,�"�" 0����/34G 6 )I�*.8"�� ����� ��� Ý$g`Þ=×$Øßá=Ôoã�×+�p0 ��g; � !.#@ ; j�j�j A�Ý`ÙgÖcÒoÞ=Þhã¬Òo×�ØÕá �S.8"�64��"��!� , ��& � 6�� ; � � "�� � ,�� "��F,�"�è

� #e%�4�èmghè��'Òoà�ã/×�Ý �³è���èfJuØßÓßØ��=Ø��çwÒoá��,�è?,�è!�Gã�Ü$ܧֵÒVÝ��¢á��ØÕáeÒo×$â�g`ã�Òoקä�Ú=ØÕá=Ôu�«ØÕÙ§Ú0+Ö¤á`åH��á=ؼæsÖ¤×§Û ��Ö¤Ü$Ù§Ü�Ý%� ��6K,�"�" 0����/34G$6 )2�*.8" � �L�*. � �"� � ���#�$�%� �8� � ��& � ��� �; 6KG�� � � 64�'& �(GK,���"��H" � & 3/64�+���*. �2G:@ ` 2�2 ; A�Ý=Þ=Þ�èmi #�#\å i � !=è

�ViW% ��è ��è �'ÒoקÛcÖ¤×$ãoÝ&, ܧç=à��IçeÒ��=קÒQÙgØÕä¦ÒQÓßÔ¤Ö¤×$ØÕÙ§Ú=Û æsÖo×;ä�Ö¤á=Ü�Ùg×$ç=ä/Ù§Øßá=Ô�ÒoÞ=Þ=×$Ö<BVØÕÛüÒLÙgã�Ó¼âÖoÞVÙgØÕÛüÒoÓoà=ØßáeÒQ×$â¢Ü$ã¬Òo×$ä�Ú�٧קã�ã/Ü�Ý( 6 � �+����& 6 ) � & 3/64�+����. �2G) c@ ; j�i�#�A�Ý\Þ=Þ�èW#�#WjLå #�j ; è

` ;

Page 22: Optimal Binary Search Trees with Costs Depending on the Access

�VjW% �4è7�;ã�;oä�Ö¤ÞhÖ¤ç=ÓÕÖ¤Ü�ÝW,�è �;Øßá=ÔµÒQÜ(ÒQá����Vè �³è�g`Òoä)�ÎÝ X�ã/ç=קØÕÜ$ÙgØÕä�Ü'æsÖ¤×'Ö¤ÞVÙ§ØßÛ¸ç=Û�à=ØßáeÒQ×$âÜ$ã¬Òo×$ä�ÚAÙg×$ã�ã/ÜüÒoá$�ÊÛcØßá=ØÕÛ¸ç=Û ��ã/ØßÔ¤ÚµÙ1Ùg×$Ø ÒoáVÔ¤ç=Ó ÒLÙgØßÖoálÞ=קÖoà=Óßã/ÛwÜ/Ý��S.8"�64��"��!� , ��&� 6�� ; � �H"�� � ,�� "��F,�"���� @ ; j�i�j A8Þ=Þ�è ; i ; å ` 2 U`è

� ;32 %qghè �¸èR04ÒQÔµÒo×gÒ3-/ÝF�¢ÞVÙ§ØßÛwÒoÓ'à=Øßá=Òo×$â�Ü$ã¬Òo×$ä�Ú�Ùgקã/ã�Ü/Ý��S.8"�64��"�� � , ��& � 6�� ; � � "�� � ,��.�"��F,�" ( @ ; j�j�#�A�ÝVÞ=Þ�è ; å !�!=è

� ; ; %qH²è�0�Ò3;QÒo×$קÖ=Ý 4�èG�!Òoקàh֤ܧÒVÝ �³èG�!Òoã�8¬ÒLå��¦ÒQÙgã/Ü�ÝY7 è ��ç=áµÙgÖAÒoá�� 0�è��XØ_;OØ Òoá=Ø�Ý�¦ØßáeÒo×�â ܧã¬ÒQקä�Ú=ØÕá=Ô �«ØÕÙ§Úzá=Ö¤á`å{ç=á=ؼæsÖ¤×§Û ä/Ö¤Ü$Ù§Ü�Òoá��zؼÙgÜ�ÒQÞ=Þ=ÓßØÕä¬ÒQÙ§ØßÖ¤áVÜ1Ù§Ö ÙgãSBOÙ×$ã/٧קØßãC;QÒoÓYÝ � & 3/64�+����. �N� , � � @ ` 2�2�2 A�Ý`Þ=Þ�è ; !.#�å ; � j`è

� ; `e% �³è g`ã��=Ôoã��«Øßä)�.Òoá�� �(èRF?Ó Ò3-$Ö¤Óßã�Ù¬Ý � ����&9�KG��(GV6 ) � & 3/64�+����. �2G�ÝZ,o���=ØÕܧ֤á`å 7 ã/ܧÓÕã/â¤Ý�«ã¬ÒW�=Øßá=ÔVÝmJt,�Ý ; j�j � è

`�`