search

frptools / collectable

High-performance immutable data structures for modern JavaScript and TypeScript applications. Functional interfaces, deep/composite operations API, mixed mutability API, TypeScript definitions, ES2015 module exports.
MIT License
273 stars 14 forks source link

Ensure that root is black to prevent rebalancing issues #73

Closed thomastay closed 3 years ago

thomastay commented 3 years ago

Hi @axefrog, I'm working on the same team as @eliranek1. We've found another issue with rebalancing when there is a one element tree. When creating a tree with two elements, the root is black and child is red. However, upon removal of the root, the child is promoted but not set to black. Later on, when another element is pushed, this allows for a red node to have a red child.

A test case which does not rely on the internals is attached. But you can see this by setting a breakpoint after set(3, 12, tree), and noting that there are two consecutive red nodes.

This issue seems to have been introduced in https://github.com/frptools/collectable/commit/22afb0335cc7708d21480e03c2e0d75d13413758, in which the check if if (tree.size > 1) was added to prevent rebalancing of trees of size 1.

The fix is to simply set the root to always be black. This follows the approach in CLRS, where the root is always set to black after rebalancing.

Regarding maintenance, we would be happy to co-maintain the package, you can reach out to Eliran or me. Understand that you are busy, and we also want to be able to publish new versions of this package quickly.

axefrog commented 3 years ago

Just quickly passing through. Shoot me an email to axefrog at gmail and we'll go from there.

thomastay commented 3 years ago

@axefrog sent you an email last week, did you get it?

axefrog commented 3 years ago

@axefrog sent you an email last week, did you get it?

I have replied now. Sorry for the delay!

thomastay commented 3 years ago

don't merge yet, i want to update the package.jsons