{"entities":{"Q1090107":{"pageid":1100859,"ns":120,"title":"Item:Q1090107","lastrevid":66912192,"modified":"2026-04-12T13:41:33Z","type":"item","id":"Q1090107","labels":{"en":{"language":"en","value":"Computing parent nodes in threaded binary trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4007721"}},"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":"Q1090107$0BA4D14E-C01B-49A2-AE5E-F3C1F08F984C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"73f66609661282d467b650e1a040e91bf1b8075c","datavalue":{"value":{"text":"Computing parent nodes in threaded binary trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1090107$D08ECC87-AA55-4706-80A7-B1C9D8BC0B6C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b5e1b0e255829d14c9603d36ca96593aaf1dd96f","datavalue":{"value":"0621.68027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090107$BB1351C7-AED3-45B8-8DCA-C56E771D6ACF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"81168cd38641e2fb9f36ce2c48f007343db67ff6","datavalue":{"value":"10.1007/BF01935047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090107$E684EC3B-222A-4E2D-BFE3-FC4A0E5E1B0A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4aacb04f6621410f49339e455765039d8ea76b53","datavalue":{"value":{"entity-type":"item","numeric-id":1090106,"id":"Q1090106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090107$1685C083-FD35-484F-B1EE-4A49FC701333","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090107$2C7A5FE5-B1ED-46B1-AB23-FE96407C352C","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":"Q1090107$7F9B70C0-EC51-4F74-8080-8998AABE660A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"495a3d06d9a0a25a1b88465b99ad536050cd3ac8","datavalue":{"value":"We give three algorithms for computing the parent of a node in a threaded binary tree, and calculate the average case complexity of each. By comparing these to the unit cost of obtaining the parent of a node with an explicit parent-pointer field, it is possible to balance runtime and storage cost with respect to the task of finding parent nodes in binary trees. The results obtained shows that, although the worst case complexity for an n-node tree is obviously O(n) for all three algorithms, the average case complexity for two input distributions is asymptotic (from below) to either 3 or 2.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090107$3B5AF17B-6242-45EB-9B91-248E112481AF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090107$0499D4D2-EDE8-4392-9361-8C2E0809B739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090107$55904A4D-5E5C-4CD7-8612-CAD570360BB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090107$5BA6A537-E6F1-47D7-A441-78EC44A68189","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d6e82ccd0b181b2f22c563d755b062dd43db710","datavalue":{"value":"4007721","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1090107$DE57D2C8-6140-4C22-AAED-15F6C585A88A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43d8de44b3f88bd19a871628a3509981cd748562","datavalue":{"value":"data structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090107$4D2E61AF-0A36-479C-9576-FE098D87CBA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1cfab7320641965853a62ff5e5c00f87e266c99b","datavalue":{"value":"binary trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090107$E2053D69-61D8-4704-8213-2848A40F04FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090107$90EEB92A-4625-4142-8385-E3891EA20378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"43ce48efb652327f503bbab041948268b783fed7","datavalue":{"value":"recurrence relations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090107$F89D90CA-9B70-4926-B561-261AB1F57C83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23d14be9089c271b31a55ad2ebbaa2ee610bcc6e","datavalue":{"value":"parent of a node","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090107$C66D93CC-A963-42BC-A14B-77CF9802F730","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e49d17c73f723e0f7083e0e79d09b1652f04c632","datavalue":{"value":"threaded binary tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090107$8A08D3D6-83B7-48E9-8610-B75CD7D910EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de6e6ec99e87a64046813cb3b5f6f74ec4a4a7b2","datavalue":{"value":"average case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090107$97DFE112-C27F-4046-833C-EB7AA6DB8BE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c15fa59b8f1ce206f81cf0de2875c3450ab5f6af","datavalue":{"value":"worst case complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1090107$13529B9C-0DAB-40D5-9276-A9D0187BA0FA","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":"Q1090107$347A43CC-3664-4B90-B198-D75AE6ADB204","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"26a57a020313df40c9759919609a3ba773e758b7","datavalue":{"value":{"entity-type":"item","numeric-id":3906432,"id":"Q3906432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090107$A78B027D-DAD0-4601-B7EB-642BB9A9CF70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dedaa2c674760fc1098cf7b6dbcec45e3a1a5b8","datavalue":{"value":{"entity-type":"item","numeric-id":3777467,"id":"Q3777467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090107$21FBE054-175E-453A-A793-D6B334C4CB22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79c4235c45aa7ac8deab49f81838427ef96f30bc","datavalue":{"value":{"entity-type":"item","numeric-id":3685212,"id":"Q3685212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1090107$D31D9EEB-E8CB-42D5-8DA4-85A740F7C4C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"004f0d0f9d263fecfe53d3ed8765cf93433a0855","datavalue":{"value":{"entity-type":"item","numeric-id":3777467,"id":"Q3777467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd8c7db927b4f322963bc1cd85d57c4e9195a391","datavalue":{"value":{"amount":"+0.7874705791473389","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":"Q1090107$042B4644-7520-4F5F-9B05-32F251EF3B11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81cf80fafe4d7b8f3fbec6809462dbd3e016a1f0","datavalue":{"value":{"entity-type":"item","numeric-id":4297204,"id":"Q4297204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"caac3337d12d9709368bb01903b2d83550b1d618","datavalue":{"value":{"amount":"+0.7408630847930908","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":"Q1090107$AD8C2C8F-65EB-4FF9-A435-2FD7C685AFF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f07f8720af00ab1b580dc2203221b8bb95533316","datavalue":{"value":{"entity-type":"item","numeric-id":3802643,"id":"Q3802643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc7a56cc6737ef88e2be4d8e3dc7870e3a686f32","datavalue":{"value":{"amount":"+0.7396959662437439","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":"Q1090107$76E397E2-64D0-4405-BCF0-22CFA85C3EDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3358737aa0d81c07496de96637a7d00024060462","datavalue":{"value":{"entity-type":"item","numeric-id":3685212,"id":"Q3685212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f672709f7e6875f124037e76dcf67b5490842f3f","datavalue":{"value":{"amount":"+0.7319940328598022","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":"Q1090107$609A6B5B-F259-4717-8F75-3AEC875B063C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fbc62846a997abb5ad412298f36fa96c3349e1c","datavalue":{"value":{"entity-type":"item","numeric-id":3723711,"id":"Q3723711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb475de6d7975aa448009ab032327428ff9e8a2f","datavalue":{"value":{"amount":"+0.7234804630279541","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":"Q1090107$5B18EDC9-02D4-4571-9C2F-750AD35ACDAB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing parent nodes in threaded binary trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_parent_nodes_in_threaded_binary_trees"}}}}}