{"entities":{"Q1323348":{"pageid":1334098,"ns":120,"title":"Item:Q1323348","lastrevid":68461953,"modified":"2026-04-12T23:52:14Z","type":"item","id":"Q1323348","labels":{"en":{"language":"en","value":"The optimal binary search tree for Andersson's search algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 567311"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323348$B515FEE8-E213-4AD4-B60A-EE9B30F0275D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"42a034688e6983cce45b9d3c0c85a6b85254fbba","datavalue":{"value":{"text":"The optimal binary search tree for Andersson's search algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1323348$A51A75B1-72B2-4905-91F4-6942EC2945C3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"42a38085cfdc1cab9a5257189ad2349a998c3b6d","datavalue":{"value":"0790.68029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323348$288EA06C-FB65-41DC-A8BC-8CF3D3DB2253","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0e7b09c41ec1ca661118a787f71d2bdbc437d9d4","datavalue":{"value":"10.1007/BF01210592","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323348$38705ED4-2D07-4ADC-8334-2835F667B6CB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b6b1f3912f0b623f935ed673f01288032b1d919","datavalue":{"value":{"entity-type":"item","numeric-id":1323347,"id":"Q1323347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323348$C5F5CA1B-1213-43A2-B027-D9D5C469DECE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323348$E1B912B7-7C4F-43D2-B314-FF5FD4BCB604","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8b439a09488bc2e6cdbf4d00c3a7f90f1bcfc4c1","datavalue":{"value":{"time":"+1994-07-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1323348$CD61B065-CCEE-4068-B8EB-56290B51DBD4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c00f3f1b328401dc58d5aa9cc67cfc6158ae5798","datavalue":{"value":"\\textit{A. Andersson} [Software, Pract. Exper. 21, No. 10, 1125-1128 (1991)] has presented a search algorithm for binary search trees that uses only two-way key comparisons by deferring equality comparisons until the leaves are reached. The use of a different search algorithm means that the optimal tree for the traditional search algorithm, which has been shown to be computable in \\(O(n^ 2)\\) time by \\textit{D. E. Knuth} [Acta Inf. 1, No. 1, 14-25 (1971; Zbl 0233.68010)] is not optimal with respect to of the different search algorithm. This paper shows that the optimal binary search tree for Andersson's search algorithm can be simply computed in \\(O(n\\log n)\\) time using existing algorithms for the special case of zero successful access frequencies, such as the Hu-Tucker algorithm [\\textit{T. C. Hu} and \\textit{A. C. Tucker}, SIAM J. Appl. Math. 21, 514-532 (1971; Zbl 0228.94002)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323348$3025026C-7902-42F9-8824-2C0122A944DF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323348$95623CE9-BC26-492C-826C-E81BB0F08E3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323348$155613AE-446B-4690-BB9F-DE3F7BADC993","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323348$2E1ED129-9BE4-44E5-919D-1B10B17C4FF0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"164838f452fc78abb3da905ce69f1c08139b71ea","datavalue":{"value":"567311","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323348$2442D25C-162D-4BAD-866F-0BC724533586","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea1454aed231ae5b76b54d0991b4ef495c79aea4","datavalue":{"value":"search algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323348$415042F4-3D31-4EC3-A6FF-1171E0949230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e22f3a113575edfbd123e335487b18a37bfe2d4f","datavalue":{"value":"binary search trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323348$0D7A11EB-CD7D-4587-A936-E85687A82684","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323348$0F1319BD-9114-4F6C-9F2B-C75563D3B57C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3f2b8b8a05c5e5e1a73bff13e01a1b382c27155","datavalue":{"value":{"entity-type":"item","numeric-id":5636753,"id":"Q5636753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323348$66ACD74F-6001-4B90-B461-4D3081135962","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4fd2399a3704cf83726a1162abe2d51c058ed2e","datavalue":{"value":{"entity-type":"item","numeric-id":2551314,"id":"Q2551314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323348$41C91EAC-C1F1-4C54-BD87-55234C020BED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323348$05300F82-0F7C-4851-B0EF-B9959B0EB34A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5319dcdef3202bc448128d6f3ff03b2718410a47","datavalue":{"value":{"entity-type":"item","numeric-id":1323348,"id":"Q1323348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323348$D605A81F-ECE8-4EF8-B7A3-7E27D775FC4C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"668e0f4becd6fbbfb0f26651d57d1d55460fa705","datavalue":{"value":{"entity-type":"item","numeric-id":5906917,"id":"Q5906917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7103cffba6255e46e15f03d9f121796e68d18057","datavalue":{"value":{"amount":"+0.92284095","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323348$093440AC-1B7C-4E03-9510-531E539F805C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a630402892a6794f3b83a6c52ff909d5b93dcc4","datavalue":{"value":{"entity-type":"item","numeric-id":5903763,"id":"Q5903763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7103cffba6255e46e15f03d9f121796e68d18057","datavalue":{"value":{"amount":"+0.92284095","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323348$BCC84F32-5754-48AD-A800-D844B3243DBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44d8f614c3b99b88e24ef0ab41842e25327173cc","datavalue":{"value":{"entity-type":"item","numeric-id":293336,"id":"Q293336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f24c347879ca9ab8cd499d286b3929e795482e3a","datavalue":{"value":{"amount":"+0.91256475","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323348$E7DA5F3A-BAAA-4F8B-9950-1DBCA2892321","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6725a7fdf864143886496ec4ee4e2142cd8bf459","datavalue":{"value":{"entity-type":"item","numeric-id":3521940,"id":"Q3521940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f292b52f737de7baa1532d011adf6d816288f6c8","datavalue":{"value":{"amount":"+0.9017729","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323348$8EA83604-51A6-4414-A94C-457788E23622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a84178e872f3d39c7878e150288750af2c9ed239","datavalue":{"value":{"entity-type":"item","numeric-id":633849,"id":"Q633849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f292b52f737de7baa1532d011adf6d816288f6c8","datavalue":{"value":{"amount":"+0.9017729","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323348$E6434A1E-3168-46D2-92E4-A41D822444CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d01582360bfedd8e95c0037f577842fdee90df08","datavalue":{"value":{"entity-type":"item","numeric-id":4268858,"id":"Q4268858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1d7905ceb846e122e9be0404cd488ed552ced2d","datavalue":{"value":{"amount":"+0.8996965","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323348$80F4E75C-2E73-481B-85FD-59797F402040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d981e45b9675d2690a16d6917a42f3445d45f167","datavalue":{"value":{"entity-type":"item","numeric-id":911247,"id":"Q911247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ff5551497daf96a9045b698ba5ff5ef11d86b8c","datavalue":{"value":{"amount":"+0.89855176","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323348$3ED791E9-1FC9-4B92-9345-FBE9F4E33D2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"535fd2d34730d723c7149154f23610943fa7de28","datavalue":{"value":{"entity-type":"item","numeric-id":3644717,"id":"Q3644717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e5abfb9da52bbcdb0fc46309204325d66acd0ea","datavalue":{"value":{"amount":"+0.8970966","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323348$E981E8AD-E595-40DF-B4FA-C6D8797B52AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e47be249aecd75348b392b5d64def697af07c45","datavalue":{"value":{"entity-type":"item","numeric-id":3210893,"id":"Q3210893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c9abeaeb38905fbe616e89ad96187d01dabd3a7","datavalue":{"value":{"amount":"+0.88554466","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323348$01AF8A64-A34F-43CC-A612-DA29FA988996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fea30fe5599e49525ad50d75ad8942eefb6dd6ce","datavalue":{"value":{"entity-type":"item","numeric-id":5443270,"id":"Q5443270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b6c4916d0e6c0a83b5891e9685ca4971d544449","datavalue":{"value":{"amount":"+0.8838494","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1323348$B3629599-AE86-419B-98CC-D437F722A760","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The optimal binary search tree for Andersson's search algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_optimal_binary_search_tree_for_Andersson%27s_search_algorithm"}}}}}