Talk:Splay tree

From Wikipedia, the free encyclopedia

Someone please do a pseudocode implementation of splay on the main page. (I removed the note suggesting that, since such notes should be confined to the talk pages.) 68.100.96.143

I've been trying to work out a way to balance a splay tree since I saw this article's claim that splay trees are "self-balancing" and support O(log N) "amortized time" insertions and deletions. I have found multiple splay trees that cannot be balanced and also keep the order defined by splaying. I'm changing the "amortized time" for now, but I would like to chat with someone about the idea that a splay tree can self-balance, just in case I'm crazy. Tjdw 14:16, 15 Jan 2004 (UTC)

I believe splay trees (at least above a certain size) will be (roughly) balanced (meaning their height will be in O(log n)), or at least cannot stay unbalanced once nodes in unbalanced parts of the tree are accessed. I have not checked for myself, but Sleator and Tarjan state in their original article that the height of nodes on the access path to a node being accessed get approximately halfed. If splay trees could be and stay unbalanced, the given worst-case access time could hardly hold. As many internet sources claim this too, I reintroduced it to the article (otherwise the last paragraph would in my eyes not be correct).DrZ 23:11, 14 May 2004 (UTC)

Actually, splay trees are not necessarily self-balancing, they are only stochastically self-balancing. That is why you get O(log n) amortized time - a single access can take n comparisons, just as with a plain binary search tree. It will, however, also somewhat rebalance the tree. Moreover, the insertations that debalance the tree are very cheap, so that in sum you get excellent behaviour. --Stephan Schulz 13:57, 26 May 2005 (UTC)

Should note that the complexity approximates O(M) where M is the working set of nodes, and is therefore appropriate to use when the working set is significantly smaller than the full set. Should also note that both reading (find) and writing (insert/delete) are about equally expensive, so it may behave poorly compared to other self-balancing trees (that only modify the tree in update) when updates are rare.

Complexity should be O(log M), unless I misuderstand what you are saying. --Stephan Schulz 13:57, 26 May 2005 (UTC)

Although the working set theorem says splays have a near O(1) access time for those items in the working set (given working set is small relative to the number of total nodes and constant), in practice randomly constructed BSTs have been shown to outperform splays even when the access pattern is heavily skewed (see, for example, Bell and Gupta). Also of note is that splay trees have better cache performance than BSTs under certain settings. Finally, we should discuss different splalying variants. Top Down vs. Bottom up. The "simple" top-down splaying variant (explained by Sleator and Tarjan) as implemented by Weiss (Data structures in C) is fast in practice (as compared to other variants).

I should probably write up pseudocode (or other more detailed explanation of the algorithm), given that I have both implemented it and documented it before. Bovlb 07:56, 2004 Mar 5 (UTC)

Diagrams of Splaying would be helpful.

I would like to know what literature/research support the claim that "randomly rebalancing the tree can avoid this unbalancing effect and give similar performance to the other self-balancing algorithms"? I didn't manage to verify that, though I tried.

Contents 1 Self-balancing? 2 Proofs? 3 Uniform sequence 4 Where is Splay?

[edit] Self-balancing?

I have an issue with the fact that this page says splay trees are "self-balancing" as opposed to "self-adjusting". AVL trees, for example, are self-balancing because they maintain a height of O(log n). In contrast, splay trees can have linear height for an indefinite period of time. Of course, splay trees were indroduced as "self-adjusting binary search trees" as well. (Jamie King 16:30, 23 February 2006 (UTC))

See my comment above. They are only stochastically self-balancing. Still, I think the link is useful, so I don't know if we should change it.--Stephan Schulz 20:09, 23 February 2006 (UTC)

They are NOT self balancing. They are self adjusting. They do, as you say, for certain lookup patterns (e.g., random and others (see the "working set theorem" by Sleator and Tarjan)) provide amoritized O(lg n) lookups. However, amortized lookups (for some access patterns) is not equivalent to "stocahtiscally self-balancing". A valid splay tree could have essentially a linked list structure (at times) which is hardly "balanced".

[edit] Proofs?

Does anyone have proof links for the theorems? It would be nice to have a proof citation for each theorem.

--AbsolutBildung 14:08, 23 April 2006 (UTC)

I haven't read the papers for a long time, but all the core results are in the original Tarjan/Sleator paper cited. As for the rest, I'd be surprised if there is anything interesting that is provable, but not proved in Knuth (also referenced). --Stephan Schulz 15:16, 23 April 2006 (UTC)

Added references for the theorems. Jamie King 15:48, 24 April 2006 (UTC)

Thanks -- that's great! --AbsolutBildung 01:41, 26 April 2006 (UTC)

[edit] Uniform sequence

Can anyone explain to me what "uniform sequence" (of operations) means ? --194.9.67.130 12:48, 26 November 2006 (UTC)

Uniform access basically refers to accessing elements of the tree uniformly at random. A uniform sequence of operations to a sequence exhibiting uniform access, i.e., artifacts such as long runs accessing a single node or accessing just a small subset of the nodes are uncommon. It is for non-uniform sequences such as these that splay trees show an advantage. Deco 17:06, 26 November 2006 (UTC)

[edit] Where is Splay?

Why when you search for splay are you brought here. A friend was told they had splayed feet I searched for it on here and found nothing but this on the word splay. I have of course found out what it means. But why do you redirect people to this technical description of something else. Can you add splay (and it's 2 meanings and multiple uses)? I know I can, but I don't know how to make it stop redirecting —The preceding unsigned comment was added by 87.74.86.198 (talk • contribs) .

Just go to this page and edit away. In general, if you come via a redirect, clicking on the little "(Redirected from Splay)" will take you to the page that redirected you. The redirection is part of the page contents, just replace it with whatever you think needs to be said. You probably will create a disambiguation page, so please try to follow the Manual of Style. --Stephan Schulz 22:23, 27 November 2006 (UTC)