As first, sorry for my English.
Answer to a question - why node 4 dissapears is simple. 7 have parent node (or 7 is root). When you call rotateLeftChild, parent of 7 still "thinking" that his child is 7, not 4:
So, there are tree solutions:
Make link to a parent node and update it. In the end of leftRotation, make assignment, n.Parent.Left = o or n.Parent.Right = o (if (n.Parent.Left == n) or (n.Parent.Right == n) respectively). Of course, you must update links to tree's root, when you rotate child of root.
When you are adding | inserting | finding node, save all previous (parent) nodes in stack, and then after rotation you must update links to their children. Or use recursion like this:
private Splay(Node parent, Node cur, Node n, bool canMoveUpTwice = false) { if (cur.Value > n.Value) Splay(cur, cur.Left, n, !canMoveUpTwice); else Splay(cur, cur.Right, n, !canMoveUpTwice); if (canMoveUpTwice) MoveUpTwice(); else MoveUpOnce(); if (parent.Left == cur) parent.Left = n; else parent.Right = n; if (Parent == null) tree.Root = n; }
How to use. After adding node, you must run Splay(root, newNode). Be sure, you'll get stack overflow.
You must swap values of nodes and then think that nodes have been swapped. In standart implementation of rotation we have such picture: In rotation with swaps we get this (=x means "node have value X"): So, we have this code
private rotateLeftChild(Node q) { Node p = q.Left; Swap(q.Value, p.Value); A = p.Left; B = p.Right; C = q.Right; q.Left = A; q.Right = p; p.Left = B; p.Right = C; }
Be careful: the code has not been tested.