Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

RedBlack fails to rebalance or recolor in delete #2849

Closed
scabug opened this issue Dec 31, 2009 · 8 comments
Closed

RedBlack fails to rebalance or recolor in delete #2849

scabug opened this issue Dec 31, 2009 · 8 comments
Assignees
@axel22

Comments

@scabug
Copy link

scabug commented Dec 31, 2009

I suffer from a !StackOverflowError in !RedBlack when using an immutable !SortedSet (scala.collection.immutable.!TreeSet) in certain circumstances.

For example with this little test program:

import collection.immutable.{TreeSet,SortedSet}

object RedBlackTest {
  def main(args: Array[String]) {

    var big = 100000

    var aSortedSet: SortedSet[Int] = TreeSet(big)

    for (i <- 1 until 10000) {
      aSortedSet = (aSortedSet - big) ++ (TreeSet(i, big - 1))
      big = big - 1
      if (i % 1000 == 0) {
        println("size = " + aSortedSet.size)
        val head = aSortedSet.until(i)
        println("head size = " + head.size)
      }
    }
  }
}

This is the result in version 2.8.0.r20327-b20091231020112 on java "1.6.0_15"

size = 1001
head size = 999
size = 2001
head size = 1999
size = 3001
head size = 2999
size = 4001
head size = 3999
size = 5001
head size = 4999
size = 6001
head size = 5999
size = 7001
java.lang.StackOverflowError
	at scala.collection.immutable.RedBlack$$NonEmpty.count(RedBlack.scala:129)
	at scala.collection.immutable.RedBlack$$NonEmpty.count(RedBlack.scala:129)
	at scala.collection.immutable.RedBlack$$NonEmpty.count(RedBlack.scala:129)

The problem doesn't occur with simple additions to the set. The order of the operations in aSortedSet = (aSortedSet - big) ++ (TreeSet(i, big - 1)) makes a difference.

If you run this test through a debugger, and have a look at the structure of the actual tree, you'll see something like this (after 5 iterations):

BlackTree(5,(),BlackTree(4,(),BlackTree(3,(),BlackTree(2,(),BlackTree(1,(),Empty,Empty),Empty),Empty),Empty),BlackTree(99995,(),Empty,Empty))

In other words: an unbalanced tree, hence the !StackOverflowError.
@scabug
Copy link
Author

scabug commented Dec 31, 2009

Imported From: https://issues.scala-lang.org/browse/SI-2849?orig=1
Reporter: Jan Van Besien (janvanbesien)
Attachments:

@scabug
Copy link
Author

scabug commented Dec 31, 2009

Florian Hars (florian) said:
The core reason seems to be that RedBlack fails to correctly rebalance or recolor the tree on a delete, the simple code TreeSet(1,2,3) - 3 results in a tree
BlackTree(2,(),BlackTree(1,(),Empty,Empty),Empty)
which has paths with two (root -> root.right) and three (root -> root.left -> root.left.left) black nodes from the root to a leaf.

@scabug
Copy link
Author

scabug commented Jan 2, 2010

@dcsobral said:
Patch

@scabug
Copy link
Author

scabug commented Jan 2, 2010

@dcsobral said:
Ok, the bug was indeed just with the deletion. I have provided a patch based on a Haskell version of Red & Black Trees, plus a ScalaCheck test for R&B Trees invariants, and basic tree properties (insertion works, deletion works, order of keys is preserved).

@scabug
Copy link
Author

scabug commented Jan 4, 2010

@lindydonna said:
Alex, do you mind looking into this?

@scabug
Copy link
Author

scabug commented Jan 5, 2010

@axel22 said:
Replying to [comment:5 malayeri]:

Alex, do you mind looking into this?

Not at all :) I'll check it out!

@scabug
Copy link
Author

scabug commented Jan 8, 2010

Terry Woodruff (twoodruff) said:
The Left-leaning Red-Black Tree variant by Robert Sedgewick
is claimed to be substantially simpler, and therefore somewhat
more performant, and easier to get implemented correctly! His Java
code is available on the web.

@scabug
Copy link
Author

scabug commented Mar 2, 2010

@dcsobral said:
Scalacheck test

@scabug scabug closed this as completed May 18, 2011
@scabug scabug mentioned this issue Apr 7, 2017
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@axel22 axel22

Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@axel22 @scabug