{"entities":{"Q1060015":{"pageid":1061863,"ns":120,"title":"Item:Q1060015","lastrevid":66056424,"modified":"2026-04-12T07:14:44Z","type":"item","id":"Q1060015","labels":{"en":{"language":"en","value":"On the average internal path length of m-ary search trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3905857"}},"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":"Q1060015$7497A6DA-6240-4D6A-8565-02FC2E8F093E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1b7ff078d2c6e0414f80bf21416aa26139383b81","datavalue":{"value":{"text":"On the average internal path length of m-ary search trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1060015$CC90911E-E999-4598-84E1-DAC2FDEECD6E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d71901d4cc5d10605feb9e05f10e7d045e0dc80f","datavalue":{"value":"0567.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060015$5C5D400E-E073-47BE-ABF5-369C0E1DAC4F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2aae4b670d77d08a0bf47c5a53e8c2eeb4d7d07f","datavalue":{"value":"10.1007/BF00268078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060015$08D43D52-255C-49FA-BEF6-06442607CBE9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e508b0c07258dc4a6fca786babde4ee9b28d388b","datavalue":{"value":{"entity-type":"item","numeric-id":221998,"id":"Q221998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060015$ABD93645-F61A-41AC-ADF6-37D7EEDC6AA0","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":"Q1060015$1DA3763E-392F-45F1-908D-8AFA62F857A6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1060015$07AC2EF4-62AE-48B9-BCBA-8635509F7715","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1eb3be1f6fbcc8280e9fa5a161f1d89e21188aba","datavalue":{"value":"Consider an m-ary tree constructed from a random permutation of size n. When all permutations are equally likely, the average internal path length, which may be considered as a cost measure for searching the tree, is shown to be \\((n+1)H_ n/(H_ m-1)+cn+O(n^{\\beta})\\), \\(\\beta <1\\), with \\(c=c(m)=-m/(m-1)-(H_ m-1)^{-1}+A_ 1^{(m)}\\), where \\(H_ k\\) is the \\(k^{th}\\) harmonic number and \\(A_ 1^{(m)}\\) is a coefficient obtained by solving a linear system of equations. This result tells us that the average cost of searching unbalanced m-ary trees is essentially the same as that of searching other popular variants of m-ary trees like B-trees and \\(B^+\\)-trees where sophisticated methods are used for balancing.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060015$7ECC6F44-08E3-4386-A08C-890E18F45F22","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060015$FD924B58-2A67-4E64-9B3B-CAAB663730F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060015$297F08A9-5F3F-4EC8-83FB-5B438B8815AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060015$0D9694E0-F822-4408-986F-920FDD8F4C06","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d6654dc8bdb688c82dde41f095b88a94b126191a","datavalue":{"value":"3905857","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060015$5F7B4E5F-7F82-4114-925C-8E5B5DEE960A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e0c7481e3c5c308fc47ea6e648bd33e7ea295f7","datavalue":{"value":"searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060015$87CEF66B-1EB2-416A-8B14-6799964F6076","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc260feb37f1d405315ced1eb20d05288635dcb8","datavalue":{"value":"random insertions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060015$4EE658CB-BF21-492C-BACD-104A5B2B174A","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":"Q1060015$76206447-3E96-4C53-86BB-957B3B5A5476","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c578dfd8206b9efc52813f4c49cdf09dcbe9072d","datavalue":{"value":{"entity-type":"item","numeric-id":4195901,"id":"Q4195901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060015$26ABD632-B516-42D1-8924-233C313D5576","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060015$DC0BD871-0B36-4A3E-9B1B-B4797881500A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b59b9a95c5ede48fa66f5efb685b30e863d99e05","datavalue":{"value":{"entity-type":"item","numeric-id":3948568,"id":"Q3948568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060015$86FF3FCA-860B-4659-B850-BBA523302A68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a59ded045c744d8e2a32d58157cee16c5fd0072","datavalue":{"value":{"entity-type":"item","numeric-id":3853109,"id":"Q3853109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060015$724051BC-F64F-417D-B178-37CC5B025049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15ba7233a6dc38db2dbf1d2ebdfa6d345128ed9a","datavalue":{"value":{"entity-type":"item","numeric-id":1121028,"id":"Q1121028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060015$8903630C-9B52-4ED5-8840-7C180FCCAAB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c345c0991265e117fa33db42d9256d4582ae2e8","datavalue":{"value":{"entity-type":"item","numeric-id":3310623,"id":"Q3310623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060015$C02D55EA-D4A2-4194-9B6D-C392C8C03790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b80ad91f7c5f9af1f26346f182db3f78ab54ce6c","datavalue":{"value":{"entity-type":"item","numeric-id":5725054,"id":"Q5725054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060015$946A4978-B214-4F9A-8E06-34B48F66509F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a90c73bcf65723c5caa489891ceb2b9a228fc41","datavalue":{"value":{"entity-type":"item","numeric-id":4046051,"id":"Q4046051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060015$F1A21ED3-202B-47E2-A703-1E9419BA6559","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7411e4ceb7ad56b5d9b239d6720d6c6ca294e672","datavalue":{"value":"https://doi.org/10.1007/bf00268078","type":"string"},"datatype":"url"},"type":"statement","id":"Q1060015$0997F9E6-863D-4167-A50D-1CDB6FB6ED20","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"72cf84961cfea6ddad11650e321b8959df6bb7f5","datavalue":{"value":"W1971711520","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060015$6DCF0DCB-288B-47D0-971B-95463D088F25","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1512462b18f8a5b4bf93e31a18d1a2c77cf9436","datavalue":{"value":{"entity-type":"item","numeric-id":1108026,"id":"Q1108026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14d26781091201ea65a794bb829751a770491b70","datavalue":{"value":{"amount":"+0.8566078543663025","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":"Q1060015$9DF92DF8-398C-4F60-B369-F1DE97D8510D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02dbf68d6c68b0ef9cfc0a50dc3e4df8329ac5fb","datavalue":{"value":{"entity-type":"item","numeric-id":1952717,"id":"Q1952717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d94a29dd864d3ac575831dadd889780741e258c","datavalue":{"value":{"amount":"+0.8452588319778442","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":"Q1060015$B5FE70D3-B621-4B9A-9513-0EE12E18AF16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc462223cdff784092dfd90e246d2c74b4738834","datavalue":{"value":{"entity-type":"item","numeric-id":3977075,"id":"Q3977075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f76c8ea3f1adee67efc0e771195a9634d4f4bd8c","datavalue":{"value":{"amount":"+0.823576033115387","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":"Q1060015$387190B7-75E3-40C3-90F5-57D095991731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"732d75af76fdb73f27c1d2798e847018507f9985","datavalue":{"value":{"entity-type":"item","numeric-id":5485337,"id":"Q5485337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b208e1264543aa5ad828a633eec4aaa39bea97f","datavalue":{"value":{"amount":"+0.8199807405471802","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":"Q1060015$91326D45-9C9B-434A-9D4C-E3E0B21E5F71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e12df33805dfb20188a8e3f63411e3ad0ec8f99","datavalue":{"value":{"entity-type":"item","numeric-id":4459586,"id":"Q4459586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d2e703246f02339923e43502c1e6e949f3433d0","datavalue":{"value":{"amount":"+0.8089439868927002","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":"Q1060015$6D088981-21BB-41B6-9E0A-BCE46A8570AA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the average internal path length of m-ary search trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_average_internal_path_length_of_m-ary_search_trees"}}}}}