| 167 | |
| 168 | template <typename K, typename V> |
| 169 | void SplayTree<K, V>::leftRotate(node *rt) |
| 170 | { |
| 171 | node *pivot = rt->right.get(); |
| 172 | node_ptr pv = move(rt->right); |
| 173 | node *grand_pa = rt->parent; |
| 174 | if (pv->left) |
| 175 | { |
| 176 | rt->right = move(pv->left); |
| 177 | rt->right->parent = rt; |
| 178 | } |
| 179 | |
| 180 | if (!grand_pa) |
| 181 | { |
| 182 | pv->left = move(root_); |
| 183 | root_ = move(pv); |
| 184 | pivot->parent = nullptr; |
| 185 | rt->parent = pivot; |
| 186 | } |
| 187 | else |
| 188 | { |
| 189 | if (grand_pa->right.get() == rt) |
| 190 | { |
| 191 | pv->left = move(grand_pa->right); |
| 192 | grand_pa->right = move(pv); |
| 193 | } |
| 194 | else |
| 195 | { |
| 196 | pv->left = move(grand_pa->left); |
| 197 | grand_pa->left = move(pv); |
| 198 | } |
| 199 | pivot->parent = grand_pa; |
| 200 | rt->parent = pivot; |
| 201 | } |
| 202 | rt->maintain(); |
| 203 | pivot->maintain(); |
| 204 | if (grand_pa) |
| 205 | grand_pa->maintain(); |
| 206 | } |
| 207 | |
| 208 | template <typename K, typename V> |
| 209 | void SplayTree<K, V>::rightRotate(node *rt) |