{"entities":{"Q1853166":{"pageid":1863908,"ns":120,"title":"Item:Q1853166","lastrevid":71501496,"modified":"2026-04-13T22:41:00Z","type":"item","id":"Q1853166","labels":{"en":{"language":"en","value":"Restricted rotation distance between binary trees."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856496"}},"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":"Q1853166$6C51830E-2411-4DCB-9391-B163BAA0E75E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b191460989894660863e0510dedd2be8c72ad233","datavalue":{"value":{"text":"Restricted rotation distance between binary trees.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853166$0DEA65DE-5E60-4AA8-974D-CBCD2899AF11","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d6709b2dad2c2b8150db7b4167ff7f90a6b23254","datavalue":{"value":"1042.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853166$90ED1D80-B17F-4522-8476-34EC1EE6A09A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"88324da16aa3eae713517a3a25b3b12c146e3cfd","datavalue":{"value":"10.1016/S0020-0190(02)00315-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853166$CCF7CEF3-BD2E-4693-B641-15659A3AE5F3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e020875c682dc5c4508539d2a1cbbb79ef40624b","datavalue":{"value":{"entity-type":"item","numeric-id":346686,"id":"Q346686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$F9D1E5B1-A68A-4ACB-BDEB-CEECF521766E","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":"Q1853166$F91EA21B-09CE-4212-8C79-023CD78404CB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853166$3070A881-1331-4A50-A388-46904DA6F020","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e5eba1d62b56b8e6a3853d5bfd0247f838a0ce5","datavalue":{"value":"Restricted rotation distance between pairs of rooted binary trees measures differences in tree shape and is related to rotation distance. In restricted rotation distance, the rotations used to transform the trees are allowed to be only of two types. Restricted rotation distance is larger than rotation distance, since there are only two permissible locations to rotate, but is much easier to compute and estimate. We obtain linear upper and lower bounds for restricted rotation distance in terms of the number of interior nodes in the trees. Further, we describe a linear-time algorithm for estimating the restricted rotation distance between two trees and for finding a sequence of rotations which realizes that estimate. The methods use the metric properties of the abstract group known as Thompson's group \\(F\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853166$6F8734A3-DDFA-411A-A6FB-AD45A40CD490","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853166$81E5C9DB-427D-4C79-92A9-83F686AF178C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853166$FE60576A-B113-4C25-B128-191CA5EE1A29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853166$3B95836B-560A-40E1-BEA2-B20EDCCF612A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ed2d028b5635c051285f952529731dc28483e842","datavalue":{"value":"1856496","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853166$54B1BEFC-F726-4D65-A17E-7A0854C3176B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"337bb7b370828935596a5578cd3d03f0c5c93b9f","datavalue":{"value":"Algorithms and data structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853166$45D417BD-1602-429E-B1FC-385CCF182D97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"073c51639ad2163ffecedc78e95adb4cb1673d14","datavalue":{"value":"Binary trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853166$250AAFD3-CFE4-441E-9D90-AAE45A08C696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"448bc2ea64e90bc312ece6bcc702f1a49ab6bdab","datavalue":{"value":"Rotation distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853166$781A4371-5A42-49FD-9294-92B6B2401B3E","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":"Q1853166$D37B6A13-57CA-46DB-9930-59D51C3105B4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"70fe176529e5e807ffb2b7826263c20a01aaa223","datavalue":{"value":{"entity-type":"item","numeric-id":761661,"id":"Q761661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$DDAC12C7-F240-494D-BACD-929EEDBF85A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7177ccf4fce139371bef04d4689496e6bb18f81c","datavalue":{"value":{"entity-type":"item","numeric-id":4012139,"id":"Q4012139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$87808105-9D2F-45B0-A111-B60D7E223419","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"177698dd2907316958a2bc5c1a235e3ef9eca2c1","datavalue":{"value":{"entity-type":"item","numeric-id":1284098,"id":"Q1284098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$2F236857-AE28-4741-81B8-ED64206CE24A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c87ded4c6cf74fe94e6c7e0e1f05e7ede1a13858","datavalue":{"value":{"entity-type":"item","numeric-id":2701675,"id":"Q2701675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$C92F6F29-B2F9-4C0D-985E-165C6414F22A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6821e57c2ca89a3d8e7a06534b6a786df81d4b3f","datavalue":{"value":{"entity-type":"item","numeric-id":1355389,"id":"Q1355389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$164E7855-7C23-4546-A667-44851051B3BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b875fe67b4d8496bd5d08cd6af0fefb1515124a","datavalue":{"value":{"entity-type":"item","numeric-id":1166933,"id":"Q1166933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$F59A4063-2030-48E9-9447-8B8A93E0DF79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bda3489b46b03cce2e2d044b296bd7198c95bbca","datavalue":{"value":{"entity-type":"item","numeric-id":4003861,"id":"Q4003861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$0D8398EC-527B-4F6B-B48C-F5262163D970","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"320a4959b3b19951cebc6a79a1a4b49c7a726972","datavalue":{"value":{"entity-type":"item","numeric-id":3772406,"id":"Q3772406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$419CC3A8-DF3C-4D65-BB04-FA3EE3B0F534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bcab14a5f022ab6fadf41be13880ca9cebe28f8","datavalue":{"value":{"entity-type":"item","numeric-id":4942049,"id":"Q4942049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$B617E5E6-DE0D-4EF8-9352-8C16CA0C4E04","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":"Q1853166$2ADD4B2A-707F-4760-A31B-A3E9826FB598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9769a1cf0247a2e7c47d142d09c00f0f775a8cf5","datavalue":{"value":{"entity-type":"item","numeric-id":1823251,"id":"Q1823251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$8847F2A2-6C48-484B-A504-9A887EEF8046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e8ab6c7426b8f397521f8c2c4ff4df6e9fcb44c","datavalue":{"value":{"entity-type":"item","numeric-id":1607028,"id":"Q1607028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$347EE38F-259D-4EF0-9CA4-95D09B4B9021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3673e367d750040d00f1954859de86ab3ecdee84","datavalue":{"value":{"entity-type":"item","numeric-id":4949795,"id":"Q4949795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$497DCC2A-CB13-4AF2-B6D3-ADFDCB313A85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abddcdf77a414c8ac1adf4bfd3e72bdf6dd1851c","datavalue":{"value":{"entity-type":"item","numeric-id":3799259,"id":"Q3799259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853166$11AFB522-AD30-4C05-A79A-9677ECEEAC35","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4ffd08dbcb957bad5c8751a96b8f81b56ba5e9e8","datavalue":{"value":"https://doi.org/10.1016/s0020-0190(02)00315-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1853166$412938E9-BACD-4B72-8C18-3E2F62107042","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8e6ffb95b6dd76f59864a187182632ec95fb4cb0","datavalue":{"value":"W1972564423","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853166$E02AECC8-6F9E-429D-BCA2-89F89CCEB7BA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe7751ba29ae3499c502bb4249e67e84ac87363b","datavalue":{"value":{"entity-type":"item","numeric-id":1029025,"id":"Q1029025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd95c2347a2de8bc1b20b72d5e484df31411e22b","datavalue":{"value":{"amount":"+0.93744957447052","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":"Q1853166$DAE0D9ED-6A37-49D7-B151-204FB067570B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60ebbcf61b841bfc881f0e7b7b0a8434b85baaef","datavalue":{"value":{"entity-type":"item","numeric-id":5297790,"id":"Q5297790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc65945eb9319b3e1ad171bb83dbb9a058ae7a99","datavalue":{"value":{"amount":"+0.9217355251312256","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":"Q1853166$7537276E-0DBC-4BDA-B9F4-87CAC63D6707","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"211e3c872e2d73575532a566d2734812618ffc91","datavalue":{"value":{"entity-type":"item","numeric-id":845999,"id":"Q845999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46503888bd27e886318c019db5767f72a6302aaf","datavalue":{"value":{"amount":"+0.880325198173523","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":"Q1853166$4B148402-1901-4091-A9C2-C14F07D8488F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6f42d96351d32e233019b903ee048b199e84342","datavalue":{"value":{"entity-type":"item","numeric-id":5045245,"id":"Q5045245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34c88b9942e1adfd58cf11d4baacd95a590561e0","datavalue":{"value":{"amount":"+0.8763718605041504","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":"Q1853166$EF944588-D42F-4847-A5FB-768D5717413C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"138e5bad1c58e6b06ce6d5f49d73e1fc6ce27609","datavalue":{"value":{"entity-type":"item","numeric-id":5886032,"id":"Q5886032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57d073668e514bd6b4372370f9dc34ed5f80a787","datavalue":{"value":{"amount":"+0.8733505606651306","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":"Q1853166$9C3DC00C-E892-47F0-B497-45D13891F316","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Restricted rotation distance between binary trees.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Restricted_rotation_distance_between_binary_trees."}}}}}