/// Deletes the node in the subtree rooted at r and its corresponding leaf
/// as indicated by replayComparison or deleteMax. Performs AVL balancing.
///
/// If deleteMax == false: deletes the first node for which replayComparison returns 0
/// and the leaf that is the leftmost descendant of this node's child
///
/// If deleteMax == true: deletes the right leaf and its parent, replacing the parent
/// with the parent's left child
///
/// Returns the new root and an indicator whether the tree height decreased
///
Deletes the node in the subtree rooted at r and its corresponding leaf
as indicated by replayComparison or deleteMax. Performs AVL balancing.

If deleteMax == false: deletes the first node for which replayComparison returns 0
and the leaf that is the leftmost descendant of this node's child

If deleteMax == true: deletes the right leaf and its parent, replacing the parent
with the parent's left child

Returns the new root and an indicator whether the tree height decreased
Deletes the node in the subtree rooted at r and its corresponding leaf as indicated by replayComparison or deleteMax . Performs AVL balancing . If deleteMax == false : deletes the first node for which replayComparison returns 0 and the leaf that is the leftmost descendant of this node ' s child If deleteMax == true : deletes the right leaf and its parent replacing the parent with the parent ' s left child Returns the new root and an indicator whether the tree height decreased
fn delete_helper(
        &mut self,
        r_node: &NodeId,
        delete_max: bool,
        operation: &Operation,
        saved_node: &mut Option<NodeId>,
    ) -> (NodeId, bool) {
        self.on_node_visit(r_node, operation, false);
        let direction = if delete_max {
            1
        } else {
            self.replay_comparison()
        };
        if let Node::Internal(r) = self.tree().copy(r_node) {
            assert!(!(direction < 0 && r.left.borrow().is_leaf()));
            // If direction<0, this means we are not in deleteMax mode and we still haven't found
            // the value we are trying to delete
            // If the next step -- which is to the left -- is a leaf, then the value
            // we are looking for is not a key of any internal node in the tree,
            // which is impossible
            if direction >= 0 {
                if let Node::Leaf(right_child) = self.tree().copy(&r.right) {
                    // we delete this node and its right child (leaf)
                    // we return the left subtree
                    self.on_node_visit(&r.right, operation, false);
                    if delete_max {
                        // If we are in deleteMax mode,
                        // we should save the info of leaf we are deleting,
                        // because it will be copied over to its successor
                        *saved_node = Some(r.right);
                        return (r.left, true);
                    } else {
                        // Otherwise, we really are deleting the leaf, and therefore
                        // we need to change the nextLeafKey of its predecessor
                        assert!(direction == 0);
                        return (
                            self.change_next_leaf_key_of_max_node(
                                &r.left,
                                &right_child.next_node_key,
                                operation,
                            ),
                            true,
                        );
                    }
                }
            }
            if direction == 0 {
                if let Node::Leaf(left_child) = self.tree().copy(&r.left) {
                    // we know (r.left.isInstanceOf[Leaf])
                    // we delete the node and its left child (leaf); we return the right
                    // subtree, after changing the key and value stored in its leftmost leaf
                    self.on_node_visit(&r.left, operation, false);
                    return (
                        self.change_key_and_value_of_min_node(
                            &r.right,
                            &left_child.hdr.key.unwrap(),
                            &left_child.value,
                            operation,
                        ),
                        true,
                    );
                }
            }
            // Potential hard deletion cases:
            if direction <= 0 {
                // going left; know left child is not a leaf; deleteMax if and only if direction == 0
                let (new_left, child_height_decreased) =
                    self.delete_helper(&r.left, direction == 0, operation, saved_node);
                let new_root = if direction == 0 {
                    // this is the case where we needed to delete the min of the right
                    // subtree, but, because we had two non-leaf children,
                    // we instead deleted the node that was the max of the left subtree
                    // and are copying its info
                    let s = saved_node.take().unwrap();
                    let r_with_changed_key = InternalNode::update_key(r_node, &self.tree().key(&s));
                    let left = self.tree().left(&r_with_changed_key);
                    let right = self.tree().right(&r_with_changed_key);
                    let key = self.tree().key(&s);
                    let value = self.tree().value(&s);
                    InternalNode::update(
                        &r_with_changed_key,
                        &left,
                        &self.change_key_and_value_of_min_node(&right, &key, &value, operation),
                        self.tree().balance(&r_with_changed_key),
                    )
                } else {
                    r_node.clone()
                };
                let root_balance = self.tree().balance(&new_root);
                let root_right = self.tree().right(&new_root);
                if child_height_decreased && root_balance > 0 {
                    // new to rotate because my left subtree is shorter than my right
                    self.on_node_visit(&root_right, operation, true);
                    // I know my right child is not a leaf, because it is taller than my left
                    if let Node::Internal(right_child) = self.tree().copy(&root_right) {
                        if right_child.balance < 0 {
                            // double left rotate
                            // I know rightChild.left is not a leaf, because rightChild has a higher subtree on the left
                            self.on_node_visit(&right_child.left, operation, true);
                            (
                                self.double_left_rotate(&new_root, &new_left, &root_right),
                                true,
                            )
                        } else {
                            // single left rotate
                            let new_left_child = InternalNode::update(
                                &new_root,
                                &new_left,
                                &right_child.left,
                                1 - right_child.balance,
                            );
                            let new_rbalance = right_child.balance - 1;
                            let new_r = InternalNode::update(
                                &root_right,
                                &new_left_child,
                                &right_child.right,
                                new_rbalance,
                            );
                            (new_r, new_rbalance == 0)
                        }
                    } else {
                        panic!("Not internal node");
                    }
                } else {
                    // no rotation, just recalculate newRoot.balance and childHeightDecreased
                    let new_balance = if child_height_decreased {
                        root_balance + 1
                    } else {
                        root_balance
                    };
                    (
                        InternalNode::update(&new_root, &new_left, &root_right, new_balance),
                        child_height_decreased && new_balance == 0,
                    )
                }
            } else {
                // going right; know right child is not a leaf
                let (new_right, child_height_decreased) =
                    self.delete_helper(&r.right, delete_max, operation, saved_node);
                if child_height_decreased && r.balance < 0 {
                    // new to rotate because my right subtree is shorter than my left
                    self.on_node_visit(&r.left, operation, true);
                    // I know my left child is not a leaf, because it is taller than my right
                    if let Node::Internal(left_child) = self.tree().copy(&r.left) {
                        if left_child.balance > 0 {
                            // double right rotate
                            // I know leftChild.right is not a leaf, because leftChild has a higher subtree on the right
                            self.on_node_visit(&left_child.right, operation, true);
                            (self.double_right_rotate(r_node, &r.left, &new_right), true)
                        } else {
                            // single right rotate
                            let new_right_child = InternalNode::update(
                                r_node,
                                &left_child.right,
                                &new_right,
                                -left_child.balance - 1,
                            );
                            let new_rbalance = 1 + left_child.balance;
                            let new_r = InternalNode::update(
                                &r.left,
                                &left_child.left,
                                &new_right_child,
                                new_rbalance,
                            );
                            (new_r, new_rbalance == 0)
                        }
                    } else {
                        panic!("Not internal node");
                    }
                } else {
                    // no rotation, just recalculate r.balance and childHeightDecreased
                    let new_balance = if child_height_decreased {
                        r.balance - 1
                    } else {
                        r.balance
                    };
                    (
                        InternalNode::update(r_node, &r.left, &new_right, new_balance),
                        child_height_decreased && new_balance == 0,
                    )
                }
            }
        } else {
            panic!("Not internal node");
        }
    }
