Talk:Scapegoat tree

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles
???	This article has not yet received a rating on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.

Computer science Unassessed

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

???

This article has not yet received a rating on Wikipedia's content assessment scale.

???

This article has not yet received a rating on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

tree

The claim at the head of this article that "Each node in a scapegoat tree keeps track of the size and height of the subtree rooted at that node, as well as whether or not that node has been deleted," is simply wrong. As the first sentence of the second paragraph of the Abstract in the original Galperin and Rivest paper states: "Scapegoat trees, unlike most balanced-tree schemes, do not require keeping extra data (e.g. "colors" or "weights") in the tree nodes."

Agreed, I noticed that to. So I decided to be bold and lose my first article rewrite to scapegoat trees =) feedback appreciated... and any help to bring it up to par appreciated. Themania 18:59, 16 February 2007 (UTC)[reply]

The description of the deletion operation assumes an alpha of .5. Really, the rule should be written "NodeCount <= MaxNodeCount * alpa". Cebarber (talk) 17:03, 16 August 2009 (UTC)[reply]

balancing

"Once the scapegoat is found, a standard binary search tree rebalance operation is performed." Either the BST article should be edited to explain what the 'standard' operation is, or the article should expound more. It's ambiguous because it's unclear if you'd want to perform only 1 rotation (as in trees that stay strictly balanced) or multiple rotations because the tree only stays 'loosely' balanced. Actually, then red-black trees are compared, and it seems to say that red-black trees use rotations *as opposed* to whatever scapegoat trees do. Looking at the original paper it doesn't seem to explain either. —Preceding unsigned comment added by 192.160.124.68 (talk) 16:23, 12 May 2010 (UTC)[reply]

Hey, looks like someone updated it. It's a little better now but still doesn't actually explain how the rebalance operation works. It explains how you pick which node to rebalance, but not what you actually do to it. "A standard rebalancing operation is performed." Looking at the paper again it looks like he basically suggests rebuilding the whole subtree (iterate it in order, copying into an array, then divide and conquer the array to make a new tree). But the paper goes into more detail about an in-place (no extra memory use) way of doing it that seems specific to goat trees; the other tree type articles usually have pseudo code for all the steps and/or an explanation for the operations that are specific to the particular tree type in question, so I don't think that'd be out of place here. —Preceding unsigned comment added by 192.160.124.68 (talk) 14:59, 13 May 2010 (UTC)[reply]

bb-tree

Hi, it looks that idea of scapegoat tree is based on "BST of bounded balance", they even cite J.Nievergelt in their work. BB-trees are very easy to implement, and have many usefull properties, especially for functional languages. Is there any article on this in wikipedia? Nore info: http://groups.csail.mit.edu/mac/users/adams/BB/index.html , Article on polish wiki: http://pl.wikipedia.org/wiki/Drzewo_o_ograniczonym_zrównoważeniu --149.156.82.207 (talk) 19:42, 2 August 2010 (UTC)[reply]