{"entities":{"Q3817628":{"pageid":5847534,"ns":120,"title":"Item:Q3817628","lastrevid":110780486,"modified":"2026-11-20T11:04:07Z","type":"item","id":"Q3817628","labels":{"en":{"language":"en","value":"Extremal properties of ?-weighted binary trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4090820"}},"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":"Q3817628$C6FB5FAC-7389-47B3-B4F8-64AE42C8C23B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f8933bda40b7077da66951fc6f57bdb49eb58afd","datavalue":{"value":{"text":"Extremal properties of ?-weighted binary trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3817628$34931DF5-914E-4877-A98D-88BB31BCE526","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9118b7d1a6e86efecb84a02112b2403f29c017be","datavalue":{"value":"0666.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3817628$4ABE0062-3103-4CDE-89E2-305D0874FED0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9ee0e03b5513a959310d2c930bf085601c3deea7","datavalue":{"value":"10.1007/BF01078899","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3817628$ED859F7E-B946-426E-91A1-398B3E082CF7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"01f9de484970fec9fa9ace994416c4a0d2b99ba2","datavalue":{"value":{"entity-type":"item","numeric-id":3817627,"id":"Q3817627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3817628$6B2C65A8-808E-45E2-9036-1DFB14FF51BE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2f2504956ff395a23643134114da7c6c64448d2","datavalue":{"value":{"entity-type":"item","numeric-id":3026191,"id":"Q3026191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3817628$CE081FE7-BC54-444A-BAD7-474408DB9838","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q3817628$04B4B187-42B3-4A78-99B4-B77FD333180E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3817628$63C33564-44F0-41D4-B432-11766ED9F20D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3817628$767434F8-7CF0-4258-9CE1-263519C72A24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3817628$9A440FA9-4A4E-440E-A6E6-670147B56CD1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8ea3d9a565aa10e78d4cca3c714d22351b3aa04e","datavalue":{"value":"4090820","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3817628$5288D76A-3835-44A4-BF72-F9E9F74B5C05","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c694ed18c09fc5ee2d528c74d4246597cc05ff08","datavalue":{"value":"weighted tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q3817628$66826252-6F4A-472E-9F12-8636ECB33E11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9498ea3113132964f8dcacbf8987afb5cd82bc4","datavalue":{"value":"joint file processing","type":"string"},"datatype":"string"},"type":"statement","id":"Q3817628$B88E5F99-90A8-4D2A-B07B-BACB29911733","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7bcb48c25db0908929ba2383247380f87f15321","datavalue":{"value":"binary tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q3817628$0BE482D6-6D71-408A-9339-EF0870CB9F08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b2b81d941ba100b29da60adf4d8f0473b00a5b8","datavalue":{"value":"external path length","type":"string"},"datatype":"string"},"type":"statement","id":"Q3817628$E8D5F334-E4C8-4EF2-8E71-C3D80883F0FB","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":"Q3817628$B57FBEF8-5EF2-47B0-AD7E-71D45E972E35","rank":"normal"}],"P223":[{"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":"Q3817628$EEBB3B6E-E2BA-467A-914C-AE338A2531DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bff4ddfee8dc2442567724fc5e94f78056dc2b","datavalue":{"value":{"entity-type":"item","numeric-id":4044114,"id":"Q4044114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3817628$025C3947-653E-4DB3-8E6B-E83ACF5810BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e4793ba5fcd1dc0b352925df687ef2f2460fd3d","datavalue":{"value":{"entity-type":"item","numeric-id":2264546,"id":"Q2264546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3817628$F2943ABD-64A2-4B44-9BB7-3110FC4C861F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3817628$CDF31A7E-B36F-4548-BD82-E155F8356EDD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1d0043f7948fbd9f70f5d1dedf6d76f9ec1b74b2","datavalue":{"value":"https://doi.org/10.1007/bf01078899","type":"string"},"datatype":"url"},"type":"statement","id":"Q3817628$2B81D209-82D3-4D61-AD46-51D852C08EF2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fb79d17b02fa4742ac3c081d48e4e18586d54c71","datavalue":{"value":"W2066449094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3817628$567DEF7F-939B-42E8-BF8B-CAEFFC2BD762","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f92d6383e56877d16c73c89bdac65711882f17e5","datavalue":{"value":{"entity-type":"item","numeric-id":4735205,"id":"Q4735205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"096066a46c1ddd8f9b1d0a26634fbc8e461704f3","datavalue":{"value":{"amount":"+0.9087902903556824","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":"Q3817628$4C8F0D6A-09B1-41A3-8D71-541AFD88D118","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d4f25b3f9089e35fa3df51f8c81ad16d978e5fe","datavalue":{"value":{"entity-type":"item","numeric-id":3833632,"id":"Q3833632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"902ec1094c6e1c514acdaa23ff4f5c13464dcc59","datavalue":{"value":{"amount":"+0.8280355334281921","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":"Q3817628$AC384F6C-5AEF-48D4-B193-AF6953D88A6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fef1c80d04e58a62d3777e67c5ad713fe3c8eec","datavalue":{"value":{"entity-type":"item","numeric-id":3680759,"id":"Q3680759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"440a2bdc504d2911fda13f936924df1f8e1948e6","datavalue":{"value":{"amount":"+0.8266938924789429","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":"Q3817628$68DD406D-4B64-4D68-ABA8-97ECD39D6F6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d419e2fadb71e4a3aff3d84980af2fd1466fbb3","datavalue":{"value":{"entity-type":"item","numeric-id":3330524,"id":"Q3330524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"531f549ae4eb9d0d1c47acb7872994e083c328d7","datavalue":{"value":{"amount":"+0.8123073577880859","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":"Q3817628$C9CE5700-1DD5-4D0B-825F-DBB9F3931685","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4584e940f399c437ab3a5958dbb7e40fb6c405a3","datavalue":{"value":{"entity-type":"item","numeric-id":3197843,"id":"Q3197843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4213e37c4e3a4e676cabc2e2947622dbda4cfc5f","datavalue":{"value":{"amount":"+0.8101311922073364","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":"Q3817628$8F176902-B075-438F-91D3-7612E591C5EC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8cc983b4d3786ea285019fdf6de1f8957d02fdb5","datavalue":{"value":"A directed binary tree is a directed tree in which the out-degree of any vertex is 0 or 2. Vertices with out-degree equal to 2 are called internal vertices, and those with out-degree equal to 0 are called leaves. The level of a vertex is the length of the path from the root to the vertex. Let \\({\\mathfrak D}_ n\\) be the set of all directed binary trees with \\(n\\geq 1\\) leaves. On the vertices of a tree \\(D_ n\\in {\\mathfrak D}_ n\\) functions \\(\\mu_{\\alpha}\\) and \\(\\sigma '_{\\alpha}\\) are defined recursively: \\(\\mu_{\\alpha}(x)=1\\), if x is a leaf, \\(\\mu_{\\alpha}(x)=\\alpha (\\mu_{\\alpha}(x_ 1)+\\mu_{\\alpha}(x_ 2))\\) otherwise, and \\(\\sigma '_{\\alpha}(x)=\\mu_{\\alpha}(x)\\) if x is a leaf, \\(\\sigma '_{\\alpha}(x)=\\mu_{\\alpha}(x)+\\sigma '_{\\alpha}(x_ 1)+\\sigma '_{\\alpha}(x_ 2)\\) otherwise, where \\(x_ 1\\) and \\(x_ 2\\) are the vertices reached by arcs from x, and \\(\\alpha >0\\). The values of \\(\\mu_{\\alpha}\\) and \\(\\sigma '_{\\alpha}\\) at the root of the tree \\(D_ n\\) are denoted, respectively, by \\(\\mu_{\\alpha}(D_ n)\\) and \\(\\sigma '_{\\alpha}(D_ n)\\). Let \\(\\sigma_{\\alpha}(D_ n)=\\sigma '_{\\alpha}(D_ n)-\\mu_{\\alpha}(D_ n).\\) The weight of an arc entering the vertex x is the value \\(\\mu_{\\alpha}(x)\\), and the \\(\\alpha\\)- weighted external path length of \\(D_ n\\) is the sum of the weights of all the tree arcs. The \\(\\alpha\\)-weighted external path length of a tree \\(D_ n\\) is equal to \\(\\sigma_{\\alpha}(D_ n)\\). The 1-weighted external path length is just the external path length considered in [\\textit{D. E. Knuth}, The art of computer programming. Vol. 1: Functional algorithms (Addison-Wesley, Reading, Mass. 1968; Zbl 0191.179)]. For fixed \\(\\alpha\\), a tree \\(D_ n\\) is said to be optimal in \\({\\mathfrak D}_ n\\) if \\(\\sigma_{\\alpha}(D_ n)\\) is minimal. The author proves the following characterization of optimal trees: For \\(0<\\alpha <0.5\\) an optimal tree is quasilinear; that is, all its internal vertices form a chain. For \\(\\alpha >0.5\\) a tree is optimal in \\({\\mathfrak D}_ n\\) if and only if it is completely balanced; that is, all leaves of the tree are on the maximal level or on the preceding level. For \\(\\alpha =0.5\\) every tree in \\({\\mathfrak D}_ n\\) is optimal. As a corollary the author obtains explicit formulas for the \\(\\alpha\\)- weighted external path length of optimal trees. The author has investigated \\(\\alpha\\)-weighted t-ary trees for any \\(t\\geq 2\\) [Vestn. Beloruss. Gos. Univ. Im. V. I. Lenina, Ser. I 1986, No.2, 55-58 (1986)]. The results are useful for the evaluation of various strategies for the joint processing of files [\\textit{G. A. Dobrushevich} and the author, ibid. 1983, No.1, 37-40 (1983)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q3817628$87A9AFCF-AB32-4207-8719-BFA60D0F3A9B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Extremal properties of ?-weighted binary trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Extremal_properties_of_%3F-weighted_binary_trees"}}}}}