{"entities":{"Q1084868":{"pageid":1095620,"ns":120,"title":"Item:Q1084868","lastrevid":42866817,"modified":"2025-07-15T13:14:25Z","type":"item","id":"Q1084868","labels":{"en":{"language":"en","value":"Almost optimal dynamic 2-3 trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3980504"}},"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":"Q1084868$5CF4FCBC-D1C6-4464-A89A-7716B24ECB13","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c612a326100ccf490ae25dbfa8ebf49d0270a459","datavalue":{"value":{"text":"Almost optimal dynamic 2-3 trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1084868$E417F911-2D94-4073-9425-72D852B9FD67","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"457040236908667e6a3ceded9fe80b5f2ecb47b1","datavalue":{"value":"0606.68059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084868$F18D5075-8171-4091-BE9B-000A5E8DF825","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"198f343b6b10fa6b0f714d4f54adf21eb675689c","datavalue":{"value":"10.1007/BF02943273","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084868$232AA8DC-83F5-4178-93C8-9B2D5BD6170F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a16181c686f326d827fc1d03cf9274cf73818824","datavalue":{"value":{"entity-type":"item","numeric-id":1084867,"id":"Q1084867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084868$573E6E5A-2A26-4E84-8EDA-44D7CE9B04D1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4c3c57bd2a24956e0520aebbb172d094d92623f1","datavalue":{"value":{"entity-type":"item","numeric-id":182337,"id":"Q182337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084868$BA7E6F33-B639-4A2B-B45E-A21A1DA472B7","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":"Q1084868$BD0C7364-2F6E-4962-8AAD-0C8AD1A61217","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0aa68d994bc19c54ee01b39cbdf5fccb27da4693","datavalue":{"value":"This paper presents a principle to create almost optimal dynamical 2-3 trees based on the theory of \\textit{R. Miller}, \\textit{N. Pippenger}, \\textit{A. Rosenberg}, and \\textit{L. Snyder} [SIAM J. Comput. 8, 42-59 (1979; Zbl 0458.05026)], and gives a searching algorithm, an insertion algorithm and a deletion algorithm for these 2-3 trees. Experimental result given in this paper indicates that these 2-3 trees have very good performance at node-visit cost. We discuss asymptotic property of the 2-3 trees as \\(N\\to \\infty\\), and evaluate its approximate height, \\(h=\\log_{2.45}(N+1)\\), where N is the number of nodes of a 2-3 tree. Finally, this paper analyses the time complexities of the algorithms, which are \\(O(\\log_{2.45}(N+1))\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084868$5B6BCC88-C2F2-4336-9CA9-8F36236FA294","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084868$E1CA8D94-91E0-4A34-8852-04CCB9605AE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084868$C296CE85-D42F-4668-B46C-02CA385D7760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084868$13FE1D4E-362D-4A07-852D-AB4B368F981E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c29521af7c49b8ab698d9ed7d5c90b162cd79d3a","datavalue":{"value":"3980504","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084868$C9CEF400-A52A-4D4A-A215-82E4DAD73F4E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62e54a1bb42bf4820ccc4ea99839c03bdefdc11a","datavalue":{"value":"searching algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084868$05B64B43-D516-4798-8719-DFADA9DC3836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2fc34037dc93d4caefc63b584ad652bfe0f3f2a","datavalue":{"value":"insertion algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084868$23BAF6A4-9B28-47E9-9FE3-00FF6B8C15CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"668d9c98b82d243767c30916291b8a960fb287fa","datavalue":{"value":"deletion algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084868$8F8E79AA-5C82-4C9D-9403-45812AA83A7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"298b4fc5753cdecce8f59718277a1935b8530264","datavalue":{"value":"node-visit cost","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084868$CA397837-97B3-48CA-A701-4CB292F14C61","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":"Q1084868$C6B8F95B-459D-4491-885F-3BC45ECB09E6","rank":"normal"}],"P223":[{"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":"Q1084868$DC500644-C97B-4C91-BC36-9758127081B2","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":"Q1084868$96770A57-A965-4BAD-892F-C6B227776933","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf09bd96511964db0c61b9a482c9900ab63e5c4d","datavalue":{"value":{"entity-type":"item","numeric-id":1243733,"id":"Q1243733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084868$DB41C00A-4E07-4D6E-B8C4-274FA4695990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"890ee19f8bfd653a665aab9a5793406f5cf7865b","datavalue":{"value":{"entity-type":"item","numeric-id":5904716,"id":"Q5904716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084868$9DA3EF5B-ED5D-4707-B165-E3D0AF54D018","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"45cdbe0f89bef71cf65dd0ae47db94125ed47158","datavalue":{"value":"https://doi.org/10.1007/bf02943273","type":"string"},"datatype":"url"},"type":"statement","id":"Q1084868$7D4BBB4C-8EFF-4B3B-B919-45F18A6F2792","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"531cf0b104227b22ada1e3290944540500d78387","datavalue":{"value":"W1976145175","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084868$EB987373-4066-4579-A15B-F9A6B905CE1E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32d9ee6994a47dc904350cc2c2736cfa48e38996","datavalue":{"value":{"entity-type":"item","numeric-id":5750392,"id":"Q5750392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1685aebadfb1868cdef8136fa7dcfb0bfe0bd47","datavalue":{"value":{"amount":"+0.91887933","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":"Q1084868$04F9BA88-9A79-4C5D-89C4-4279D0D0D1FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86ba557c678041c4f424d91ba4e71dbbd124e752","datavalue":{"value":{"entity-type":"item","numeric-id":5009598,"id":"Q5009598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afd6347a658ec3047c2150d980254a670805b8c2","datavalue":{"value":{"amount":"+0.9098724","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":"Q1084868$0170F717-9F80-448C-BD29-EB489E2EADAD","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":"b4859112873c88a9b6ffb9b9c7befad94d9b3cbb","datavalue":{"value":{"amount":"+0.8860294","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":"Q1084868$D071F184-1789-480C-A939-E0AEDD246013","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":"295d6660a23a8b1662013e0ba20a3b02230d9037","datavalue":{"value":{"amount":"+0.8853457","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":"Q1084868$4D7C9297-6337-4768-B141-474C83BBE79A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf55c3476ead2e9380b547588a8f99ba73a7e3ce","datavalue":{"value":{"entity-type":"item","numeric-id":4571959,"id":"Q4571959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0940277ea8b8b01cc6a7efdbed5d2ba9b51bb5f2","datavalue":{"value":{"amount":"+0.8757734","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":"Q1084868$8D68462B-4467-42E4-9C82-6561AF155E2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7026978725c344a95021d25c4febbad1cdd20c5","datavalue":{"value":{"entity-type":"item","numeric-id":3459851,"id":"Q3459851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95d10957feded367ff4ddc253be3a4470db14cd7","datavalue":{"value":{"amount":"+0.8739528","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":"Q1084868$80C825AC-5F8F-4C0C-B8AA-864BFEB478A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5db07c845c5acb5b46eba35a9e55d789598c295d","datavalue":{"value":{"entity-type":"item","numeric-id":2268721,"id":"Q2268721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e204e0114f1c0bf1413096d9c2ffd0cac0f5cb7d","datavalue":{"value":{"amount":"+0.8704885","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":"Q1084868$DB21B147-E408-4BCC-A0F8-D565AC145653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d36bb5859106b33e1e73c4d725c335694e73a28","datavalue":{"value":{"entity-type":"item","numeric-id":4213917,"id":"Q4213917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b91378304d0ab35dcdb286cb5dbf248136fc1df8","datavalue":{"value":{"amount":"+0.86967343","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":"Q1084868$6A748702-985B-4A79-8C79-FEF9540466CB","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":"8e79dc54c2274acabc4e1865736328b6ab78a0d1","datavalue":{"value":{"amount":"+0.86419684","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":"Q1084868$9372B930-3190-40B4-BB7E-95F8C9B85CA5","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":"1257e8519577c460ae83ac57d7842a86feb62717","datavalue":{"value":{"amount":"+0.8632808","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":"Q1084868$F95BA0D5-2F53-46A1-B873-307C7D568AA1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1084868","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1084868"}}}}}