OK, I know I'm embarrassing myself here, but is libiberty's splay-tree.c
doing the right thing for the zig-zig and zag-zag cases? The code reads:
/* Now we have the four cases of double-rotation. */
if (cmp1 < 0 && cmp2 < 0)
{
rotate_left (&n->left, c, c->left);
rotate_left (&sp->root, n, n->left);
}
else if (cmp1 > 0 && cmp2 > 0)
{
rotate_right (&n->right, c, c->right);
rotate_right (&sp->root, n, n->right);
}
else ...
whereas I thought you were supposed to rotate on the root first
for these cases. E.g. instead of:
X Y Z
/ \ / \ / \
Y D Z X A Y
/ \ / \ / \ / \
Z C ---> A B C D ---> B X
/ \ / \
A B C D
the above seems to implement:
X X Z
/ \ / \ / \
Y D Z D A X
/ \ / \ / \
Z C ---> A Y ----> Y D
/ \ / \ / \
A B B C B C
(The other two cases seem fine.)
Richard
