{"entities":{"Q40371":{"pageid":40427,"ns":120,"title":"Item:Q40371","lastrevid":105426359,"modified":"2026-10-09T10:05:14Z","type":"item","id":"Q40371","labels":{"en":{"language":"en","value":"Root Balanced Tree"}},"descriptions":{"en":{"language":"en","value":"AFP entry Root_Balanced_Tree"}},"aliases":{},"claims":{"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"b09b17a319b3197ec59af5556a8360da8455e856","datavalue":{"value":"28657","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40371$B8092C8E-C522-4F86-BF76-B442538B2929","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$C0DADFC5-D433-4F45-B947-15C0B85EA849","rank":"normal"}],"P29":[{"mainsnak":{"snaktype":"value","property":"P29","hash":"7ef8ffc6d22dd777594eb8f3c68d7f91914d982b","datavalue":{"value":"https://www.isa-afp.org/entries/Root_Balanced_Tree.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q40371$B0FF479A-061D-4277-A061-6FED3380CA7C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd3cd3c8cd085ac2048034c2279872658062342d","datavalue":{"value":"11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40371$6FEEC7F2-64F8-47BA-AB33-1A8AB1E3D5D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"acf10290b955a69659a681d98822944f91bbad9e","datavalue":{"value":"68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40371$B4810911-F203-4301-85AD-952A6CAC6913","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f5e0c6033338f59ef27e37d6877da0f26d9646","datavalue":{"value":"68.0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40371$9A2F2278-2221-4A31-84C7-29F0C4F98B94","rank":"normal"}],"P1458":[{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bb05cb23794774f62a8e4aa4de610af231973a1d","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$18AB3B55-B7FC-4691-9D58-252A0BF52691","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a2a767ccd0e9bdc5b1b4a2069a6679f9340a857a","datavalue":{"value":{"entity-type":"item","numeric-id":14275,"id":"Q14275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$1DCB4547-1364-484D-AE4B-3B35984CA6EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"246d8bcd4bf1600a7c6d2b07f9f11f8689d33486","datavalue":{"value":{"entity-type":"item","numeric-id":40320,"id":"Q40320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$46B4DAA8-75E4-4F9C-9950-F5E0338EDAAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"cc41d9364226bfa8139f8dbc43b1b77967245f13","datavalue":{"value":{"entity-type":"item","numeric-id":17631,"id":"Q17631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$9CD2AC06-3201-46B7-A977-0F93FBD2BAA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ecda3e6d8e971c0b93d4cf3afb41990e853f830f","datavalue":{"value":{"entity-type":"item","numeric-id":13212,"id":"Q13212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$0E5D58B7-16EF-4F99-9CBC-5C84EB89E7D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"03281999c3208b8f3a62eaceadadf1ce834fe219","datavalue":{"value":{"entity-type":"item","numeric-id":12929,"id":"Q12929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$CF207D3E-D384-44A1-9E6B-5A83C23E0B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a24f8a7388f66e88d6b3ae785d8ac21a7facd0b9","datavalue":{"value":{"entity-type":"item","numeric-id":34466,"id":"Q34466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$83ED5C5C-10E8-4B48-A011-08437086091E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"244ebbac6461f60bed6d50e50ce8194b0e233968","datavalue":{"value":{"entity-type":"item","numeric-id":40296,"id":"Q40296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$CE8AA059-F05C-4E42-A26E-902E00B6A1CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"3a073d1e3162db58b1a890386d8dbe9eebb4637c","datavalue":{"value":{"entity-type":"item","numeric-id":40373,"id":"Q40373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$78746509-9EC0-48BF-A8E6-AA2661669889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"b74075817e632ca235b8b1333580f4f12e29f9fd","datavalue":{"value":{"entity-type":"item","numeric-id":40372,"id":"Q40372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$CC41CFA3-4867-46A7-B7E3-B10CF012F8E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"6bbc316d4497e097d8fb3e48fd57f7643b44826c","datavalue":{"value":{"entity-type":"item","numeric-id":40246,"id":"Q40246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$53AA4FD4-4D75-440D-BF86-1988B36E5BA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"03bedb439d5ea402bd9603d3cdfe1813f9fa06ca","datavalue":{"value":{"entity-type":"item","numeric-id":40356,"id":"Q40356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$56830F85-62B2-4369-B201-840C5D3D3F53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"0777df209460f6d453f13a63edbbd60cf656f2b5","datavalue":{"value":{"entity-type":"item","numeric-id":40355,"id":"Q40355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$E20D5D85-ACD9-407A-AF64-E7F6B9440A34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"2cd157c0ce895ace042c647f41667d99482a6298","datavalue":{"value":{"entity-type":"item","numeric-id":23299,"id":"Q23299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$B73886DA-744A-46C1-A162-0CFB7260EEE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"74afd8a3b10bf054bf31ff15012404c74fd8d4f2","datavalue":{"value":{"entity-type":"item","numeric-id":53726,"id":"Q53726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$9322A65C-5ECB-40B0-AB78-171BB2886596","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"10fef36c72ce6737e4d52153b38693318e8540dd","datavalue":{"value":{"entity-type":"item","numeric-id":53725,"id":"Q53725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$D1F5D108-85B5-4BC7-8DAA-8B6914123084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"dd25ad249c2b0bfc0ae57f791baa0d6fded59cb3","datavalue":{"value":{"entity-type":"item","numeric-id":32511,"id":"Q32511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$B61C4A52-EE29-4E53-BD30-4E0C01202DB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ed15eb8701a335444fde1bcc3327d1067ce64751","datavalue":{"value":{"entity-type":"item","numeric-id":24376,"id":"Q24376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$920D30B0-A4A3-48E0-908F-F068CB409048","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"7d1a8519018039436924ad678b461ed447b5bd71","datavalue":{"value":{"entity-type":"item","numeric-id":40310,"id":"Q40310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$1736ABAC-271B-41C4-A0D1-73E1526DF589","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8a428f05a606483c98630626feed7c7ebc5be4dd","datavalue":{"value":"https://isa-afp.org/entries/Root_Balanced_Tree.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q40371$6EEC077A-0A10-4A9B-90F2-37A4CCB41F2E","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"78083bbf5b06a4f292e9e00ee445948e4fa51db5","datavalue":{"value":"Tobias Nipkow","type":"string"},"datatype":"string"},"type":"statement","id":"Q40371$61323998-90E0-4E08-BC88-0F47989E6361","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aeb8faa1e80c527fb1c67af95d88ec81ca5b08eb","datavalue":{"value":"Andersson introduced general balanced trees , search trees based on the design principle of partial rebuilding: perform update operations naively until the tree becomes too unbalanced, at which point a whole subtree is rebalanced. This article defines and analyzes a functional version of general balanced trees, which we call root-balanced trees . Using a lightweight model of execution time, amortized logarithmic complexity is verified in the theorem prover Isabelle. This is the Isabelle formalization of the material decribed in the APLAS 2017 article Verified Root-Balanced Trees by the same author, which also presents experimental results that show competitiveness of root-balanced with AVL and red-black trees.","type":"string"},"datatype":"string"},"type":"statement","id":"Q40371$EA6C8B0F-ED33-4D7B-957B-674B13FFFAC3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca3eea3d02312a1a919c8f20c91f08e81477149a","datavalue":{"value":{"entity-type":"item","numeric-id":4028903,"id":"Q4028903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$52A90CD4-4CB1-44D5-91FE-149630C560CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef557d8e1341d7bd3b6a423803b0facdf2efa6c2","datavalue":{"value":{"entity-type":"item","numeric-id":4228282,"id":"Q4228282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$9A5334FB-584D-4821-9088-CAE57D684680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be601c5bf7825539b84b5a53fa0383fa6e2a1c28","datavalue":{"value":{"entity-type":"item","numeric-id":5056001,"id":"Q5056001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$B012CB4C-C8FA-4DC1-AA02-831D8B76FC34","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a96ba71a589792865ac78ed095e262aa2e730862","datavalue":{"value":{"time":"+2017-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q40371$8B8BB3F4-0BE1-4DE3-916C-C07484C3743A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5e5c7c05c8cdfe9640cfd15603e78f57575f6218","datavalue":{"value":{"text":"Root-Balanced Tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q40371$45F321D4-4A56-4282-91C9-521CBA0687B4","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$16522F7C-7576-47DA-9247-D9E69E4684CB","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"8455051b40ae39924eb6a0dc07670c52cc941af6","datavalue":{"value":{"entity-type":"item","numeric-id":7361397,"id":"Q7361397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$8B45323E-16FA-4625-BEEC-C444AC8E1414","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"ef7bddd24a035fe32f48fd95ea6033928a9b8e67","datavalue":{"value":{"entity-type":"item","numeric-id":7360788,"id":"Q7360788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40371$86037DF6-BBA0-49E9-8E47-19B74D167757","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Root Balanced Tree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Root_Balanced_Tree"}}}}}