Talk:Scapegoat tree

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing  
WikiProject icon 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.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 
WikiProject Computer science  
WikiProject icon 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.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

tree[edit]

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)

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)


balancing[edit]

"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)

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)

bb-tree[edit]

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)