| 143 | |
| 144 | |
| 145 | alloc_node* predecessorSwap(alloc_node* del) |
| 146 | { |
| 147 | alloc_node* pred = del->left_; |
| 148 | alloc_node* predPrev = del; |
| 149 | |
| 150 | while (pred->right_) { |
| 151 | predPrev = pred; |
| 152 | pred = pred->right_; |
| 153 | } |
| 154 | if (predPrev == del) |
| 155 | predPrev->left_ = pred->left_; |
| 156 | else |
| 157 | predPrev->right_ = pred->left_; |
| 158 | |
| 159 | pred->left_ = del->left_; |
| 160 | pred->right_ = del->right_; |
| 161 | |
| 162 | return pred; |
| 163 | } |
| 164 | |
| 165 | |
| 166 | // iterative remove |