二叉搜索树（又：二叉查找树，二叉排序树）是以一颗二叉树来组织的，在代码实现上，二叉搜索树可以用链表来表示，将二叉树的节点看作链表的Node对象，每个Node对象包含left、right、parent属性，它们分别代表节点的左孩子、右孩子、父节点（双亲节点），如果某个孩子或父节点不存在，则用null值表示。
二叉搜索树是指具有下面定义的二叉树（下面1、2点必须背下来）：
1、任何父节点的值均大于等于（>=）左孩子节点值以及左孩子下的所有孩子节点值
2、任何父节点的值均小于（<）右孩子节点值以及右孩子下的所有孩子节点值
3、树最根节点是唯一父节点值为null的节点
二叉搜索树本质上就是一颗二叉树，二叉树逻辑上一般有以下类型和形态：
1、空二叉树
2、只有一个根节点的二叉树
3、左斜树
4、右斜树
5、完全二叉树
6、满二叉树
二叉搜索树一般具有以下动态集合操作API：
1、查找（search）
2、插入（insert）
3、删除（delete）
4、最大值（maxVal）
5、最小值（minVal）
6、前驱（pre）
7、后继（post）
前驱：给定任意节点，如果该节点是整颗树的最小值（绝对不存在左孩子的），它的前驱是null；否则如果该节点存在左孩子，它的前驱是以这个左孩子为根下的左边整颗子树中最大值的那个节点；如果不存在左孩子且不是最小值，它的前驱是根节点。
后继：给定任意节点，如果该节点是整颗树的最大值（绝对不存在右孩子的），它的后继是null；否则如果该节点存在右孩子，它的后继是以这个右孩子为根下的右边整颗子树中最小值的那个节点；如果不存在右孩子且不是最大值，它的后继是根节点
二叉搜索树基本动态集合操作API的时间复杂度均为O（h）,其中h为二叉树的高度。
当调用插入接口时（insert）就开始构建了二叉搜索树了，所以，研究如何构建二叉树实际上就是研究如何实现插入方法。根据如下定义，我们来看下如何实现插入接口的代码：
根据定义，我们还快能够想到，插入元素一些基本逻辑如下：
1、每个元素值必须是能够进行大小比较的，至少有定义好比较规则
2、第一次插入元素可以直接作为根。这里注意，如果第一次插入的值是整棵树最大值或最小值，那么这种情况这个二叉树通过会成为斜树，就是只有（首次插入的是最大值）左孩子或（首次插入的是最小值）右孩子的，那么这棵树的高度会很高，我们知道，二叉搜索树的大部分操作API时间复杂度是0（h）高度h越高，时间复杂度越大，实际使用时可以使用随机方式避免这种情况的发生。
3、后面每次插入元素时，从根开始进行比对，如果小于等于根，循环判断左孩子下的所有孩子节点直到叶子节点（孩子节点为null值）；如果大于根，循环判断右孩子下的所有孩子节点直到叶子节点（孩子节点为null值）；
代码如下：
从根往下查找一个给定的值，我们只需要判断这个值是根节点的左孩子还是右孩子，如果是左孩子，那么将左孩子和这个值比较看是否相等，如果相等就返回，否则将这个左孩子作为子根按上面逻辑递归查找，代码如下：
给定任意节点的最大值节点：基于这个给定节点循环或递归往右查找，直到叶子节点为止，该叶子节点便是整棵树的最大值节点，代码如下：
给定任意节点的最小值节点：基于这个给定节点循环或递归往左查找，直到叶子节点为止，该叶子节点便是整棵树的最小值节点，代码如下：
前驱：给定任意节点，如果该节点是整颗树的最小值（绝对不存在左孩子的），它的前驱是null；否则如果该节点存在左孩子，它的前驱是以这个左孩子为根下的左边整颗子树中最大值的那个节点；如果不存在左孩子且不是最小值，它的前驱是根节点，代码如下：
后继：给定任意节点，如果该节点是整颗树的最大值（绝对不存在右孩子的），它的后继是null；否则如果该节点存在右孩子，它的后继是以这个右孩子为根下的右边整颗子树中最小值的那个节点；如果不存在右孩子且不是最大值，它的后继是根节点，代码如下：
删除API是二叉搜索树所有API中最复杂之一，下面我们把它分解多种情况来讲解。
1、如果节点只有一个元素且删除的节点是根节点，那么直接把根节点置为null即可
2、删除给定任意一个节点，如果该节点只存在左节点，那么很简单，只需要把左节点替换到该节点上，给定的这个节点就被删除了
3、删除给定任意一个节点，如果该节点只存在右节点，那么很简单，只需要把右节点替换到该节点上，给定的这个节点就被删除了
4、删除给定任意一个节点，如果该节点存在左右节点，这种情况就比较复杂些，我们知道，删除某个节点一定是要改变二叉树的结构的，而改变结构可能会破坏二叉搜索树的定义。所以复杂之处就是要保证删除后的二叉搜索树依然满足定义，下面直接给出删除的处理逻辑。
4.1、找出被删除节点的后继节点
4.2、判断这个后继节点是否是被删除节点的直接孩子节点（后继节点不可能是左孩子节点）
4.3、如果后继节点是被删除节点的直接孩子节点，直接将后继节点替换到被删除节点的位置
4.4、如果后继节点不是被删除节点的直接孩子节点，需要先将后继节点的右孩子节点（根据定义这个后继节点不可能有左孩子节点的只有右孩子节点）替换到这个后继节点位置，最后再把后继节点替换到被删除节点位置
图解后继节点是被删除节点的直接孩子节点的删除前后情况：
图解后继节点不是被删除节点的直接孩子节点的删除前后情况：
我们发现，删除API需要替换节点位置能力，我们可以先把这个能力提取出来作为一个独立的方法，代码如下：
删除节点代码如下：
输出：
构建完成后的二叉树 [8,12,15,16,17,19,23]
根节点值 16
值为16的节点值 16
值为15的前驱值 12
值为8的前驱值 null
值为16的前驱值 15
值为16的后继值 17
值为8的后继值 12
值为23的后继值 null
值为17的后继值 19
删除根前根值是 16
删除根后根值是 17
删除根节点后二叉树正序输出
8 12 15 17 19 23
删除后值为16的节点值 null
删除后值为17的前驱值 15
删除后值为15的后继值 17
二叉搜索树是二叉树的一种，顾名思义，二叉搜索树一般就是做路径搜索用的，如何定义好父节点很重要，调优二叉搜索树，实际上就是如何找到集合的中间值作为父节点，因为只有父节点值处于较中间位置，那么二叉树的高度就比较低，查找速度就比较快。如果已知集合是可能有序的或者第一个插入值是最大或小值时，最好通过随机的方式从集合获取一个值进行插入，避免出现斜树的情况。