二叉搜索树

说明

在二叉树中插入和查找数字。

当我们需要表示有序数据时，数组并不是一种好的数据结构。

假设我们有数组 [1, 3, 4, 5]，往里面加入 2，它就变成了 [1, 3, 4, 5, 2]。 现在我们又得把整个数组重新排序一遍！ 我们可以改进一下：只需要为新元素腾出空间，即 [1, nil, 3, 4, 5]，然后把新元素放进腾出的那个空间里。 但这样做仍然需要把许多元素向下移动一位。

然而，二叉搜索树处理有序数据的效率要高得多。

二叉搜索树由一系列相互连接的节点组成。 每个节点包含一份数据（例如数字 3）、一个名为 left 的变量和一个名为 right 的变量。 left 和 right 变量指向 nil，或者指向其他节点。 由于这些其他节点下面又连着别的节点，我们说 left 和 right 变量指向的是子树。 左子树中的所有数据都小于或等于当前节点的数据，右子树中的所有数据都大于当前节点的数据。

例如，假设我们有一个包含数据 4 的节点，然后加入数据 2，树就会变成这样：

      4
     /
    2

如果接着加入 6，树就会变成这样：

      4
     / \
    2   6

如果接着加入 3，树就会变成这样。

       4
     /   \
    2     6
     \
      3

如果接着加入 1、5 和 7，树就会变成这样。

          4
        /   \
       /     \
      2       6
     / \     / \
    1   3   5   7

致谢

这些图片由 habere-et-dispertire 使用 Till Tantau 开发的 PGF/TikZ 制作。

实现

在 Cairo（或任何具有不可变内存的纯函数式语言）中实现高效且可修改的树结构颇具挑战，因为这类语言的设计目标就是避免在数据创建后更改数据。 这种不可变性意味着，你不能直接更新树节点，而必须在每次修改时创建树的新版本。

为了说明为什么会这样，想象一个简单的二叉树结构，其中每个节点都有一个左子节点和一个右子节点。 假设我们一开始有这样一棵小树：

       1
      / \
     2   3

现在，假设我们想添加一个新节点4，作为节点2的左子节点。 在纯函数式语言（如 Cairo 或 Haskell）中，内存是不可变的，所以我们不能简单地把节点4直接加到2上。 相反，我们必须为从根节点到被修改节点这条路径上的每个节点创建新版本，因为这条路径上的每个节点现在都指向一个新的或修改过的子树。

这个过程会像这样：

1. 将节点 4 添加到节点 2：

   • 创建节点2的新版本，现在它的左子节点是4。

       2'
      / 
     4   
   

2. 更新根节点：

   • 由于节点1最初指向旧的2，我们创建一个根节点1'的新版本，它现在在左侧指向更新后的节点2'，并在右侧保留节点3。

       1'
      / \
     2'  3
   

因此，得到的树变成：

       1'
      / \
     2'  3
    /
   4

这棵新树（1'）仍然与原树相似，只是路径更新了。 关键在于，为了保持不可变性，我们必须重新创建路径上的每个节点（从1到2），因为现有节点无法就地修改。 原始树仍然存在（例如，对于所有指向其原始根节点1的引用），而这棵新树表示修改后的状态。

在大型树中，这种方法可能会变得开销很大，因为每次新的修改都需要重新创建从根节点到更新节点的节点路径，即使树中只有一小部分实际发生了变化。