这一节我们来看看二叉树基础下，主要讲二叉查找树的操作。
前一讲我们讲了最基础的二叉树的一些常规操作。这一节我们来看看二叉查找树。它最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。
之前我们讲散列表的时候有说到，它也支持这些操作，而且时间复杂度还是O(1)。那既然有了这么高效的散列表，使用二叉树的地方是不是都可以用散列表来替换呢？他们的区别在哪里？下面我们就来看看。
二叉查找树(Binary Search Tree)
二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值要小于这个节点值，而右子树节点的值都大于这个节点的值。像这样：
现在我们来看看，它是来看看它的查找、插入和删除操作。
1. 查找操作
从定义中可以看出，对于任意一个节点，它的左子树中的节点都是比它小的，右子树中的节点都是比它大的。我们先取根节点，如果等于要查找的数据，就直接返回。如果比根节点小，那就去根节点的左子树里找，相反就去右子树里找。
代码实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29// 二叉查找树——查找
public class BinarySerachTree {
private Node tree;
public Node find(int data) {
Node p = tree;
while(p != null) {
if(data < p.data) {
p = p.left;
} else if(data > p.data) {
p = p.right;
} else {
return p;
}
}
return null;
}
public static class Node {
private int data;
private Node left;
private Node right;
public Node(int data) {
this.data = data;
}
}
}
2. 插入操作
和查找类似，新插入一个数据一般都是在叶子节点上。所以，我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。
如果待插入数据比节点的数据大，并且节点的右子树为空，就将待插入的数据放在这个节点的右节点的位置，如果不为空就继续递归遍历右子树，查找插入位置。如果带插入数据比节点小，那就从左边遍历，查找插入位置。
代码实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24// 二叉查找树——插入
public void insert(int data) {
if(tree == null) {
tree = new Node(data);
return ;
}
Node p = tree;
while(p != null) {
if(data > p.data) {
if(p.right == null) {
p.right = new Node(data);
return ;
}
p = p.right;
} else {
if(p.left == null) {
p.left = new Node(data);
return ;
}
p = p.left;
}
}
}
3. 删除操作
二叉查找树的删除操作相对前面两种操作要稍微麻烦一些。针对要删除节点的子节点个数的不同，我们需要分三种情况来处理。
第一种，也是最简单的情况。如果删除的节点没有子节点，我们只需要直接将父节点指向要删除节点的指针置为null就可以了。
第二种情况是，如果要删除的节点只有一个子节点，那我们只需要更新父节点中指向要删除节点的指针，让它指向要删除节点的子节点就行。
第三种情况是，要删除的节点有两个子节点。我们需要找到这个节点的右子树中最小节点，把它替换到要删除的节点上。然后再删除掉刚刚查找到的最小节点(指的是最小节点位置的指针要置为null)。
代码实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51// 二叉查找树——删除
public void delete(int data) {
Node p = tree; // 指向要删除的节点，初始化时指向根节点
Node fp = null; // p的父节点
// 要删除的节点没有子节点
while(p != null && p.data != data) {
fp = p;
if(data > p.data) {
p = p.right;
} else {
p = p.left;
}
}
if(p == null) {
return;
}
// 删除节点是叶子节点或者仅有一个子节点
Node child;
if(p.left != null) {
child = p.left;
} else if(p.right != null) {
child = p.right;
} else {
child = null;
}
if(fp == null) {
tree = child;
} else if(fp.left == p) {
fp.left = child;
} else {
fp.right = child;
}
// 要删除的节点有两个子节点
if(p.left != null && p.right != null) {
Node minP = p.right; // 右子树中最小节点
Node minFp = p; // minP的父节点
while(minP.left != null) {
minFp = minP;
minP = minP.left;
}
p.data = minP.data;
p = minP;
fp = minFP;
}
}
实际上，关于二叉查找树的删除操作，还有一个非常简单、取巧的方法，就是单纯将要删除的节点标记为“deleted”，但不真正从树中删除这个节点。但是这样做会比较浪费内存空间。
二叉查找树的其它操作
除了插入、删除、查找操作之外，二叉查找树还可以支持 快速得查找最大节点、最小节点、前驱结点和后继节点。
二叉查找树除了支持上面几个操作之外，还有一个重要得特性，就是 中序遍历二叉查找树，可以输出有序得数据序列，时间复杂度是O(n)，非常高效。因此，二叉查找树也叫二叉排序树。
支持重复数据的二叉查找树
前面我们举的例子中，都是默认数据是不重复的。但是在实际得开发中，我们往往存储得是包含很多字段的对象。我们利用某一个字段作为键值来构建二叉树。
当键值相同的时候，我们应该怎么处理呢？我们有两种方法。
第一种，二叉查找树中，每一个节点不仅会存储一个数据，我们通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
第二种，每一个节点仍然只存一个数据。在查找插入位置的过程中，如果碰到一个节点值与插入数据相同，那我们就将这个待插入数据放到这个节点的右子树中(把它当作比它大的值来处理)。
当然，这就意味着，当我们查找某一个数据的时候，当已经查到与当前节点数据相等的时候不能停止查找，要去它的右子树中继续遍历查找，直到遇到叶子节点才停止。删除也是。
二叉查找树的时间复杂度分析
从图中可以看出来，不管是插入还是删除亦或是查找，它的时间复杂度都与树的高度有关，与高度成正比，也就是O(height)。那么，一棵包含n个节点的完全二叉树的高度怎么计算呢？
树的高度就等于最大层数减一，为了方便计算，我们转换成层来表示。从下图中，我们可以看到，包含n个节点的完全二叉树中，从第一层到倒数第二层的节点数都满足等比，1, 2, 2^2, 2^3 … 2^(k - 1)。设树的最大层数为L，又有，最大层数的节点数在区间 [1, 2^(L-1)]之间，于是L和n满足这样一个关系：1
2n >= 1 + 2 + 4 + 8 + ... + 2^(L-2) + 1
n <= 1 + 2 + 4 + 8 + ... + 2^(L-2) + 2^(L-1)
借助等比求和，我们可以计算出L的范围是 [log(2)(n + 1), log(2)n + 1]。完全二叉树的层数小于log(2)n + 1。所以，它的时间复杂度是O(logn)。
其实，对于这种时间复杂度我们可以直接估算。观察到，每进行一次操作，剩余的数据量都会在原来的基础上大致减半，这样的操作时间复杂度一般就可以认定为O(logn)了(看到等比求指数，大概率就是logn了 :)。当然，也不能忽略指数的表示形式啦，不然最后变成了nlogn就很尴尬了)。
解答开篇
散列表和二叉查找树比较：
第一、散列表中的数据是无序存储的，如果要输出有序数据需要先对数据进行排序。而对于二叉查找树，中序遍历即可以在O(n)的时间复杂度内输出有序数据。
第二，散列表扩容耗时多，而且当遇到散列冲突时，性能不稳定。虽然二叉查找树有时也会退化成链表影响性能，但是我们常用的平衡二叉查找树的性能非常稳定，时间复杂度是O(logn)。
第三，笼统的讲，尽管散列表的查找等操作的时间复杂度是常量级的，但是因为存在冲突，所以这个常量不一定比logn小。
第四，散列表的构造比二叉查找树要复杂的多，需要考虑很多问题。比如散列函数的设计、冲突的解决方法、扩容缩容等问题。而相比之下，二叉查找树就要乖巧的多了。
最后，为了避免过多的散列冲突，散列表的装载因此也要合适。
课后问题
今天我讲了二叉树高度的理论分析方法，给出了粗略的数量级。如何通过编程，求出一棵给定二叉树的确切高度呢？
@失火的夏天
确定二叉树高度有两种思路：第一种是深度优先思想的递归，分别求左右子树的高度。当前节点的高度就是左右子树中较大的那个+1；第二种可以采用层次遍历的方式，每一层记录都记录下当前队列的长度，这个是队尾，每一层队头从0开始。然后每遍历一个元素，队头下标+1。直到队头下标等于队尾下标。这个时候表示当前层遍历完成。每一层刚开始遍历的时候，树的高度+1。最后队列为空，就能得到树的高度。
@拉欧
递归法，根节点高度 = max(左子树高度，右子树高度) + 1
有问题？发送 issues 给我~