数据频繁变化的情况下，如何高效检索？ _高效检索

当我们在电脑中查找文件的时候，我们一般习惯先打开相应的磁盘，再打开文件夹以及子文件夹，最后找到我们需要的文件。这其实就是一个检索路径。如果把所有的文件展开，这个查找路径其实是一个树状结构，也就是一个非线性结构，而不是一个所有文件平铺排列的线性结构。

文章插图
树状结构：文件组织例子
我们都知道，有层次的文件组织肯定比散乱平铺的文件更容易找到。这样熟悉的一个场景，是不是会给你一个启发：对于零散的数据，非线性的树状结构是否可以帮我们提高检索效率呢？
另一方面，我们也知道，在数据频繁更新的场景中，连续存储的有序数组并不是最合适的存储方案。因为数组为了保持有序必须不停地重建和排序，系统检索性能就会急剧下降。但是，非连续存储的有序链表倒是具有高效插入新数据的能力。因此，我们能否结合上面的例子，使用非线性的树状结构来改造有序链表，让链表也具有二分查找的能力呢？
一、树结构是如何进行二分查找的？之前就和大家分享过，因为链表并不具备“随机访问”的特点，所以二分查找无法生效。当链表想要访问中间的元素时，我们必须从链表头开始，沿着指针一步一步遍历，需要遍历一半的节点才能到达中间节点，时间代价是 O(n/2) 。而有序数组由于可以“随机访问”，因此只需要 O(1) 的时间代价就可以访问到中间节点了。
那如果我们能在链表中以 O(1) 的时间代价快速访问到中间节点，是不是就可以和有序数组一样使用二分查找了？你先想想看该怎么做，然后我们一起来试着改造一下。

文章插图
直接记录和访问中间节点
既然我们希望能以 O(1) 的时间代价访问中间节点，那将这个节点直接记录下来是不是就可以了？因此，如果我们把中间节点 M 拎出来单独记录，那我们的第一步操作就是直接访问这个中间节点，然后判断这个节点和要查找的元素是否相等。如果相等，则返回查询结果。如果节点元素大于要查找的元素，那我们就到左边的部分继续查找；反之，则在右边部分继续查找。
对于左边或者右边的部分，我们可以将它们视为两个独立的子链表，依然沿用这个逻辑。如果想用 O(1) 的时间代价就能访问这两个子链表的中间节点，我们就应该把左边的中间节点L 和右边的中间节点 R，单独拎出来记录。
并且，由于我们是在访问完了 M 节点以后，才决定接下来该去访问左边的 L 还是右边的R 。因此，我们需要将 L 和 M，R 和 M 连接起来。我们可以让 M 带有两个指针，一个左指针指向 L，一个右指针指向 R 。这样，在访问 M 以后，一旦发现 M 不是我们要查找的节点，那么，我们接下来就可以通过指针快速访问到 L 或者 R 了。

文章插图
将 M 节点改为带两个指针，指向 L 节点和 R 节点
对于其余的节点，我们也可以进行同样的处理。下面这个结构，你是不是很熟悉？没错，这就是我们常见的二叉树。你可以再观察一下，这个二叉树和普通的二叉树有什么不一样？

文章插图
二叉检索树结构
没错，这个二叉树是有序的。它的左子树的所有节点的值都小于根节点，同时右子树所有节点的值都大于等于根节点。这样的有序结构，使得它能使用二分查找算法，快速地过滤掉一半的数据。具备了这样特点的二叉树，就是二叉检索树（Binary Search Tree），或者叫二叉排序树（Binary Sorted Tree）。
讲到这里，不知道你有没有发现，尽管有序数组和二叉检索树，在数据结构形态上看起来差异很大，但是在提高检索效率上，它们的核心原理都是一致的。那么，它们是如何提高检索效率的呢？核心原理又一致在哪里呢？接下来，我们就从两个主要方面来看。