定义
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点
优势
- 查找、插入的时间复杂度较低
- 时间复杂度为O(logN)，最坏时间复杂度为O(N)
- 从基础的二叉查找树可以衍生平衡二叉树，从而使得查询/插入操作的时间复杂度平衡在O(logN)
PS: 查询节点的时间与树高度相关，高度越高，时间越长
劣势
-
由于普通的二叉查找树没有做平衡（通过旋转来达到树左右子树高度相差不大）处理，导致可能会出现树的严重倾斜
平衡二叉树与倾斜的二叉树.png
二叉树查找
在二叉搜索树b中查找x的过程为：
若b是空树，则搜索失败，否则：
若x等于b的根节点的数据域之值，则查找成功；否则：
若x小于b的根节点的数据域之值，则搜索左子树；否则：
若x大于b的根节点的数据域之值，则搜索右子树。
二叉树插入
向一个二叉搜索树b中插入一个节点s的算法，过程为：
若b是空树，则将s所指结点作为根节点插入，否则：
若s->data等于b的根节点的数据域之值，则返回，否则：
若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
把s所指节点插入到右子树中。（新插入节点总是叶子节点）
二叉树删除
在二叉查找树删去一个结点，有3种情况：
-
若*p结点为叶子结点，即当前节点的左子树和右子树均为空树:
由于删去叶子结点不破坏整棵树的结构，则只需修改其父节点的指针即可。
删除无子树的节点 -
若p结点只有左子树或右子树:
此时只要令左子树或右子树直接成为父结点左子树（当p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉查找树的特性。
删除只有一个子树 -
若p结点的左子树和右子树均不空：
在删去p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法
a. 令p的左子树为f的左/右（依p是f的左子树还是右子树而定）子树，s为p左子树的最右下的结点，而p的右子树为s的右子树
b. 令p的直接前驱（in-order predecessor）或直接后继（in-order successor）替代p，然后再从二叉查找树中删去它的直接前驱（或直接后继）。
删除有两个子树的节点
前驱(Preducessor)
定义：节点val值小于该节点val值并且值最大的节点
若一个节点有左子树，那么该节点的前驱节点是其左子树中val值最大的节点（也就是左子树中所谓的rightMostNode）
若一个节点没有左子树，那么判断该节点和其父节点的关系
2.1 若该节点是其父节点的右节点，那么该节点的前驱结点即为其父节点。
2.2 若该节点是其父节点的左节点，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的右节点，那么Q就是该节点的前驱节点
如最上图所示：
3的前驱是1：当前节点有左子树，找到左子树最右的节点
10的前驱是8：当前节点没有左子树，并且是父节点的右子树
4的前驱是3：当前节点没有左子树，找到沿父节点出于左子树节点
后继(Successor)
定义：节点val值大于该节点val值并且值最小的节点
若一个节点有右子树，那么该节点的后继节点是其右子树中val值最小的节点（也就是右子树中所谓的leftMostNode）
若一个节点没有右子树，那么判断该节点和其父节点的关系
2.1 若该节点是其父节点的左子树，那么该节点的后继结点即为其父节点
2.2 若该节点是其父节点的右子树，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的子树 ，那么Q就是该节点的后继节点
如最上图所示：
8的后继是10：当前节点有右子树，并且右子树节点无左子树
10的后继是13：当前节点有右子树，则找到右节点的右子树最小的节点
4的后继是6：当前节点是父节点的左子树，则该节点的后继即为其父节点
