右旋操作变换为: Y X / \ / \ X c => a Y / \ / \ a b b c */
(
mut root: Option<NonNull<Node<K, V>>>,
y: NonNull<Node<K, V>>,
)
| 231 | |
| 232 | */ |
| 233 | fn rotate_right<K, V>( |
| 234 | mut root: Option<NonNull<Node<K, V>>>, |
| 235 | y: NonNull<Node<K, V>>, |
| 236 | ) -> Option<NonNull<Node<K, V>>> { |
| 237 | let mut y = NodeQuery::new(Some(y)); |
| 238 | let p = y.parent(); |
| 239 | let mut x = y.left(); |
| 240 | let a = x.left(); |
| 241 | let b = x.right(); |
| 242 | let c = y.right(); |
| 243 | y.replace(x.node); |
| 244 | y.set_children(b.node, c.node); |
| 245 | x.set_children(a.node, y.node); |
| 246 | if p.is_none() { |
| 247 | root = x.node; |
| 248 | } |
| 249 | root |
| 250 | } |
| 251 | |
| 252 | #[test] |
| 253 | fn t_insert() { |