Bit Focus

找到节点
将节点移动到容易删除的位置
删除节点

找到节点与查询操作非常类似, 只不过, 正如插入元素过程中需要将路径上所有节点负载加上 1, 删除过程中, 也需要将节点路径上所有节点负载都减去 1.
下面是这一部分的实现

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 种情况

节点是叶子
节点只有一侧子树
节点两侧子树健全

前两种情况好办, 找到为空的一侧子树, 将另一侧子树接到父节点上, 然后删除当前节点即可. 也就是说当前已经处在容易删除的位置, 可以跳过一个中间步骤. (P 表示待删除节点的父节点)

	Back to Bit Focus
	NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
	About this site