二叉查找树（英语：Binary Search Tree, 后文中简称 BST）, 也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree）, 是在 20 世纪 60 年代为解决标记数据的高效存储问题而设计的, 由 Conway Berners-Lee 和 David Wheeler 发明.

具体指的是一棵空树或者具有下列性质的二叉树:

1. 若任意节点的左子树不空, 则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空, 则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；

简单来说, 二叉搜索树中的每一个节点都满足: 左子树中的所有元素均小于该节点元素; 右子树中的所有元素均大于该节点元素. 左子树元素≤本节点元素≤右子树元素左子树元素≤本节点元素≤右子树元素. 左小右大.

这种结构上的设计使得 BST 可以以二分查找思路实现 Ω(logn)Ω(log⁡n) （不是大o, 而是下限在logn）级别的快速增, 删, 查等操作, 因为在树中的每一步操作都能排除一半的元素. 完成一颗二叉搜索树的建立之后, 我们还可以以中序遍历的方式得到排序后的序列, 这也是二叉搜索树被称为排序二叉树的原因.

需要注意的是, 二叉搜索树的效率与在建立时输入的元素顺序有很大的关系. 在最坏情况下, 二叉搜索树会退化成链表. 树层数大大增加使得查找等操作需要消耗更多的时间）此时, 需要对树进行额外的优化 - 平衡, 来保证高效的运行效率. 在本文中我们不作讨论, 本文仅介绍朴素的二叉搜索树.

如果看完之后还是不太理解的话, 可以看看这个美国旧金山大学CS做的一个算法可视化. Binary Search Tree Visualization (usfca.edu) 在这个网站上详细地看到 BST 每一步的操作. 做的很好, 不妨去玩玩!