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

RbTree.delete invalidate successor pointer when y != z #14

Closed
lsarrazi opened this issue Mar 21, 2022 · 0 comments
Closed

RbTree.delete invalidate successor pointer when y != z #14

lsarrazi opened this issue Mar 21, 2022 · 0 comments

Comments

@lsarrazi
Copy link

Hi, there is a problem in the implementation of the delete function of Red Black Tree.
rbtree.go:219:

if y != z {
	z.key = y.key
	z.value = y.value
}

It reuse the node-to-delete z in the tree and delete the successor node y
This is not correct because all pointers stored by the user on the y node will be invalidated.
I found a solution in the C++ STL of clang 13 (I believe), they swap the nodes y and z such that only z is invalidated, as expected.
Here is the code that I found:
__tree:382:

if (__y != __z)
{
    // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr
    __y->__parent_ = __z->__parent_; // 1
    if (_VSTD::__tree_is_left_child(__z))
      __y->__parent_->__left_ = __y;
    else
      __y->__parent_unsafe()->__right_ = __y;
    __y->__left_ = __z->__left_;
    __y->__left_->__set_parent(__y);
    __y->__right_ = __z->__right_;
    if (__y->__right_ != nullptr)
      __y->__right_->__set_parent(__y);
    __y->__is_black_ = __z->__is_black_;
    if (__root == __z)
      __root = __y;
}

Which I try'd to adapt to our implementation, it give me something like:
rbtree.go:219:

if y != z {
    //z.key = y.key
    //z.value = y.value

    y.parent = z.parent

    if t.root == z {
      t.root = y
    } else if z.parent.left == z {
      y.parent.left = y
    } else {
      y.parent.right = y
    }

    y.left = z.left
    y.left.parent = y

    y.right = z.right
    if y.right != nil {
      y.right.parent = y
    }

    y.color = z.color
}

But unfortunately this solution seems to break the tree for some reason that I don't know, it fail the tests.
Could a brilliant brain figure it out? I'm stuck

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants