Splay tree: Revision history

Filter revisionsshowhide

To date:

Tag filter:

Invert selection

External tools:

For any version listed below, click on its date to view it. For more help, see Help:Page history and Help:Edit summary. (cur) = difference from current version, (prev) = difference from preceding version, m = minor edit, → = section edit, ← = automatic edit summary

curprev 02:4602:46, 21 April 2024‎ DanielMussell talk contribs‎ 33,219 bytes +805‎ Mention the CBTree, a counting-based concurrent variant of the splay tree. undo

curprev 20:0320:03, 31 March 2024‎ David Eppstein talk contribs‎ 32,414 bytes +9‎ Undid revision 1216565709 by 99.231.1.14 (talk) "=O" is a single piece of notation. "O" is not a function, producing something for which ≤ comparison is meaningful. undo
curprev 19:4319:43, 31 March 2024‎ 99.231.1.14 talk‎ 32,405 bytes +3‎ According the description in the next statement 'the inequality', this should be an less or equal sign rather than equal sign undo Tag: Visual edit

curprev 18:2418:24, 17 November 2023‎ CiaPan talk contribs‎ m 32,402 bytes +5‎ →‎Implementation and variants: MOS:WE undo
curprev 18:1718:17, 17 November 2023‎ CiaPan talk contribs‎ m 32,397 bytes −24‎ →‎Insertion: simplifying the description undo
curprev 11:5911:59, 17 November 2023‎ CiaPan talk contribs‎ 32,421 bytes −32‎ →‎Splaying: MOS:WE, MOS:INSTRUCT, MOS:NOTETHAT undo
curprev 11:5611:56, 17 November 2023‎ CiaPan talk contribs‎ 32,453 bytes −202‎ →‎Operations: undone the unrelated change Special:Diff/419538421 made on 18 March 2011 by 24.77.47.103 undo

curprev 15:0815:08, 18 October 2023‎ Kku talk contribs‎ m 32,655 bytes +4‎ link [mM]emory footprint undo

curprev 08:2908:29, 18 August 2023‎ OAbot talk contribs‎ m 32,651 bytes −4‎ Open access bot: doi updated in citation with #oabot. undo

curprev 09:1109:11, 19 June 2023‎ Citation bot talk contribs‎ 32,655 bytes +57‎ Add: s2cid, doi. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 862/999 undo

curprev 10:2310:23, 9 May 2023‎ WikiCleanerBot talk contribs‎ m 32,598 bytes 0‎ v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation) undo Tag: WPCleaner

curprev 15:1215:12, 28 April 2023‎ AlgorithmSoup talk contribs‎ 32,598 bytes −29‎ No edit summary undo
curprev 14:3914:39, 28 April 2023‎ AlgorithmSoup talk contribs‎ 32,627 bytes +620‎ →‎Variants: Added a citation connecting to succinct data structures. undo Tag: Visual edit

curprev 18:2118:21, 27 April 2023‎ 93.103.201.135 talk‎ 32,007 bytes +103‎ There are m splays and at each splay one operation was ignored. This means that in total m operations were ignored, something that is not asimptomatically neglectible. This is especially imporant for the performance theorems because if those m operations are neglected, the proof for the Static optimality theorem doesn't work. undo

curprev 10:1310:13, 30 March 2023‎ Materialscientist talk contribs‎ m 31,904 bytes −3‎ Reverted edits by 14.139.190.106 (talk) (HG) (3.4.12) undo Tag: Rollback
curprev 10:1210:12, 30 March 2023‎ 14.139.190.106 talk‎ 31,907 bytes +3‎ →‎Join undo Tag: Reverted

curprev 02:0302:03, 7 February 2023‎ 103.31.24.81 talk‎ 31,904 bytes 0‎ No edit summary undo

curprev 02:5602:56, 30 January 2023‎ OAbot talk contribs‎ m 31,904 bytes +21‎ Open access bot: doi added to citation with #oabot. undo

curprev 09:2009:20, 11 March 2022‎ WikiLinuz talk contribs‎ m 31,883 bytes −29‎ Reverted edits by WikiLinuz (talk) to last version by David Eppstein undo Tag: Rollback

curprev 23:4423:44, 10 March 2022‎ WikiLinuz talk contribs‎ 31,912 bytes +29‎ added Category:Data structures using HotCat undo Tag: Reverted

