二叉搜索树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
1. 二叉搜索树结构
上图是一棵典型的二叉搜索树，二叉搜索树按照中序遍历，是一个递增的序列，很容易得到其中序遍历结果为：1、3、5、6、7、8、10。
2. 二叉搜索树查找
查找比较简单，根据二叉搜索树的特性，当前节点比其左子节点值大，比其右子节点值小，依次递归比较当前节点与待查找值的大小，直到最后找到结果。如下图所示：
3. 二叉搜索树插入
从根节点开始，依次与待插入的数据进行比较，直到无法比较为止，这个时候最后找到的这个节点必然是叶子节点或者只有一个子节点，最后将待插入的数据插入到这个节点上。
4. 二叉搜索树删除
要删除一个数据，首先得在树中找到目标节点，找到目标节点很简单，前面已经讲过，但难的是删除。待删除节点一般会有以下 4 种情况：
我们先说简单的：
- 第4种情况：待删除节点为 8 ，我们只需要将其父节点 10 的左孩子置空就可以了；
- 第2、3种情况：这两种都是类似的。以第2个为例，待删除节点为 1，其父节点为 5，其子节点为 3，我们只需将节点 5 的左孩子置为节点 3 即可；
最后我们来看第 1 种情况，发现怎样操作都不好：如果将节点 7 删除，再将节点 5 置为根节点，由于节点 5 已经有一个右孩子节点 6，那么节点 6 与节点 10 就会发生冲突，然后还要继续调整节点的位置；如果将节点 10 置为根节点，那么还得继续调整节点 8 ，如果是一棵复杂的树，操作起来非常难。
那么怎么办呢？既然情况 1 直接调整难度很大，那么是否有某种方式，可以将其转换为第2、3、4种情况呢，如果可以的话，那这个问题就迎刃而解了。答案是肯定的，看以下流程所示：
如上图所示，经过一番操作之后，我们将原问题转换成另外一个问题了，简化后的问题我们能很方便解决了。
最后是完整的代码（kotlin编写）：
//二叉树节点
class Node<T>(var value: T?) {
var left: Node<T>? = null
var right: Node<T>? = null
}
//二叉搜索树
class BinarySearchTree {
//二叉搜索树根节点
var root: Node<Int>? = null
/**
* 在树中进行查找
*/
fun find(data: Int): Node<Int>? {
var p = root
while (p != null) {
if (data == p.value) {
return p
}
if (data < p.value!!) {
p = p.left
} else {
p = p.right
}
}
return null
}
/**
* 往树中插入数据
*/
fun insert(data: Int) {
var p = root
var pp: Node<Int>? = null
//循环结束时，pp 最多只有1个子节点，将待插入节点与 pp 比较大小，如果比 pp 大，则插入到 pp 的右子节点，否则就插入到 pp 的左子节点
while (p != null) {
if (data > p.value!!) {
pp = p
p = p.right
} else {
pp = p
p = p.left
}
}
//pp 为 null，说明整棵树就是空的，我们直接为树的根节点赋值即可
if (pp == null) {
root = Node(data)
} else {
if (data > pp.value!!) {
pp.right = Node(data)
} else {
pp.left = Node(data)
}
}
}
/**
* 删除节点
* 删除策略：首先找到待删除节点 p，然后找到该目标节点的右子树中的最左节点 t，交换节点 p 与 t 的值，最后删除节点 t
*/
fun delete(data: Int) {
var p = root //目标节点
var pp: Node<Int>? = null //目标节点的父节点
while (p != null) {
if (data == p.value) {
//找到目标节点，停止循环
break
}
if (data > p.value!!) {
pp = p
p = p.right
} else {
pp = p
p = p.left
}
}
//如果找不到待删除节点则直接返回
p ?: return
//找到节点 p 的右子树中的最左叶子节点 t
var t = p.right //待删除目标节点的右子节点
var tt = p //节点 t 的父节点
while (t?.left != null) {
tt = t
t = t.left
}
if (t != null) {
//交换节点 p、t 的值，后面我们直接删除节点 t 仍能满足二叉搜索树的特性
p.value = t.value
pp = tt
p = t
}
//待删除的是根节点
if (pp == null) {
root = if (p.left != null) p.left else p.right
} else {
//删除节点 p，此时的指针 p 必然最多只有1个子节点
var child = if (p.left != null) p.left else p.right
if (pp.left == p) {
pp.left = child
} else {
pp.right = child
}
}
}
}
二叉搜索树的查找、插入、删除操作的时间复杂度与树的高度有关，如果是一棵平衡二叉搜索树，则其时间复杂度均为 O(logn)，如果树退化成一个链表，则其时间复杂度为最坏情况 O(n)。
所以树的高度很重要，如果我们能一直维持一棵树比较平衡，那么其增删改查的时间复杂度均为 O(logn)，这样操作的效率就会非常之高。大名鼎鼎的红黑树就是这样一棵树，其实现非常复杂，涉及到节点的左旋、右旋等操作，有兴趣的可以去研究研究，不过我们还是要弄懂二叉搜索树的结构以及各种操作。
