CareerCup

go thru Split in splay trees

As the tree was BST earlier, the parent of node would be greater than the rightmost child of node. So rearrange it like this ;

7
/ \
5 10
/ \ /\
2 6 8 11
/\
1 3

Suppose node is 2

then break 2 -> 5
Arrange 2 -> 3 -> 7.

New tree is

2
/\
1 3
\
7
/\
5 10
\ /\
6 8 11

Use rotation (as we use Left and Right rotation in AVL tree or Red Black tree)

Make the Node's parent as its right child.Rotation.

1. Delete the node just as you would in a normal BST (trivial if node is leaf; splice out the node if it has only one child i.e. replace with child, replace with successor if node has both children).

2. Now compare value of node with value in root. If node value > root value then original root becomes node's left child else it becomes its right child. Finally update root to node.

Compare node with root, if greater than root, replace root with node and put root as leftmost child of right subtree.If less than root, replace root with node and put root as rightmost child in left subtree. Now rearrange the tree in bottom-up fashion.

What if we just find that node and swap values of root and node ??Its a Binary Tree and not a BST . DO we also have to take care that the left and right childs wud be same in the new Tree ?

How about this ?
1.Do a DFS from root to the node you are looking for
2. Reverse the direction of the path from Root to the found node and you will get a new binary tree with the newly found node as the root....

All Solution is fail...Correct solution is to delete the main node and insert the new node twice..twice becaue first will make the binary tree and second insertion will force it to convert it to bST (duplicate matching corollary)

the answer is rotate to root:

template<typename T>
void insert_root(node*& h, T x) {
   if (!h) { h = new node{x}; return }
   if (x.key() < h->item.key()
      { insert_root(h->l, x); rotate_right(h); }
   else { insert_root(h->r, x); rotate_left(h); }
}

using the usual left or right rotations. ref: algorithms in c++, sedgewick and van wyk.

exchange the root's value and the node's value

can you pls explain what do you mean by transform ?