Ive built my entire splay tree program successfully, every function works- splay, rotate, find and insert, but im trying to implement remove. My strategy so far has been to find and splay the element im trying to remove, deleting the node and splitting its left and right into subtrees. I splay the largest element on the left subtree successfully but I'm having trouble re assembling the tree after doing that. Any ideas how to reassemble the tree successfully?
For my remove function im finding and splaying the element i want removed successfully. i can even get the left tree to point at the right tree but im unable to update the right trees parent successfully.
node* remove(int k);
{
node* del = find(k);
node* R = del->right;
node* L = del->left;
node* big = largest(L); // returns largest in left tree
splay(big);
R->parent = big;
L->right = R;
delete del;
return big;
}