{"entities":{"Q1183418":{"pageid":1194167,"ns":120,"title":"Item:Q1183418","lastrevid":66442824,"modified":"2026-04-12T10:06:17Z","type":"item","id":"Q1183418","labels":{"en":{"language":"en","value":"Height balance distribution of search trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33278"}},"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":"Q1183418$55A2D840-5531-4B4B-BF99-E7121CF26553","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"73bdfc456f313dceb661ca54f7b12744fc3bcd07","datavalue":{"value":{"text":"Height balance distribution of search trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183418$41722EA9-28E6-4B02-A88F-575CC6C62249","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"440e9e309b7ac823e84db574dbc8997867539668","datavalue":{"value":"0749.68024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183418$AF05F047-0591-445F-8FC5-69756E76FB35","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c8c4e016232bcd78f77cfb1ab9f7c389475c1715","datavalue":{"value":"10.1016/0020-0190(91)90005-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183418$F7AF0AE8-5A6B-4811-8465-395ED2AFE101","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"655734b0c6707ab827d303b6b3012a0b3916095a","datavalue":{"value":{"entity-type":"item","numeric-id":671613,"id":"Q671613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$987DAA11-4EE9-4B82-8180-9ABBFFCF3C04","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$B4598238-7102-4844-8AC2-28A0422F815A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183418$3F53EB62-AF1D-4CB2-A0C6-8AAC9B0BF0A3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6d6fcbbecc03831488d9c643d4d9780869296708","datavalue":{"value":"Local balancing in binary search trees is a heuristic applied to the frings of a tree. This technique lies between no balance (binary search trees) and rigid balance disciplines (height \\textit{G. M. Adel'son- Vel'skii} and \\textit{E. M. Landis} [An algorithm for the organization of information, Dokl. Akad. Nauk SSSR 146 (2), 263-266 (1962); English translation in Soviet Math. Dokl. 3, (1962) 1259-1263 (1962)], weight, or internal path balance). The basic is to keep the fringe of a tree balanced using local rotations. The origin of this heuristic can be traced to the work of \\textit{C. Bell} [An investigation into the principles of the classification and analysis of data on an automatic digital computer, Ph. D. Thesis, Leeds University (1965)] and \\textit{W. A. Walker} and \\textit{D. Wood}[Comput. J. 19 (4), 322-325 (1976; Zbl 0341.68026)].   We study the height balance distribution of binary search trees (BSTs), with or without local/global balancing. We extend this study to locally balanced search trees and analyze a generalized heuristic for local balance in binary search trees. From this we obtain the expected number of comparisons in successful and unsuccessful searches, and we also determine the optimal heuristic for this schema when uniform, random keys are used. We also propose an implementation, which in the worst case uses only one pointer per key. Furthermore we study the balance distribution of AVL trees and a variant of them. We also include exact results for small AVL trees.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183418$95AB801E-C766-431C-89B3-E59D209494F5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183418$D63343BB-4ED0-4EFD-A199-6E479589392A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183418$D772B92E-1D46-4B2C-B010-6DCFBA5BF3E8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f7af8c222c74fce10855dd3665d461cbf3fe091e","datavalue":{"value":"33278","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183418$417CEE9C-E1D2-4678-8E01-47E2CE417455","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e22f3a113575edfbd123e335487b18a37bfe2d4f","datavalue":{"value":"binary search trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183418$4DDEDB66-6BFE-4AC3-B59A-4A833B687D40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f2a2eeaa56fa4f1a1e84fd9d0757068ed97a366","datavalue":{"value":"balanced search trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183418$3D25EB0C-891C-47F8-BA03-E59C5859F3FA","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"e751138e8b150b28783c5a210048f6817120432b","datavalue":{"value":{"entity-type":"item","numeric-id":32511,"id":"Q32511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$5C5778D7-514F-468D-BDE8-A6F5EFEE374D","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":"Q1183418$201D118D-E008-49D5-B01D-300DF39CFFFD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fc76bb143ecc1d0afd049961019a3495fc744b4b","datavalue":{"value":"https://doi.org/10.1016/0020-0190(91)90005-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1183418$7CA4990F-F1AF-44DD-B8EC-7CB8CEB2E98B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0fc39ce94c6af56a47b4250d1e640ae719dd571b","datavalue":{"value":"W1972630724","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183418$59F1ABFE-21BF-49D5-9A22-C48ACDEEDDD1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a827154c37322c5290ca1edab9da0b7eb89fa1c","datavalue":{"value":{"entity-type":"item","numeric-id":5056099,"id":"Q5056099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$9449B3D8-786E-4760-B6C6-62ADC2E45489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"acb39af144a499ae254d4317ac28f124176af7e4","datavalue":{"value":{"entity-type":"item","numeric-id":1160488,"id":"Q1160488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$380CD35F-9995-4635-8239-66C0A3ED0819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50841ec01cee3e0a73b409db2ac155c06c92451b","datavalue":{"value":{"entity-type":"item","numeric-id":4186339,"id":"Q4186339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$7DEA8A81-3B6D-4679-A7A2-63C6BE493D5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"486f55fcfe11b8fa1ee030740c4b3e7eaca6fd42","datavalue":{"value":{"entity-type":"item","numeric-id":3714475,"id":"Q3714475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$3A59C0DB-3694-431F-81B1-2F6A427C7B3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90060329061497b6fd454adcf45640facad4de86","datavalue":{"value":{"entity-type":"item","numeric-id":1056233,"id":"Q1056233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$D976F880-B507-4071-A046-A902C58A9D40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$AC2E8854-1151-456B-9B5F-A49DB2B12CE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e37bb3fcdb01eab86b5965d3e2e5e4cd4b4a245f","datavalue":{"value":{"entity-type":"item","numeric-id":5678421,"id":"Q5678421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$4098E5D4-1E95-472A-9DE6-7AEE354A67A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6a17eaed6dd2d13f5fdb0b682b908546c7f5b61","datavalue":{"value":{"entity-type":"item","numeric-id":3696534,"id":"Q3696534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$A574A23E-030B-414E-A420-9705390D0972","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"652d0dfffcc00f1b99850fcb3cec8152f73abc90","datavalue":{"value":{"entity-type":"item","numeric-id":1054157,"id":"Q1054157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$F33776D7-FFDE-4336-9BF0-18CE6349F163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb1247f88c76a84b67cc8b7e0e4a397a4cdf25bc","datavalue":{"value":{"entity-type":"item","numeric-id":5904100,"id":"Q5904100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$F7887351-E7A3-445C-8E6D-E0EFDD6AD570","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8003bbd39893b4f4d681fe8277c618796300eaa2","datavalue":{"value":{"entity-type":"item","numeric-id":4109291,"id":"Q4109291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$50AA928B-5E8C-4CE2-8AA9-70D24042D05D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2465fca19b4185c84a91dac5ca6029a6564b8424","datavalue":{"value":{"entity-type":"item","numeric-id":3967043,"id":"Q3967043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183418$09BDC510-652F-4511-AE4D-3BFBB71499B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37f19514f3fe0661ab27f42fbbd7eeb9a196661c","datavalue":{"value":{"entity-type":"item","numeric-id":1323353,"id":"Q1323353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2569699d040f8b1838fe6e3062fc53f66a57f610","datavalue":{"value":{"amount":"+0.8497614860534668","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":"Q1183418$3357ABA1-ECB4-4DDB-B712-7A4B4C93E0FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a1d32227283e10122135f2d801401a89e35a00c","datavalue":{"value":{"entity-type":"item","numeric-id":2956694,"id":"Q2956694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"876eb74a248f6c6192b348264bb4d076389c350f","datavalue":{"value":{"amount":"+0.8495799899101257","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":"Q1183418$E49B9BC0-066A-4C8A-81C6-AD5E3713ED89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26d5a30e8e3ec9ccb8f78a3bd8017c75a292f249","datavalue":{"value":{"entity-type":"item","numeric-id":3714475,"id":"Q3714475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13f7ae437a8326854bb828788a9a3714ff102689","datavalue":{"value":{"amount":"+0.8427551984786987","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":"Q1183418$9D6EB834-FAD3-44DA-8EBD-8B70854EB825","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fda047c162ca8388175b3d392b21f11cb134cf18","datavalue":{"value":{"entity-type":"item","numeric-id":3321482,"id":"Q3321482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39b6c4ca03f6abc686bedc8abcf9a98ef292a102","datavalue":{"value":{"amount":"+0.8227119445800781","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":"Q1183418$F544468B-C179-46E0-8EEB-254E92475338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3e6057f1edb2cdd8b5d4c375d1593a3ec499243","datavalue":{"value":{"entity-type":"item","numeric-id":1923861,"id":"Q1923861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54b60c6b05277b28a66b2398710461d3f6c0447b","datavalue":{"value":{"amount":"+0.8195279240608215","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":"Q1183418$E9536E97-059E-4D87-A48E-5C3ADC5EB3BA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Height balance distribution of search trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Height_balance_distribution_of_search_trees"}}}}}