std-lib-orphanage icon indicating copy to clipboard operation
std-lib-orphanage copied to clipboard
verified publisher icon ziglang

Red black tree "remove" bug

Open greenfork opened this issue 3 years ago • 1 comments

Order of removals breaks the tree, tests show the problem. I have no idea of when of whether I will be able to fix this, feel free to take over.

greenfork avatar Apr 24 '22 19:04 greenfork

Shorter bug reproduction:

  1. Insert nodes 12, 15, 47, 50, 60
  2. Remove 15

According to this visualisation before delete it should look like: image

and after like this image

but inspecting current implementation root is 47 and the deleted node 15 can be found as tree.root.?.right.?.left

greenfork avatar Jun 05 '22 17:06 greenfork