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

Question

我一直在查看 C++ 指针和引用，并想验证我是否理解以下示例中 "destructive procedural variant" 的含义 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.

这里的重点（没有双关语意）是否可能存在 "root" 指针的其他副本，当我们此处的指针被引用到新的 Node 对象时，它们仍将指向 NULL 值？

如果是，那为什么要用"the prior version of the tree is lost"？（在 C++ 中对此的一个简单解决方案难道不是确保没有人存储指向 NULL 二叉树的指针，或者确保他们存储对根指针的引用而不是它的副本吗？）

Answer 1

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

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

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

C++ "destructive procedural variant" results in prior version of binary search tree being lost

c++

algorithm

pointers

reference

binary-search-tree