C++ "destructive procedural variant"导致先前版本的二叉搜索树丢失

Question

我一直在审查 C++ 指针和引用，并想验证我是否理解以下来自 Wikipedia 的示例中“破坏性程序变体”的含义。 :

Here's how a typical binary search tree insertion might be performed in a binary tree in C++:

Node* insert(Node*& root, int key, int value) {
  if (!root) 
    root = new Node(key, value);
  else if (key < root->key)
    root->left = insert(root->left, key, value);
  else  // key >= root->key
    root->right = insert(root->right, key, value);
  return root;
}

The above destructive procedural variant modifies the tree in place. It uses only constant heap space (and the iterative version uses constant stack space as well), but the prior version of the tree is lost.

这里的重点(没有双关语意)是指当我们此处的指针被引用到一个新的 Node 对象时，可能还有“根”指针的其他拷贝仍然指向 NULL 值吗？

如果是，那么为什么要使用“树的先前版本丢失”这句话？ (在 C++ 中对此的简单解决方案不是确保没有人存储指向 NULL 二叉树的指针，或者确保他们存储对根指针的引用而不是它的拷贝吗？)

Answer 1

在维基百科条目的下方，Python 的行为作为一个对比示例被注明。在那里，您会看到向树“添加”一个节点实际上会创建一个带有额外节点的新树。因此在这种情况下仍然可以引用调用插入之前的树。

但是，在 C++ 示例中，当插入新节点时树结构会发生变化，并且先前的状态会丢失。