RedBlackTrees in rust; Sedgewick style

#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;
}
#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
#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.

#4

I have fixed right rb-rotation. here

#5

Ok, so I turn it into my first crate

1 Like