从二叉检索树中删除一个元素分多个步骤:
- 找到节点
- 将节点移动到容易删除的位置
- 删除节点
下面是这一部分的实现
void remove_by(key_type const& key)
{
remove_by_from(key, &root);
}
void remove_at(int position)
{
remove_at_from(position, &root);
}
static void remove_by_from(key_type const& key, node** parent)
{
--((*parent)->load);
if (key < (*parent)->t.key()) {
remove_by_from(key, &((*parent)->left));
return;
}
if ((*parent)->t.key() < key) {
remove_by_from(key, &((*parent)->right));
return;
}
remove(parent);
}
static void remove_at_from(int position, node** parent)
{
--((*parent)->load);
int left_load = (NULL == (*parent)->left) ? 0 : (*parent)->left->load;
if (position < left_load) {
remove_at_from(position, &((*parent)->left));
return;
}
if (left_load < position) {
position = position - left_load - 1;
remove_at_from(position, &((*parent)->right));
return;
}
remove(parent);
}
static void remove(node** n);
class binary_search_tree 旗下的. 与插入操作类似地, 这里需要的同样是节点的二级指针, 因为当节点从树中被移除时, 必然伴随着对其父节点对应的子树指针修改.找到了节点之后将会有下面 3 种情况
- 节点是叶子
- 节点只有一侧子树
- 节点两侧子树健全