curprev 08:2908:29, 19 February 2022‎ David Eppstein talk contribs‎ 31,883 bytes −37‎ →‎top: I don't know what "sufficiently non-random" is supposed to mean undo
curprev 08:2908:29, 19 February 2022‎ David Eppstein talk contribs‎ 31,920 bytes +237‎ →‎top: dyn opt conj undo
curprev 08:2608:26, 19 February 2022‎ David Eppstein talk contribs‎ 31,683 bytes +209‎ Ok, whatever, but if you're going to remove the entropy from the infobox, don't bury it deep in the analysis and leave the lead falsely implying that random patterns are slow. And it is incorrect to remove "amortized" from the average case; the average case analysis is still amortized. undo
curprev 07:3807:38, 19 February 2022‎ 134.19.11.175 talk‎ 31,474 bytes +376‎ WP:Verifiability: correct worst cases in Infobox (covered by reliable source); quote of Knuth; interpretation of Grinberg undo Tag: Visual edit: Switched

curprev 18:5718:57, 17 January 2022‎ Rusalkii talk contribs‎ 31,098 bytes +56‎ Adding local short description: "Self-adjusting binary search tree", overriding Wikidata description "self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again" (Shortdesc helper) undo

curprev 15:3715:37, 15 January 2022‎ Dawnseeker2000 talk contribs‎ 31,042 bytes −6‎ clean up after myself undo
curprev 15:3515:35, 15 January 2022‎ Dawnseeker2000 talk contribs‎ m 31,048 bytes −38‎ date format audit, minor formatting undo Tag: AWB

curprev 21:0821:08, 3 January 2022‎ 136.56.9.115 talk‎ 31,086 bytes +40‎ No edit summary undo

curprev 16:5516:55, 4 December 2021‎ David Eppstein talk contribs‎ 31,046 bytes −1,203‎ Undid revision 1058590243 by Nomen4Omen (talk) Bad edits by editor who refuses to understand this material and demonstrates that refusal and lack of understanding repeatedly on talk undo Tag: Undo
curprev 14:1314:13, 4 December 2021‎ Nomen4Omen talk contribs‎ 32,249 bytes +1,203‎ see talk undo Tag: Reverted

curprev 18:1318:13, 7 November 2021‎ JCW-CleanerBot talk contribs‎ m 30,351 bytes 0‎ task, replaced: Software—Practice and Experience → Software: Practice and Experience undo Tag: AWB

curprev 23:4423:44, 4 October 2021‎ David Eppstein talk contribs‎ 30,351 bytes +329‎ →‎Performance theorems: add entropy to main article text undo
curprev 22:5222:52, 4 October 2021‎ David Eppstein talk contribs‎ 30,022 bytes −6‎ put entropy into average case; may be better than log n depending on access pattern undo
curprev 16:5916:59, 4 October 2021‎ David Eppstein talk contribs‎ 30,028 bytes +61‎ Undid revision 1048114144 by Nomen4Omen (talk) If you don't understand amortized analysis you should not be making this sort of change undo Tag: Undo
curprev 09:3609:36, 4 October 2021‎ Nomen4Omen talk contribs‎ m 29,967 bytes −61‎ see talk undo Tag: Reverted

curprev 12:5912:59, 6 July 2021‎ OAbot talk contribs‎ m 30,028 bytes +21‎ Open access bot: doi added to citation with #oabot. undo

curprev 14:4914:49, 2 March 2021‎ Citation bot talk contribs‎ 30,007 bytes −70‎ Removed parameters. | Use this bot. Report bugs. | Suggested by Abductive | via #UCB_webform 1529/1999 undo

curprev 15:4315:43, 27 December 2020‎ Monkbot talk contribs‎ m 30,077 bytes −112‎ Task 18 (cosmetic): eval 13 templates: del |ref=harv (8×); undo Tag: AWB

curprev 03:3603:36, 7 November 2020‎ 2001:240:2403:dd5b:15f0:e38d:46bf:a2e9 talk‎ 30,189 bytes +1‎ →‎Advantages: Fixed link undo Tags: Mobile edit Mobile web edit

curprev 16:4516:45, 17 October 2020‎ David Eppstein talk contribs‎ 30,188 bytes +42‎ "Average case" means averaged over some probability distribution of inputs or of random choices. "Amortized" concerns WORST CASE inputs. The amortized analysis holds regardless of which input sequence is given to the data structure; it is a form of worst case analysis. Confusing them like this means that you do not understand these concepts well enough to be editing this article. undo
curprev 10:0510:05, 17 October 2020‎ 92.119.17.10 talk‎ 30,146 bytes +329‎ Splay trees do not meet the O(log n) height definition of self-balancing binary search tree, so rewrite to avoid claiming that. Italicize n consistently. TODO: Add ref to self-organizing list. undo

21 April 2024

31 March 2024

17 November 2023

18 October 2023

18 August 2023

19 June 2023

9 May 2023

28 April 2023

27 April 2023

30 March 2023

7 February 2023

30 January 2023

11 March 2022

10 March 2022

19 February 2022

17 January 2022

15 January 2022

3 January 2022

4 December 2021

26 November 2021

7 November 2021

4 October 2021

6 July 2021

2 March 2021

27 December 2020

7 November 2020

17 October 2020