blocks/manu343726/edalib/TreeMap.h
/**
     * Erases a node, promoting and reordering children as needed
     * so as to return a tree that is ordered, with only the
     * deleted node missing.
     * @param n node to erase
     * @return a descendant of n, with its own children reordered so that
     * it forms a valid sorted binary tree.
     */
Erases a node, promoting and reordering children as needed
so as to return a tree that is ordered, with only the
deleted node missing.
@param n node to erase
@return a descendant of n, with its own children reordered so that
it forms a valid sorted binary tree.
Erases a node promoting and reordering children as needed so as to return a tree that is ordered with only the deleted node missing . @param n node to erase @return a descendant of n with its own children reordered so that it forms a valid sorted binary tree .
static Node *_erase(Node *n) {
        Node *replacement;
        if ( ! n->_left) {
            replacement = n->_right;
        } else if ( ! n->_right) {
            replacement = n->_left;
        } else {
            Node *parentOfSmallest = 0;
            Node *smallest = n->_right;
            while (smallest->_left) {
                parentOfSmallest = smallest;
                smallest = smallest->_left;
            }
            if (parentOfSmallest) {
                parentOfSmallest->_left = smallest->_right;
                smallest->_left = n->_left;
                smallest->_right = n->_right;
            } else {
                smallest->_left = n->_left;
            }
            replacement = smallest;
        }
        delete n;
        return replacement;
    }
static Node * _erase ( Node * n ) { Node * replacement ; if ( ! n -> _left ) { replacement = n -> _right ; } else if ( ! n -> _right ) { replacement = n -> _left ; } else { Node * parentOfSmallest = 0 ; Node * smallest = n -> _right ; while ( smallest -> _left ) { parentOfSmallest = smallest ; smallest = smallest -> _left ; } if ( parentOfSmallest ) { parentOfSmallest -> _left = smallest -> _right ; smallest -> _left = n -> _left ; smallest -> _right = n -> _right ; } else { smallest -> _left = n -> _left ; } replacement = smallest ; } delete n ; return replacement ; }
Erases a node, promoting and reordering children as needed
 so as to return a tree that is ordered, with only the
 deleted node missing.
Erases a node promoting and reordering children as needed so as to return a tree that is ordered with only the deleted node missing .
// easy, promote the right child // easy, promote the left child // interesting; promote the smallest-of-right // (largest-of-left would also have worked) // smallest has a parent; disconnect smallest // smallest is n->_right; no need to disconnect