{"entities":{"Q40372":{"pageid":40428,"ns":120,"title":"Item:Q40372","lastrevid":105426374,"modified":"2026-10-09T10:05:17Z","type":"item","id":"Q40372","labels":{"en":{"language":"en","value":"Random BSTs"}},"descriptions":{"en":{"language":"en","value":"AFP entry Random_BSTs"}},"aliases":{},"claims":{"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"9aee79e4e6a58ddced9558276f88753680de0ddf","datavalue":{"value":"28658","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40372$15D7FAC6-8090-4E98-9191-E409E8A953F9","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":"Q40372$0F6AC58A-0DC8-4A36-8977-B0465526C49D","rank":"normal"}],"P29":[{"mainsnak":{"snaktype":"value","property":"P29","hash":"ed460844fe7c5a4ed2d65f27fb82267bd06c5c21","datavalue":{"value":"https://www.isa-afp.org/entries/Random_BSTs.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q40372$AFE2C44C-C5CA-41A8-A6BE-F4FAF007C25C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"acf10290b955a69659a681d98822944f91bbad9e","datavalue":{"value":"68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40372$7EA33271-F095-48A2-82E5-B1A46FBAB259","rank":"normal"}],"P1458":[{"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":"Q40372$1960E058-86C7-4A08-90E8-D353780805B7","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":"Q40372$2D07DFC3-F2F8-47CC-AED4-1815BCC8670B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"868d665ea0607bf8bd28ea3e3872eb2ea87bd3d3","datavalue":{"value":{"entity-type":"item","numeric-id":40371,"id":"Q40371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40372$6B8E6F9E-7072-4D78-AA84-3F136EC7DFB3","rank":"normal"},{"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":"Q40372$13635AC0-F2F4-4AB9-A088-7C9F0C9E6A0A","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":"Q40372$062AEB65-4981-4472-B98E-2EC3B9228B53","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":"Q40372$B17E89FB-9F45-41EB-9E7B-35ACD2547747","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":"Q40372$684CE8E9-4AEE-4A20-B8BA-AA70FE1403DC","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":"Q40372$B26E4E80-164F-4A18-8015-D2C75F790648","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":"Q40372$E0153E94-61E2-4620-92E2-A9A694F0349E","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":"Q40372$EC17CC40-647A-461F-AE31-F27C92B9F238","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":"Q40372$CF0125C6-0001-45F8-98A5-9DC51BF21AE1","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":"Q40372$408BB98D-A773-4344-8C5E-039AEABD1D28","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":"Q40372$FBD0382A-B881-474D-A05E-B74238E2C07D","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":"Q40372$8BE2416D-3F50-4628-A126-5EEC6E50453E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"8dde418bf28e22fefe1976bd953eb7c8ec5b548d","datavalue":{"value":{"entity-type":"item","numeric-id":16770,"id":"Q16770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40372$EEA57B0D-C596-4FC8-A648-3CCEB2D3694B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"02b329e86bd44e002b407e5543cbe998c79c263a","datavalue":{"value":{"entity-type":"item","numeric-id":13928,"id":"Q13928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40372$59C87DE8-38DD-4207-B4F1-C5C84493F905","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":"Q40372$A439EFBF-A67E-4AB5-A320-D5EB53F0409B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0f892090ad6635b8900192b42bfb8ae9f3847c5e","datavalue":{"value":"https://isa-afp.org/entries/Random_BSTs.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q40372$D52D4138-5966-40F3-9CE9-D87208427C74","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"85859c7ab42dcb8b36208f2902b7ce0d86423a6f","datavalue":{"value":"Manuel Eberl","type":"string"},"datatype":"string"},"type":"statement","id":"Q40372$3B6209FA-A38B-461A-A31C-79889DA24533","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9e0f3d5da3653a72e90b88471ea922d101213fb1","datavalue":{"value":"This entry contains proofs for the textbook results about the distributions of the height and internal path length of random binary search trees (BSTs), i. e. BSTs that are formed by taking an empty BST and inserting elements from a fixed set in random order. In particular, we prove a logarithmic upper bound on the expected height and the \u0398(n log n) closed-form solution for the expected internal path length in terms of the harmonic numbers. We also show how the internal path length relates to the average-case cost of a lookup in a BST.","type":"string"},"datatype":"string"},"type":"statement","id":"Q40372$C02D1C1B-3B47-402D-9D2A-7BF9A928ECD8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40372$AF7299B2-4038-4FB3-99D3-2909FB4DAF6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1780f4a9266aea675c4973306f353db13abb9c0","datavalue":{"value":{"entity-type":"item","numeric-id":3452494,"id":"Q3452494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40372$60C7F287-992D-431C-ABDD-A6986EB10C8E","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"4e61d5c4974522a5fe3780c9295027ba96d92743","datavalue":{"value":{"entity-type":"item","numeric-id":7361487,"id":"Q7361487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40372$F2483DB2-DB71-465D-90F3-B3D06CC1ECEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"e9cbb7a6f50fb25879daa2b7165c9216eb9c6a2b","datavalue":{"value":{"entity-type":"item","numeric-id":7361882,"id":"Q7361882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40372$4A0615DD-D22B-44F1-B85C-4EEC12158BA6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"59c8949104cb3355067f12c7ef2dbd734933f3b0","datavalue":{"value":{"time":"+2017-04-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q40372$F257A296-A7A0-4082-97A2-EDAF76EBC1F6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cecf663cb4b9c64396415457c0ba248de464ebb8","datavalue":{"value":{"text":"Expected Shape of Random Binary Search Trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q40372$6355856D-97BA-4CA8-8E72-4E98ED7325BA","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":"Q40372$C5241CA4-8157-475A-A20A-C7A066DB97EC","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":"Q40372$03A36DD1-F693-4663-BC97-121629E61FDF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Random BSTs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Random_BSTs"}}}}}