从二叉检索树中删除一个元素分多个步骤:
- 找到节点
- 将节点移动到容易删除的位置
- 删除节点
下面是这一部分的实现
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 | +---+
+---+ | P |
| +---+
V |
+---+ ------> V
| X | ---
+---+ =
/ \
--- ---
= =
+---+
| P | +---+
+---+ | P |
| +---+
V |
+---+ |
| X | ------> V
+---+ .
/ \ / \
/ \ --- / L \
/ L \ = '-----'
'-----'
static void remove(node** n)
{
if (NULL == (*n)->right) {
node* rm = *n;
(*n) = (*n)->left;
delete rm;
return;
}
if (NULL == (*n)->left) {
node* rm = *n;
(*n) = (*n)->right;
delete rm;
return;
}
rm_after_find_slot(n);
}
static void rm_after_find_slot(node** n);
class binary_search_tree 的成员.找个合适的位置也并不是什么难事. 比如, 可以找节点左子树的最右侧节点, 让这个替死鬼跟当前节点进行元素交换. 此时, 树的键序会被破坏, 但仅限于即将被删除的元素. 并且, 删除将会被转换为有一侧 (必然是右侧) 子树为空的情况.
+---+ +---+ +---+
| X | | S | | S |
+---+ +---+ +---+
/ \ / \ / \
/ \ / \ / \
/ \ / \ / \ / \ / \ / \
/ L \ / R \ / L \ / R \ / L \ / R \
'-----' '-----' ----> '-----' '-----' ----> '-----' '-----'
/ \ / \ / \
/ . / . / .
/ \ . / \ . / \ .
/ \ . / \ . / \ .
'-----' . '-----' . '-----' .
+---+ +---+ /\
| S | | X | / \
+---+ +---+ / SL \
/ \ / \ '------'
/\ --- /\ ---
/ \ = / \ =
/ SL \ / SL \
'------' '------'
static void rm_after_find_slot(node** n)
{
node** most_right_in_left = &((*n)->left);
while (NULL != (*most_right_in_left)->right) {
--((*most_right_in_left)->load);
most_right_in_left = &((*most_right_in_left)->right);
}
std::swap((*n)->t, (*most_right_in_left)->t);
remove(most_right_in_left); // recursively call remove
}
理想情况下, 具有 N 个节点的二叉检索树的高度是 log2N, 因此在树中查询元素和随机访问, 添加节点, 删除节点的平均时间开销都将是对数, 与向堆中添加任意元素, 删除极值元素相同, 略大于堆维护极值元素 (常数时间), 但功能简直多得爆表了. 计算机不变魔法, 多功能和高性能必然伴随代价, 代价首先体现在空间开销, 由于堆的底层用个数组就好了, 因此存多少元素就用多少空间, 而二叉树节点则肩负各种关系指针和负载计数, 有额外空间消耗. 此外, 堆还得益于数组的连续存储特性, 在缓存命中啥的将有极大的优势.
说到缓存, 顺带提一下 B-tree. 将二叉树拓展一下, 设想数据结构 X 叉树, 每个节点中有至多 X - 1 元素, 至多 X 个子树, 并且第 K 个子树中任何元素的值小于节点中第 K 个元素的值, 而第 K 个元素的值小于第 K + 1 个子树中任意元素的值 (如下图, 一棵 4 叉树)
+------------+
| 3 7 19 |
+---+---+----+
.--------' / \ `----------.
+---------+ +---------+ +------------+ +--------+
| 0 1 2 | | 4 5 6 | | 11 14 16 | | 20 21 |
+---------+ +---------+ +---+--------+ +--------+
/ |
+--------+ +-------+
| 8 9 10 | | 12 13 |
+--------+ +-------+