{"entities":{"Q7361825":{"pageid":31521014,"ns":120,"title":"Item:Q7361825","lastrevid":105423884,"modified":"2026-10-08T13:45:47Z","type":"item","id":"Q7361825","labels":{"en":{"language":"en","value":"Expected Shape of Random Binary Search Trees"}},"descriptions":{"en":{"language":"en","value":"AFP entry Random_BSTs"}},"aliases":{},"claims":{"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":"Q7361825$BF9B20E2-1047-4488-B87E-F5E3DC12F222","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"85859c7ab42dcb8b36208f2902b7ce0d86423a6f","datavalue":{"value":"Manuel Eberl","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361825$C58C5709-5A54-48E9-A414-A5A6ACDD164F","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":"Q7361825$10858344-62FD-4396-9C30-14F28527416E","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":"Q7361825$B12EB169-5BCA-4E0A-AFF5-662F0C04EC43","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":"Q7361825$5CD449F8-A4B3-4709-820B-3F9308CB3B83","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":"Q7361825$D647E108-EFBA-485F-BE91-69C0B6298FA5","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":"Q7361825$9273DCF3-533D-438E-8A72-0C4CE2325EF7","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":"Q7361825$1D16485F-3F3F-4CEF-968E-C9FCB8473497","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":"Q7361825$03F36854-60F3-47E4-A5C1-4123C804FD35","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":"Q7361825$91DEA324-D7AE-44BF-97BE-E2EF5B1C7252","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":"Q7361825$67813050-71EE-4452-B85E-4DD9FE8781AC","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":"Q7361825$4C38974F-6046-4FE3-97D9-FC6D323AF74B","rank":"normal"}],"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"9aee79e4e6a58ddced9558276f88753680de0ddf","datavalue":{"value":"28658","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361825$54EC186E-55B5-47FA-9213-FD3241968EE9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"acf10290b955a69659a681d98822944f91bbad9e","datavalue":{"value":"68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361825$E1AC508A-9FD5-465C-A421-111957C36F86","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":"Q7361825$2F22D53A-83EA-4CC1-AA55-B60924C60A4A","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":"Q7361825$CC486FBB-9DDF-43A7-BC0E-0E80F44592A9","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":"Q7361825$A5595394-AA3D-48DB-B14D-6B608ACE687E","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":"Q7361825$154CB22E-CF9C-4CB8-AC8F-63B8F3CBD743","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":"Q7361825$8F441894-32A2-4930-828D-7B1257D15F1B","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":"Q7361825$DCB220FC-346E-45A1-8984-B6C1CC639E7D","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":"Q7361825$69079F5A-8316-4D32-9F4C-A2D29F80FD1B","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":"Q7361825$22E508CF-61A3-4AD3-ACA6-0E990F25FC0D","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":"Q7361825$FE94BFEF-F0B1-4EFA-941D-BA97FDEDE28F","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":"Q7361825$328DB622-9B8C-4532-92CB-568CDF2F9811","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":"Q7361825$DDF9A3B6-42B1-4CD5-8723-E62BFF33196C","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":"Q7361825$05AED692-C60C-4922-826C-C2176C8690F4","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":"Q7361825$56897B93-7DED-41FE-9974-EC98FACA8994","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":"Q7361825$16CF05D8-AB65-4FAC-998A-A49F6D40F820","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":"Q7361825$6CE98568-C63F-4637-B0C5-E6991698D5F7","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":"Q7361825$92D6B4D0-4A92-443D-90ED-5C8BD36107A8","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":"Q7361825$ABEDFB7B-ACE4-4536-88F3-46BC4AC8EBAA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Expected Shape of Random Binary Search Trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Expected_Shape_of_Random_Binary_Search_Trees"}}}}}