二叉查找树：树中的任意一个节点，它的左子树节点的值都小于该节点的值，它的右子树节点的值都大于该节点的值。
图例如下：
二叉查找树-查找
获取根节点，如果根节点为空，如果根节点的值等于该值，则返回根节点。如果该值小于根节点，则在根节点的左子树中递归查找。如果该值大于根节点，则在根节点的右子树中递归查找。
代码如下：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//树节点
class TreeNode{
int data;
TreeNode leftNode;
TreeNode rightNode;
public TreeNode(int data){
this.data = data;
}
//二叉查找树查询
public static TreeNode selectTreeNode(TreeNode tree, int val){
TreeNode node = tree;
if(node.data == val){
return node;
}
while(node != null && node.data != val){
if(val > node.data){
node = node.rightNode;
}else if(val < node.data){
node = node.leftNode;
}else{
return node;
}
}
return 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//树节点
class TreeNode{
int data;
TreeNode leftNode;
TreeNode rightNode;
public TreeNode(int data){
this.data = data;
}
//二叉查找树插入节点
public static TreeNode insertTreeNode(TreeNode tree, int val){
TreeNode node = tree;
while(node != null){
if(val > node.data){
if(node.rightNode == null){
node.rightNode = new TreeNode(val);
}else{
node = node.rightNode;
}
}
if(val < node.data){
if(node.leftNode == null){
node.leftNode = new TreeNode(val);
}else{
node = node.leftNode;
}
}
}
return null;
}
补充：删除插入节点的方法只针对于插入无重复值的节点。
二叉查找树-删除
删除节点时分以下三种情况：
1：如果被删除节点分别左右子节点的时候，需要查找到该节点的右子书的最小节点，将其值付给该节点，并删除这个最小节点。
2：被删除节点有一个子节点的时候，该节点的父节点直接指向子节点。
3：被删除节点没有节点的时候，该节点的父节点指向 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68//树节点
class TreeNode{
int data;
TreeNode leftNode;
TreeNode rightNode;
public TreeNode(int data){
this.data = data;
}
//删除节点
public static TreeNode deleteTreeNode(TreeNode tree,int val){
TreeNode p = tree;//要删除的节点
TreeNode pp = null;//p 节点的父节点
while(p != null && p.data != val){
pp = p;
if(val > p.data){
p = p.rightNode;
}
if(val < p.data){
p = p.leftNode;
}
}
if(p == null){
return null;//没有找到要删除的节点
}
//删除有左右子节点的节点
if(p.leftNode != null && p.rightNode != null){
TreeNode minp = p;//要删除的节点
TreeNode minpp = p;//minp 节点的父节点
while(minp.leftNode != null){
minpp = minp;
minp = minp.leftNode;
}
/**
* 此处将查找到的右子树最小节点的值赋值给 p 节点的数据域。
* 然后 p 节点指向 minp 节点，pp 节点指向 minpp 节点
* 原先删除有左右子节点的节点问题，变成了删除没有子节点的节点
*/
p.data = minp.data;
p = minp;
pp = minpp;
}
/**
* 删除只有一个子节点和没有子节点的节点
* (删除有左右子节点的节点那部分删除逻辑也放在这里执行了)
*/
TreeNode child;
if(p.leftNode != null){
child = p.leftNode;
}else if(p.rightNode != null){
child = p.rightNode;
}else{
child = null;
}
if(pp == null){//删除的是根节点
tree = child;
}else if(pp.leftNode == p){
pp.leftNode = child;
}else{
pp.rightNode = child;
}
return p;
}
}
二叉查找树的其他操作
查找最大值的节点：从根节点开始递归查找右子节点，直到找到叶子节点，该节点就是值最大的节点。
查找最小值的节点：从根节点开始递归查找左子节点，直到找到叶子节点，该节点就是值最小的节点。
中序遍历输出二叉查找树的节点，正好是按照值从小到大的顺序输出。
支持重复数据的二叉查找树
方法一：二叉查找树的节点维护的是一个数组，该数组支持动态扩容，我们把键值相同的数据放在该节点的数组中。或者，二叉查找树的节点维护的是一个链表，我们把键值相同的数据插入到该链表的尾部。
方法二：插入值相同的节点的时候，将该值放入该节点的右子树中，也就是说相同的值， 我们当做大于该值来处理。
针对方法二，查找节点的时候，遇到相同值的节点的时候，继续在该节点的右子树查找，直到查找到叶子节点位置。删除节点的时候，查找到所有要删除的节点，然后利用删除删除节点的方法依次删除。还有一种简便的删除方法，对要删除的节点做删除标记，这样不改变树的结构，就完成了删除，只是比较浪费空间。
在实际应用中，二叉查找树的节点并非只是存储一个值，而是存储一个对象。利用对象的某个属性值，作为键值构建二叉查找树，其他数字段叫做卫星数据。
二叉查找树的时间复杂度分析
极端情况下，除根节点以外的其他节点都是父节点的左子节点或者是右子节点，则二叉查找树就退化为链表了，查找的时间复杂度为 O(n)。
理想情况下，二叉查找树是一个完全二叉树(满二叉树)，那么查找到某个节点的最坏时间复杂度就是该二叉查找树的高度了，所以时间复杂度就是 O(high)。
推理过程省略了，我不会推理，直接总结结论：一个有着 n 个节点的完全二叉查找树，它的高度小于等于 log2|n，所以时间复杂度为 O(logn)。
总结
二叉查找树和散列表的对比：
1：散列表是无序的，如果想要有序输出，必须对数据排序。而二叉查找树只要中序遍历输出，就是一个有序的输出。
2：散列表扩容耗时多，散列冲突严重的时候，性能不稳定。二叉查找树的性能不稳定，但是平衡二叉查找树性能稳定。
3：散列表查找数据的时间复杂度是常量级别的，但是因为有散列冲突，所以常量级别的时间复杂度不一定比 logn 的值小。同时，哈希函数的运算也需要耗时，未必就比二叉查找树的查找效率高。
4：散列表的构造比较复杂，既要考虑散列函数的高效，又要考虑散列冲突的解决方法，对于扩容缩容也需要合适的设计。而平衡二叉查找树就没有这么些限制，只需要考虑性能问题就行。
本文创作灵感来源于 极客时间 王争老师的《数据结构与算法之美》课程，通过课后反思以及借鉴各位学友的发言总结，现整理出自己的知识架构，以便日后温故知新，查漏补缺。
初入算法学习，必是步履蹒跚，一路磕磕绊绊跌跌撞撞。看不懂别慌，也别忙着总结，先读五遍文章先，无他，唯手熟尔~
与诸君共勉