fn delete_helper ( & mut self , r_node : & NodeId , delete_max : bool , operation : & Operation , saved_node : & mut Option < NodeId > , ) -> ( NodeId , bool ) { self . on_node_visit ( r_node , operation , false ) ; let direction = if delete_max { 1 } else { self . replay_comparison ( ) } ; if let Node :: Internal ( r ) = self . tree ( ) . copy ( r_node ) { assert ! ( ( direction 0 r left borrow ( ) is_leaf ( ) ) ) ; // If direction<0, this means we are not in deleteMax mode and we still haven't found // the value we are trying to delete // If the next step -- which is to the left -- is a leaf, then the value // we are looking for is not a key of any internal node in the tree, // which is impossible if direction >= 0 { if let Node :: Leaf ( right_child ) = self . tree ( ) . copy ( & r . right ) { // we delete this node and its right child (leaf) // we return the left subtree self . on_node_visit ( & r . right , operation , false ) ; if delete_max { // If we are in deleteMax mode, // we should save the info of leaf we are deleting, // because it will be copied over to its successor * saved_node = Some ( r . right ) ; return ( r . left , true ) ; } else { // Otherwise, we really are deleting the leaf, and therefore // we need to change the nextLeafKey of its predecessor assert ! ( direction 0 ) ; return ( self . change_next_leaf_key_of_max_node ( & r . left , & right_child . next_node_key , operation , ) , true , ) ; } } } if direction == 0 { if let Node :: Leaf ( left_child ) = self . tree ( ) . copy ( & r . left ) { // we know (r.left.isInstanceOf[Leaf]) // we delete the node and its left child (leaf); we return the right // subtree, after changing the key and value stored in its leftmost leaf self . on_node_visit ( & r . left , operation , false ) ; return ( self . change_key_and_value_of_min_node ( & r . right , & left_child . hdr . key . unwrap ( ) , & left_child . value , operation , ) , true , ) ; } } // Potential hard deletion cases: if direction <= 0 { // going left; know left child is not a leaf; deleteMax if and only if direction == 0 let ( new_left , child_height_decreased ) = self . delete_helper ( & r . left , direction == 0 , operation , saved_node ) ; let new_root = if direction == 0 { // this is the case where we needed to delete the min of the right // subtree, but, because we had two non-leaf children, // we instead deleted the node that was the max of the left subtree // and are copying its info let s = saved_node . take ( ) . unwrap ( ) ; let r_with_changed_key = InternalNode :: update_key ( r_node , & self . tree ( ) . key ( & s ) ) ; let left = self . tree ( ) . left ( & r_with_changed_key ) ; let right = self . tree ( ) . right ( & r_with_changed_key ) ; let key = self . tree ( ) . key ( & s ) ; let value = self . tree ( ) . value ( & s ) ; InternalNode :: update ( & r_with_changed_key , & left , & self . change_key_and_value_of_min_node ( & right , & key , & value , operation ) , self . tree ( ) . balance ( & r_with_changed_key ) , ) } else { r_node . clone ( ) } ; let root_balance = self . tree ( ) . balance ( & new_root ) ; let root_right = self . tree ( ) . right ( & new_root ) ; if child_height_decreased && root_balance > 0 { // new to rotate because my left subtree is shorter than my right self . on_node_visit ( & root_right , operation , true ) ; // I know my right child is not a leaf, because it is taller than my left if let Node :: Internal ( right_child ) = self . tree ( ) . copy ( & root_right ) { if right_child . balance < 0 { // double left rotate // I know rightChild.left is not a leaf, because rightChild has a higher subtree on the left self . on_node_visit ( & right_child . left , operation , true ) ; ( self . double_left_rotate ( & new_root , & new_left , & root_right ) , true , ) } else { // single left rotate let new_left_child = InternalNode :: update ( & new_root , & new_left , & right_child . left , 1 - right_child . balance , ) ; let new_rbalance = right_child . balance - 1 ; let new_r = InternalNode :: update ( & root_right , & new_left_child , & right_child . right , new_rbalance , ) ; ( new_r , new_rbalance == 0 ) } } else { panic ! ( " " ) ; } } else { // no rotation, just recalculate newRoot.balance and childHeightDecreased let new_balance = if child_height_decreased { root_balance + 1 } else { root_balance } ; ( InternalNode :: update ( & new_root , & new_left , & root_right , new_balance ) , child_height_decreased && new_balance == 0 , ) } } else { // going right; know right child is not a leaf let ( new_right , child_height_decreased ) = self . delete_helper ( & r . right , delete_max , operation , saved_node ) ; if child_height_decreased && r . balance < 0 { // new to rotate because my right subtree is shorter than my left self . on_node_visit ( & r . left , operation , true ) ; // I know my left child is not a leaf, because it is taller than my right if let Node :: Internal ( left_child ) = self . tree ( ) . copy ( & r . left ) { if left_child . balance > 0 { // double right rotate // I know leftChild.right is not a leaf, because leftChild has a higher subtree on the right self . on_node_visit ( & left_child . right , operation , true ) ; ( self . double_right_rotate ( r_node , & r . left , & new_right ) , true ) } else { // single right rotate let new_right_child = InternalNode :: update ( r_node , & left_child . right , & new_right , - left_child . balance - 1 , ) ; let new_rbalance = 1 + left_child . balance ; let new_r = InternalNode :: update ( & r . left , & left_child . left , & new_right_child , new_rbalance , ) ; ( new_r , new_rbalance == 0 ) } } else { panic ! ( " " ) ; } } else { // no rotation, just recalculate r.balance and childHeightDecreased let new_balance = if child_height_decreased { r . balance - 1 } else { r . balance } ; ( InternalNode :: update ( r_node , & r . left , & new_right , new_balance ) , child_height_decreased && new_balance == 0 , ) } } } else { panic ! ( " " ) ; } }
Deletes the node in the subtree rooted at r and its corresponding leaf
as indicated by replayComparison or deleteMax.
Deletes the node in the subtree rooted at r and its corresponding leaf as indicated by replayComparison or deleteMax .
&mut self
r_node
&NodeId
delete_max
bool
operation
&Operation
saved_node
&mut Option<NodeId>