探究二叉查找树

引言

二叉查找树（Binary Search Tree）又称为有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： (1) 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； (2) 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； (3) 任意节点的左、右子树也分别为二叉查找树。 (4) 任意节点的左子树和右子树深度之差不超过1。 以上四点称作是二叉查找树的性质。

二叉查找树的基本操作

二叉查找树主要有三个基本操作：插入，查找，删除。其中插入和查找的时间复杂度都是O(logn)，但是删除操作因为需要保证二叉查找树的性质，所以时间复杂度会稍微比较高。 在插入一个数据时，我们首先从根节点开始，将数据与该节点的值进行比较，如果插入的数据比该节点的值小，则继续从该节点的左子树找，否则从该节点的右子树中找。接着对比下一个节点，直到该节点为空，即可插入该数据。 而查找操作则是从根节点开始比较，如果要查找的数据与该节点的值相等，则直接返回该节点。如果要查找的数据比该节点的值小，则从左子树找，否则从右子树中找，知道该节点为空，即未找到该数据。 删除操作比较复杂，首先需要找到要删除的节点，然后需要保证删除后的树仍然是二叉查找树，因此需要分类讨论删除节点的情况，包括：1. 叶子节点 2. 只有一个子节点 3. 有两个子节点。具体操作可参见相关代码。

二叉查找树的应用

由于二叉查找树的方便查找以及插入操作均为O(logn)的时间复杂度，因此二叉查找树在计算机科学领域有很多应用，其中较为常见的是哈希表的实现，以及很多的搜索引擎，例如Lucene。 在哈希表的实现中，因为哈希表需要通过键值计算出数组下标，而哈希表中数组的下标是连续的，并不方便动态调整。因此我们需要使用二叉查找树来存储数据。由于二叉查找树的特点，我们可以保证树的高度在O(logn)的范围内，保证了查找性能。 在搜索引擎Lucene中，采用倒排索引的方式来存储数据。倒排索引的结构是：词项作为关键字，文档的ID和位置作为属性值。由于需要支持快速的查找，因此用一个支持O(logn)查找的数据结构(Binary Search Tree)来存储这些关键字会是一个很好的选择。