二叉搜索树执行add(x)操作后再执行同值x的remove(x)操作，是否必然恢复为原树？

嘿，这个问题挺有意思的！答案是不一定，执行完add(x)再remove(x)后，二叉搜索树的结构未必能回到最初的状态，这得看你用的是哪种二叉搜索树：

• 如果是普通的、不做自平衡调整的二叉搜索树：插入x的时候，它会被放到唯一符合规则的叶子节点位置；删除x时，直接把这个叶子节点移除，父节点的对应指针置空，这时候树的结构就和操作前一模一样了。
• 但如果是自平衡二叉搜索树（比如AVL树、红黑树这类），情况就不一样了。插入x的时候，为了维持树的平衡，可能会触发旋转操作，这已经改变了原树的结构；之后删除x，虽然移除了刚插入的节点，但平衡调整的结果往往没法让树完全恢复到最初的样子。

给你举个AVL树的例子就清楚了：
原树结构：

3
   / \
  2   4
 /
1

插入x=0后，树出现失衡，会执行右旋操作，变成这个平衡结构：

2
   / \
  1   3
 /     \
0       4

删除x=0之后，树的结构变成这样：

2
   / \
  1   3
       \
        4

你看，这个结构和最开始的原树完全不一样了。

内容的提问来源于stack exchange，提问作者Abdullah naeem