作者：
lufficc
原文：https://lufficc.com/blog/binary-search-tree
（
点击文末阅读原文即可前往
）
在计算机科学中，二叉搜索树（Binary Search Tree）（有时称为有序或排序的二叉树）是一种能存储特定数据类型的容器。二叉搜索树允许快速查找、添加或者删除某一个节点，并且它是动态的集合。
二叉搜索树按照关键字顺序地保存节点，因此查找和其他操作可以使用二叉搜索原理：当在树（或者寻找插入新节点的地方）中查找节点时，它从根节点遍历到叶节点，与每个节点的关键字进行比较，然后基于比较结果，决定继续在左子树或者右子树中进行搜索。平均而言，每次比较将跳过树的大约一半的元素，这使得每次查找，插入或删除一个节点所花费的时间与树的节点个数的对数成（树的高度）正比，比线性表的性能要好很多。
定义
二叉搜索树是以一棵二叉树来组织，每个节点就是一个对象，包括key、卫星数据，除此之外还包括一些为了维持树结构所需要的信息：left、right、parent，分别指向左孩子、右孩子、父节点。其中如果孩子节点或者父节点不存在时，用NIL表示。根节点是树中唯一一个父节点为NIL的节点。
二叉搜索树具有以下性质：
1、如果节点的左子树不空，则左子树上所有结点的值均小于等于它的根结点的值；
2、如果节点的右子树不空，则右子树上所有结点的值均大于等于它的根结点的值；
3、任意节点的左、右子树也分别为二叉查找树；
比如在上图中根节点的关键字为6，左子树有关键字2、4和5，均不大于6；右子树有关键字7和8，均不小于6。这个性质对树中的每个节点都成立，也就是说，二叉搜索树的定义是递归的。
在讨论二叉搜索树的操作之前，先看看二叉搜索树的遍历。二叉搜索树可以使用先序遍历（preorder tree walk）、中序遍历（inorder tree walk）和后序遍历（postorder tree walk）。这样命名的依据是根据输出关键字相对于左右子树的位置。以中序遍历为例，伪代码如下：
INORDER-TREE-WALK(x)
if x != nil // 如果节点不为空
INORDER-TREE-WALK(x.left) // 首先递归地遍历左孩子，直到左孩子为空
print x.key // 输出当前节点（显然第一次运行到这里时，它是最小值，因为它是整棵树的最左节点）
INORDER-TREE-WALK(x.right) // 递归地遍历右孩子
对于上图中的二叉搜索树，动态过程如下，这样输出结果为：2，4，5，6，7，8，即按照从小到大的顺序排列。因为输出时一直遍历左孩子，知道遇到第一个左孩子为空的节点，将它输出，然后出栈返回继续输出。
查询
二叉搜索树还应该可以完成MINIMUM，MAXIMUM，SUCCESSOR和PREDECESSOR操作，即求最小值，最大值，后继和前驱，并且这些操作都可以在o(lgn)的时间内完成。
查找指定关键字
TREE-SEARCH操作在二叉树中查找一个具有指定的关键字的节点，输入树的根节点指针和关键字k，如果存在，返回节点指针，否则，返回nil。
TREE-SEARCH(x, k)
if x == nil or k == x.key //如不存在或者找到，直接返回
return x
if k < x.key //如果小于当前节点，根据性质，在左子树中搜索
return TREE-SEARCH(x.left, k)
else //如果大于等于当前节点，根据性质，在右子树中搜索
return TREE-SEARCH(x.right, k)
比如查找关键字为5的节点，首先从根节点6开始，与5进行比较，因为5小于6，因此在节点6的左子树继续搜索。到达节点4时因为5大于4，所以在4节点的右子树搜索，这样就顺利找到了节点5，此时函数将返回指向节点5的指针。如果找不到目标节点，TREE-SEARCH函数将返回nil。整个搜索过程如下：
最小/最大关键字
通过从树根开始，沿着left孩子向下搜索，直到遇到nil，那么根据二叉搜索树的性质，如果节点x没有左子树，而x的右子树的关键字肯定都大于x.key，因此此时当前节点一定是整个树中的最小值。
TREE-MINIMUM(x)
while x.left != nil // 沿着左子树一直深入搜索下去，直到遇到左子树为空的节点，此时当前节点为最小值
x = x.left
return x
同理，最大关键字的伪代码如下：
TREE-MAXIMUM(x)
while x.right != nil // 沿着右子树一直深入搜索下去，直到遇到右子树为空的节点，此时当前节点为最大值
x = x.right
return x
求取最大、最小关键字的时间复杂度仅为o(lgn)，即与树的高度成正比，因为查找过程自上而下形成一条线，线的最大长度为数的高度，如求取最小值的过程：
前驱/后继
给定二叉搜索树的一个节点，有事需要按照中序遍历的次序查找它的后继，如果所有的关键字互不相同，则一个节点x的后继一定是大于x.key的最小关键字。
TREE-SUCCESSOR(x)
if x.right != nil //case 1:如果右子树不为空，则后继一定是右子树的最小值，即大于x的最小值（右子树的值都大于x节点）
return TREE-MINIMUM(x.right)
y = x.p // case 2:右子树为空时
while y != nil and x == y.right
x = y // 变量x代表节点原始x的祖先，如果找到x，它是父节点的左孩子，则循环终止
y = y.p // y 代表节点x的父节点，如果x是y的左孩子，循环终止，并且返回y
return y
1、对于第一种情况比较简单，如果x右子树不为空，那它的后继就是右子树的最左节点，对应伪代码case 1，例如下图寻找68的后继，即寻找68的右子树的最小节点72，同时它也是右子树的最左节点。
2、第二种情况是x的右子树为空，注意x的后继始终是大于x的最小值（或者不存在），所以当x的右子树不存在时大于x的最小值在哪儿呢？我们只需要简单的从x开始沿树而上，找到第一个这样一个节点：它的父节点为空（即根节点）或者它的左孩子是x节点的祖先节点（不一定是直接祖先）。例如下图中为了寻找17的后继，沿着树上升，首先以此遇到了节点13，11，它们均不符合条件，因为它们不是父节点的左孩子。当遇到节点10时，此时x指向节点10，y指向节点19，并且节点10是节点19的左孩子，符合条件，所以返回节点y，它是节点x的后继。
再举一个例子，下图为了找15的后继，仍然沿着树上升，直到遇到节点10（此时伪代码中的变量x指向节点10）：它是15的祖先，而且是左孩子。所以此时返回节点10的父节点19，即节点15的后继。
一个二叉搜索树中除了最大节点外，都有后继。对于前驱节点，和后继节点原理一样，这里不再赘述。
插入
插入操作会引起二叉搜索树集合的动态变化，因此需要一定的修改来维持二叉搜索树。由于二叉搜索树的性质，即左孩子小于等于父节点，右孩子大于等于父节点，因此插入操作相对简单。
将一个节点插入到二叉搜索树中，需要调用TREE-INSERT，该过程以节点z作为输入，其中z.left = nil, z.right = nil, z.key = 将要插入数据的关键字：
TREE-INSERT(T, z)
y = nil
x = T.root
while x != nil //循环结束后，x一定为空，此时x即为节点z要插入的地方
y = x //在这里给y赋值，保证循环结束后y始终是x的父节点
if z.key < x.key
x = x.left
else
x = x.right
z.p = y // y始终是x的父节点，为了插入z，需要让z的父节点指向x的父节点，即指向y
if
