{"entities":{"Q800733":{"pageid":802581,"ns":120,"title":"Item:Q800733","lastrevid":64469187,"modified":"2026-04-11T20:04:51Z","type":"item","id":"Q800733","labels":{"en":{"language":"en","value":"Optimal alphabetic binary tree for a nonregular cost function"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3878375"}},"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":"Q800733$B5ED5B9E-3312-4A09-ABD7-A1C5167B9D97","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c22066f5c4659743405bf4cae78afcef9dcfcbea","datavalue":{"value":{"text":"Optimal alphabetic binary tree for a nonregular cost function","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q800733$984C9952-563E-4E80-9F3D-F0CA84204EE4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"341f1f0ff7a56fe2a4748e011f04eaff63a97575","datavalue":{"value":"0551.68057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800733$2C7FB086-A7C3-4707-85D2-7B2F52A0601A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9f4f776cd31eb0fbbe6b56d3bf9227f9fe59ca59","datavalue":{"value":"10.1016/0166-218X(84)90128-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800733$D44EC328-86F4-4EF8-84F7-8557339D8B7D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"511890414016001f87f67e677ff572f2fd1acbf6","datavalue":{"value":{"entity-type":"item","numeric-id":175515,"id":"Q175515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800733$5D4A079B-CDDD-4B5E-95A2-0A87B897FBAA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800733$7906F9E2-3895-4ACC-AE32-2C06DB7C6D26","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q800733$2F7749AB-C24F-489A-ABB1-67E895E8FBD4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1bff7c3545d0e7949fff14ec3b9742fee016d73d","datavalue":{"value":"A nonregular cost function of a binary tree T is defined by  \\[  f(T)=\\sum_{v\\in T}w(v),  \\]  where \\(w(v)=\\max \\{w(v'),w(v'')\\},\\) if v' and v'' are the sons of v. The following algorithm will construct the optimal alphabetic binary tree with a given weighted terminal node sequence:    1. In the node sequence \\(\\{v_ 1,...,v_ n\\},\\) combine the node \\(v_ i\\) of the smallest weight with its smaller neighbour \\(v_{i-1}\\) (or \\(v_{i+1}),\\) to form a new node \\(v_{(i-1,i)},\\) as the father of \\(v_{i-1}\\) and \\(v_ i;\\)    2. Get a new sequence \\(\\{v_ 1,...,v_{i-2},v_{(i- 1,i)},v_{i+1},...,v_ n\\}\\) of length \\(n-1;\\) 3. Repeat step 1 and 2 on the new sequence, until the sequence becomes of length one.","type":"string"},"datatype":"string"},"type":"statement","id":"Q800733$2A2AFA9A-265B-4CBC-B8B3-148FBED398E8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800733$9D28156A-7B74-4087-B8CF-0076E5BE8D3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800733$45EDDF44-5DE0-4518-B567-79FA9746515D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bd6519b17fdc1d063ac782986abe3bbf983f4671","datavalue":{"value":"3878375","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800733$858E0290-0D5F-4B07-9A4E-E441BFD3490A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80987f63c88cbca67dab72a4ee24f2e7e037ee3a","datavalue":{"value":"cost function of a binary tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q800733$3B3C76FC-A4F8-489F-AA61-998109EB2186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q800733$0B0B7D0F-5A72-4802-B2F6-22EAECC6FBCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"294e8843bdd095b7641e12d92d4657c92d32e94b","datavalue":{"value":"optimal alphabetic binary tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q800733$6B444ED0-1E7E-4209-B435-2B8288AAF24E","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":"Q800733$CD2AFA22-B379-4B0A-9589-7DE90AD95345","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":"Q800733$2C1F7D4F-C5DD-4C86-B7FC-19DBA42D891D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80e1dbec7084a675afce25c49441fb0cdfccefb1","datavalue":{"value":{"entity-type":"item","numeric-id":4199541,"id":"Q4199541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800733$2B253F8B-2335-499E-B8A9-B06254EE8BF5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41e6efde7bd0b9d896933be84791af52d17e55b1","datavalue":{"value":{"entity-type":"item","numeric-id":5636753,"id":"Q5636753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24b2405e8d252013ce57256510ac5b9e30e8ae1b","datavalue":{"value":{"amount":"+0.8347724080085754","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800733$F90B6F10-D3AA-44A2-B92F-5FB15BE1D55E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"259886fe8093e80281c4f59f62b62ebaab042298","datavalue":{"value":{"entity-type":"item","numeric-id":3140420,"id":"Q3140420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35557f54f62ec729ba56f3ad1caa3ed72666905b","datavalue":{"value":{"amount":"+0.8262572288513184","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800733$76CC0998-1957-4BD9-A1DB-449A6B1D999E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0549a2d10453c47c127afb1382fb11a21cbe604a","datavalue":{"value":{"entity-type":"item","numeric-id":2249740,"id":"Q2249740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bc559d932a33c4eff0ecc807bd4c7bdb437eaed","datavalue":{"value":{"amount":"+0.8213069438934326","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800733$148ACC2D-8883-4B81-818F-B199F6289828","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a860b9b44430ffac3ced8c8515fa914f9888154f","datavalue":{"value":{"entity-type":"item","numeric-id":3586484,"id":"Q3586484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eacf7685e82cec423a590390d6b240745600ad9f","datavalue":{"value":{"amount":"+0.820347011089325","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800733$138480AC-DD21-4264-A7E0-D4F378858449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3aa9234cb736a7a208990078f20766cef7f9f18","datavalue":{"value":{"entity-type":"item","numeric-id":4411351,"id":"Q4411351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29d9ec51c44c0b048cc1d6b20da210fb456fe96a","datavalue":{"value":{"amount":"+0.8198068737983704","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q800733$109E2419-6E38-4F07-A129-19B719036C92","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal alphabetic binary tree for a nonregular cost function","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimal_alphabetic_binary_tree_for_a_nonregular_cost_function"}}}}}