{"entities":{"Q1072706":{"pageid":1083458,"ns":120,"title":"Item:Q1072706","lastrevid":69570042,"modified":"2026-04-13T07:54:42Z","type":"item","id":"Q1072706","labels":{"en":{"language":"en","value":"Sequential access in splay trees takes linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3943043"}},"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":"Q1072706$BF1A8CE6-219F-4D8E-A3BB-B37F41016729","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"63aabe948445423d5366c6f8574a3b17c80d9f12","datavalue":{"value":{"text":"Sequential access in splay trees takes linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1072706$C9D94BD0-DB10-40B5-85F1-EDD085A3372B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5ce8c5841d604158e6334fb8f1cc594fb8e00cfb","datavalue":{"value":"0587.68058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072706$14797E8E-4433-4F6E-80AF-7FFC8C7D87AA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ace3c0d4320aaf7aaef520447171e12eb4f7054a","datavalue":{"value":"10.1007/BF02579253","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072706$13DEA6AB-9C0F-4404-80B4-BDF7AE2E660E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072706$C90EC20D-A2CB-42C9-8E9A-A861FED5437B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1072706$964F4EDC-0A49-411D-B3A6-3AE12E027381","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a444564e00449f98323b2ed5bb85494563b296b8","datavalue":{"value":"\\textit{D. D. Sleator} and the present author [J. Assoc. Comput. Mach. 32, 652-686 (1985)] have invented a form of self-adjusting binary search tree called the splay tree. On any sufficiently long access sequence, splay trees are as efficient, to within a constant factor, as both dynamically balanced and static optimum search trees. The authors of the mentioned paper have made a much stronger conjecture; namely, that on any sufficiently long access sequence and to within a constant factor, splay trees are as efficient as any form of dynamically updated search tree. This dynamic optimality conjecture implies as a special case that accessing the items in a splay tree in sequential order takes linear time, i.e. O(1) time per access. In this paper we prove this special case of the conjecture, generalizing an unpublished result of Wegman. Our sequential access theorem not only supports belief in the dynamic optimality conjecture but provides additional insight into the workings of splay trees. As a corollary of our result, we show that splay trees can be used to simulate output-restricted deques (double-ended queues) in linear time. We pose several open problems related to our result.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072706$5CD80EAC-9631-4B15-B50E-208DA7132A53","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072706$09A91D4A-5DFE-4E5C-8DD1-78A825A6CC36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072706$D5B13798-BBCC-442E-A3FC-1EDB6982F299","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072706$95FAD25C-FBFF-46DF-8982-91BBC0DA1972","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"68715292a42ce41f475677cb1917a35bed411f62","datavalue":{"value":"3943043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072706$ACB8400E-20FB-4125-B461-E9C4A1678F02","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae59fa2fd255fcb4892b4577fae14d72baf8469b","datavalue":{"value":"self-adjusting binary search tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072706$3631EB67-9B1A-430A-9D4C-E8C3EA7A92C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"163a2f40f1b99172cf66b11402eecdafec5bf03b","datavalue":{"value":"dynamically updated search tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072706$46D5C2BB-72B6-42DB-B539-854B17B4CE58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2863bde5dc969dd6aa9fc2e9eb9a2f685bcfc928","datavalue":{"value":"dynamic optimality conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072706$CE4C195B-A49B-42BB-9D32-C15A5217998C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"716bd17511c47610acbdbdc01ac5113a21999e4c","datavalue":{"value":"output-restricted deques","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072706$DF1A9006-6306-4A56-8926-63E6F62BC5B2","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ae410c790c09d6d71093b98fa3b15d6a4cd91ba3","datavalue":{"value":"Q56066207","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072706$1B49C63E-0DE0-472B-9EF3-7AA47B9DA023","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"065c91f208b67eb2296cd8ea5272c33efd202f25","datavalue":{"value":{"entity-type":"item","numeric-id":598808,"id":"Q598808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072706$4ABEADE9-24BC-42D3-8AE6-D682F14087BD","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":"Q1072706$BF6540CB-65A1-42B5-BC5E-D5E54CF14FF4","rank":"normal"}],"P223":[{"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":"Q1072706$3BEBDD76-8871-49F4-95AD-45608E2FF941","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":"Q1072706$F382F010-6931-4A0F-A7F1-5EC594C8DA70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0f53d9231bc5ff64922d7dd218bb49071786117","datavalue":{"value":{"entity-type":"item","numeric-id":3768416,"id":"Q3768416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072706$972F1F7C-7408-4DDA-8879-6DCCC1BC3975","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e689ca9104617943bd76b284824e0c9ceb6bd","datavalue":{"value":{"entity-type":"item","numeric-id":3707420,"id":"Q3707420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072706$3F712B38-4B99-470D-9D53-59E2F79B8A0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00910816ba034b6655b7a47d13d1206cc1d40ae2","datavalue":{"value":{"entity-type":"item","numeric-id":3735083,"id":"Q3735083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072706$C9F1BFC3-E92F-492A-A139-4CC08D71936D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"86b293fb677c99868f889cce1ba4e8ecd5693ebb","datavalue":{"value":"https://doi.org/10.1007/bf02579253","type":"string"},"datatype":"url"},"type":"statement","id":"Q1072706$13E0EE9C-A190-4664-93F2-3D2EFAC06962","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"df2af6a3ce671b08e55ace107c0539fd17fda64b","datavalue":{"value":"W2078913074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072706$8FFD5969-2D8C-4936-B341-2C94C1256524","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"20fdf1e2c27d31bb964f607a9f993f83e5e2e724","datavalue":{"value":"journals/combinatorica/Tarjan85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072706$4062584F-CC19-4CB1-9483-22F3386143FA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49a8f5004ba09f7517d98146081742ea9ca9cf67","datavalue":{"value":{"entity-type":"item","numeric-id":1826644,"id":"Q1826644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0d54660efe8029ec9dcf927fd36be771c8dc1b5","datavalue":{"value":{"amount":"+0.8941518068313599","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":"Q1072706$ACDA317F-0D2B-4A21-8491-B1829E10E680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbcc615a922dfe8e77e9817223cf07f5d8f4f730","datavalue":{"value":{"entity-type":"item","numeric-id":3768416,"id":"Q3768416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"474518487921c5e19b50cc1f3043503c67f5e564","datavalue":{"value":{"amount":"+0.8750736117362976","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":"Q1072706$07E20672-C4FA-48A9-8BCF-0F7E8019C7D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69be2425deb88493cfa745218ec5542330f9fa15","datavalue":{"value":{"entity-type":"item","numeric-id":5236264,"id":"Q5236264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae5f2d70ab55f77cfb2a5722dca14b45a53bb523","datavalue":{"value":{"amount":"+0.8688974976539612","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":"Q1072706$F2894FF7-E651-4F18-AE12-7DDA86852444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6058acb4c656f8780515653ac066bb9333d7c07b","datavalue":{"value":{"entity-type":"item","numeric-id":4507339,"id":"Q4507339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bfa0cc10a583de86a40bec43b335d857a48ee9b","datavalue":{"value":{"amount":"+0.862928569316864","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":"Q1072706$F123462F-29CB-4348-A06F-3F238EC45680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"096f027931f407e775f53e6549dcc48cf480a83e","datavalue":{"value":{"entity-type":"item","numeric-id":2419117,"id":"Q2419117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15a8af160d9a32a29a55af00268e511220d19434","datavalue":{"value":{"amount":"+0.8577960133552551","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":"Q1072706$BC951232-F3D4-4A74-9AA5-5F63125A3CAB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sequential access in splay trees takes linear time","badges":[]}}}}}