Talk:Scapegoat tree

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
???	This article has not yet received a rating on the assessment scale.
???	This article has not yet received an importance rating on the assessment scale.

[edit] 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)