(tree: &mut RBTree<K, V>, mut parent: *mut RBNode<K, V>)
| 685 | // 删除数据时旋转、着色 |
| 686 | #[inline] |
| 687 | unsafe fn delete_fixup<K: Ord + Debug, V>(tree: &mut RBTree<K, V>, mut parent: *mut RBNode<K, V>) { |
| 688 | let mut node: *mut RBNode<K, V> = null_mut(); |
| 689 | let mut sibling: *mut RBNode<K, V>; |
| 690 | /* sl and sr denote left and right child of sibling, respectively. */ |
| 691 | let mut sl: *mut RBNode<K, V>; |
| 692 | let mut sr: *mut RBNode<K, V>; |
| 693 | |
| 694 | loop { |
| 695 | // 黑色节点或空节点、非根节点 |
| 696 | sibling = (*parent).right; |
| 697 | if node != sibling { |
| 698 | /* node = (*parent).left */ |
| 699 | if matches!((*sibling).color, Color::Red) { |
| 700 | /* |
| 701 | * 左旋转 |
| 702 | * |
| 703 | * P S |
| 704 | * / \ / \ |
| 705 | * N s --> p Sr |
| 706 | * / \ / \ |
| 707 | * Sl Sr N Sl |
| 708 | */ |
| 709 | |
| 710 | left_rotate(tree, parent); |
| 711 | (*parent).color = Color::Red; |
| 712 | (*sibling).color = Color::Black; |
| 713 | sibling = (*parent).right; |
| 714 | } |
| 715 | sl = (*sibling).left; |
| 716 | sr = (*sibling).right; |
| 717 | |
| 718 | if !sl.is_null() && matches!((*sl).color, Color::Red) { |
| 719 | /* |
| 720 | * 兄弟节点右旋之后父节点左旋 |
| 721 | * (p and sr could be either color here) |
| 722 | * (p) (p) (sl) |
| 723 | * / \ / \ / \ |
| 724 | * N S --> N sl --> P S |
| 725 | * / \ \ / \ |
| 726 | * sl (sr) S N (sr) |
| 727 | * \ |
| 728 | * (sr) |
| 729 | */ |
| 730 | |
| 731 | (*sl).color = (*parent).color; |
| 732 | (*parent).color = Color::Black; |
| 733 | right_rotate(tree, sibling); |
| 734 | left_rotate(tree, parent); |
| 735 | } else if !sr.is_null() && matches!((*sr).color, Color::Red) { |
| 736 | /* |
| 737 | * 父节点左旋 |
| 738 | * (p could be either color here) |
| 739 | * (p) S |
| 740 | * / \ / \ |
| 741 | * N S --> (p) (sr) |
| 742 | * / \ / \ |
| 743 | * Sl sr N Sl |
| 744 | */ |
no test coverage detected