(tree: &mut RBTree<K, V>, mut node: *mut RBNode<K, V>)
| 569 | // 插入数据时旋转、着色 |
| 570 | #[inline] |
| 571 | unsafe fn insert_fixup<K: Ord + Debug, V>(tree: &mut RBTree<K, V>, mut node: *mut RBNode<K, V>) { |
| 572 | let mut parent: *mut RBNode<K, V> = (*node).parent; |
| 573 | let mut gparent: *mut RBNode<K, V>; |
| 574 | let mut tmp: *mut RBNode<K, V>; |
| 575 | |
| 576 | loop { |
| 577 | // 节点为红色 |
| 578 | if parent.is_null() { |
| 579 | (*node).color = Color::Black; |
| 580 | break; |
| 581 | } |
| 582 | |
| 583 | if matches!((*parent).color, Color::Black) { |
| 584 | break; |
| 585 | } |
| 586 | |
| 587 | gparent = (*parent).parent; |
| 588 | tmp = (*gparent).right; |
| 589 | if parent != tmp { |
| 590 | if !tmp.is_null() && matches!((*tmp).color, Color::Red) { |
| 591 | /* parent = (*gparent).left |
| 592 | * 颜色改变 |
| 593 | * G g |
| 594 | * / \ / \ |
| 595 | * p u --> P U |
| 596 | * / / |
| 597 | * n n |
| 598 | */ |
| 599 | |
| 600 | (*parent).color = Color::Black; |
| 601 | (*tmp).color = Color::Black; |
| 602 | (*gparent).color = Color::Red; |
| 603 | node = gparent; |
| 604 | parent = (*node).parent; |
| 605 | continue; |
| 606 | } |
| 607 | tmp = (*parent).right; |
| 608 | if node == tmp { |
| 609 | /* node = (*parent).right |
| 610 | * 左子树旋转 |
| 611 | * G G |
| 612 | * / \ / \ |
| 613 | * p U --> n U |
| 614 | * \ / |
| 615 | * n p |
| 616 | */ |
| 617 | |
| 618 | left_rotate(tree, parent); |
| 619 | parent = node; |
| 620 | } |
| 621 | /* |
| 622 | * 右子树旋转 |
| 623 | * G P |
| 624 | * / \ / \ |
| 625 | * p U --> n g |
| 626 | * / \ |
| 627 | * n U |
| 628 | */ |
no test coverage detected