image-20211130192402269

实现 contains、findMax、findMin

  • contains:递归判断。
  • findMax/findMin:往左走到头可以找到最小值,往右走到头可以找到最大值。用非递归也很容易实现。

实现 insert

x 插入 t 的代码如下:上面是普通插入,下面是针对右值的插入。

/**
 * Internal method to insert into a subtree.
 * x is the item to insert.
 * t is the node that roots the subtree.
 * Set the new root of the subtree.*/
void insert(const Comparable &x, BinaryNode *&t) {
  if (t == nullptr)
    t = new BinaryNode{x, nullptr, nullptr};
  else if (x < t->element)
    insert(x, t->left);
  else if (t->element < x)
    insert(x, t->right);
  else
    ; // Duplicate; do nothing
}
/**
 * Internal method to insert into a subtree.
 * x is the item to insert by moving.
 * t is the node that roots the subtree.
 * Set the new root of the subtree.
 */
void insert(Comparable &&x, BinaryNode *&t) {
  if (t == nullptr)
    t = new BinaryNode{std::move(x), nullptr, nullptr};
  else if (x < t->element)
    insert(std::move(x), t->left);
  else if (t->element < x)
    insert(std::move(x), t->right);
  else
    ; // Duplicate; do nothing
}

代码中的 Comparable 是树中数据泛型名。

右值:无名称的值,表达式结束后就不存在。详见脚注 (2) (3)

&& 表示对右值的引用。

可以看到插入条件是 t == nullptr,相当于进行一次失败的查找,然后在失败位置插入。

实现 delete

delete 稍显复杂。对于被删除元素

1)若无子节点,则直接删除即可。

2)若有一个子节点,则要先假定被删元素已被删,重新建立其亲节点与其子节点的关系(如下图,删除 4 的情况)

image-20211130194543868

2)若有两个子节点。如下图删除 2 的情况。这时候:

  1. 首先将 2 替换为 2 的右子树上的最小元素 3
  2. 从右子树上删除 3

image-20211130194602859

延迟删除(lazy deletion)策略:即只是标记为删除(并不真的删除),对于可重复的情况,每个节点都有一个 counter,这样就允许 counter 暂时为 0.

那么什么时候真的删除呢?可以采用策略:当树的名义大小 $\leq$ 已删除的大小,即被删除的数据甚至比实际有的数据还多的时候,执行真删除。

参考

(1) 数据结构与算法 C++ 语言实现

(2) C++ 右值引用(std::move) - 知乎 (zhihu.com)

(3) 一次性搞定右值,右值引用(&&),和 move 语义 - 掘金 (juejin.cn) (推荐)