二叉查找树(Binary Search Tree)

定义

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点

深度为3的二叉查找树

优势

1. 查找、插入的时间复杂度较低
2. 时间复杂度为O(logN)，最坏时间复杂度为O(N)
3. 从基础的二叉查找树可以衍生平衡二叉树，从而使得查询/插入操作的时间复杂度平衡在O(logN) PS: 查询节点的时间与树高度相关，高度越高，时间越长

劣势

1. 由于普通的二叉查找树没有做平衡（通过旋转来达到树左右子树高度相差不大）处理，导致可能会出现树的严重倾斜

平衡二叉树与倾斜的二叉树.png

二叉树查找

在二叉搜索树b中查找x的过程为： 若b是空树，则搜索失败，否则： 若x等于b的根节点的数据域之值，则查找成功；否则： 若x小于b的根节点的数据域之值，则搜索左子树；否则： 若x大于b的根节点的数据域之值，则搜索右子树。

查找过程.png

二叉树插入

向一个二叉搜索树b中插入一个节点s的算法，过程为： 若b是空树，则将s所指结点作为根节点插入，否则： 若s->data等于b的根节点的数据域之值，则返回，否则： 若s->data小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则： 把s所指节点插入到右子树中。（新插入节点总是叶子节点）

插入过程.png

二叉树删除

在二叉查找树删去一个结点，有3种情况：

1. 若*p结点为叶子结点，即当前节点的左子树和右子树均为空树: 由于删去叶子结点不破坏整棵树的结构，则只需修改其父节点的指针即可。

删除无子树的节点

1. 若p结点只有左子树或右子树: 此时只要令左子树或右子树直接成为父结点左子树（当p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉查找树的特性。

删除只有一个子树

1. 若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就是该节点的前驱节点

TreeMap的Preducessor算法

如最上图所示： 3的前驱是1：当前节点有左子树，找到左子树最右的节点 10的前驱是8：当前节点没有左子树，并且是父节点的右子树 4的前驱是3：当前节点没有左子树，找到沿父节点出于左子树节点

后继(Successor)

定义：节点val值大于该节点val值并且值最小的节点 若一个节点有右子树，那么该节点的后继节点是其右子树中val值最小的节点（也就是右子树中所谓的leftMostNode） 若一个节点没有右子树，那么判断该节点和其父节点的关系 2.1 若该节点是其父节点的左子树，那么该节点的后继结点即为其父节点 2.2 若该节点是其父节点的右子树，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的子树 ，那么Q就是该节点的后继节点

TreeMap的Successor算法

如最上图所示： 8的后继是10：当前节点有右子树，并且右子树节点无左子树 10的后继是13：当前节点有右子树，则找到右节点的右子树最小的节点 4的后继是6：当前节点是父节点的左子树，则该节点的后继即为其父节点