| 207 | |
| 208 | template <typename K, typename V> |
| 209 | void SplayTree<K, V>::rightRotate(node *rt) |
| 210 | { |
| 211 | node *pivot = rt->left.get(); |
| 212 | node_ptr pv = move(rt->left); |
| 213 | node *grand_pa = rt->parent; |
| 214 | if (pv->right) |
| 215 | { // right node of pv to left node of rt |
| 216 | rt->left = move(pv->right); |
| 217 | rt->left->parent = rt; |
| 218 | } |
| 219 | if (!grand_pa) |
| 220 | { // if rt is really root of the tree |
| 221 | pv->right = move(root_); |
| 222 | root_ = move(pv); |
| 223 | pivot->parent = nullptr; |
| 224 | rt->parent = pivot; |
| 225 | } |
| 226 | else |
| 227 | { |
| 228 | if (grand_pa->right.get() == rt) |
| 229 | { // rt is in right branch from his grandparent |
| 230 | pv->right = move(grand_pa->right); |
| 231 | grand_pa->right = move(pv); |
| 232 | pivot->parent = grand_pa; |
| 233 | rt->parent = pivot; |
| 234 | } |
| 235 | else |
| 236 | { // rt is in left branch from his grandparent |
| 237 | pv->right = move(grand_pa->left); |
| 238 | grand_pa->left = move(pv); |
| 239 | pivot->parent = grand_pa; |
| 240 | rt->parent = pivot; |
| 241 | } |
| 242 | } |
| 243 | rt->maintain(); |
| 244 | pivot->maintain(); |
| 245 | if (grand_pa) |
| 246 | grand_pa->maintain(); |
| 247 | } |
| 248 | |
| 249 | template <typename K, typename V> |
| 250 | void SplayTree<K, V>::splay(node *x) |