Horki
July 9, 2020, 9:03pm
1
I want to rewrite (for educational purposes) Red-Black Tree data structure(from Sedgewick, Algorithms 4th ed.)
For example, I have an issue doing safe rotation (rotation left and right), any suggestions on how to do it properly?
My code
Sedgewick example in java, full-example
Summary
private Node rotateLeft(Node h) {
assert isRed(h.right);
Node x = h.right;
h.right = x.left;
h.color = RED;
x.left = h;
x.color = h.color;
x.size = h.size;
h.size = size(h.left) + size(h.right) + 1;
return x;
}
cliff
July 9, 2020, 11:31pm
2
IIRC, you will need to take ownership of three nodes: a child node and two grandchildren. In order to do that, you'll need to detach the grandchildren from the child node, so each is directly owned by the function that is doing the rotation. You can probably do this with std::mem::replace
, like this:
let left = std::mem::replace(&mut child.left, RedBlackTree::NIL);
2 Likes
Horki
July 22, 2020, 10:19pm
3
Well in this hobby version, I've used without parent node, (due to recursive nature, "self" is parent).
So, far I have managed to have semi-working RBTree, still need to fix right rotation .
Horki
July 24, 2020, 10:09pm
4
I have fixed right rb-rotation. here
Horki
August 26, 2020, 2:45pm
5
Ok, so I turn it into my first crate
1 Like
system
Closed
November 24, 2020, 2:45pm
6
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.