二叉查找树
二叉查找树又称二叉搜索树。
它具有以下性质：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
- 任意结点的左、右子树也分别为二叉搜索树
二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势。
前驱节点和后继节点
前驱节点：
-
若一个节点有左子树，那么该节点的前驱节点是其左子树中val值最大的节点（也就是左子树中所谓的rightMostNode）
-
若一个节点没有左子树，那么判断该节点和其父节点的关系
2.1 若该节点是其父节点的右边孩子，那么该节点的前驱结点即为其父节点。
2.2 若该节点是其父节点的左边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的右边孩子，那么Q就是该节点的后继节点
后继节点：
- 若一个节点有右子树，那么该节点的后继节点是其右子树中val值最小的节点（也就是右子树中所谓的leftMostNode）
- 若一个节点没有右子树，那么判断该节点和其父节点的关系
2.1 若该节点是其父节点的左边孩子，那么该节点的后继结点即为其父节点
2.2 若该节点是其父节点的右边孩子，那么需要沿着其父亲节点一直向树的顶端寻找，直到找到一个节点P，P节点是其父节点Q的左边孩子（可参考例子2的前驱结点是1），那么Q就是该节点的后继节点
-
如图4的前驱结点是3
-
2的前驱结点是1
-
6的前驱结点是5
-
7的后继结点是8
-
5的后继节点是6
-
2的后继节点是3
查找节点
查找节点，必须从根节点开始查找：
- 查找值比当前节点值大，则搜索右子树。
- 查找值等于当前节点值，停止搜索。
- 查找值小于当前节点值，则搜索左子树。
删除节点
删除有一个子节点的节点
删除有一个子节点的节点，我们只需要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可。
如上图，节点4失去引用，等待GC回收
删除有两个子节点的节点
二叉查找树中的节点是按照关键自来进行排列的，某个节点的关键字次高节点是它的中序遍历后继节点，用后继节点来代替删除的节点，显然该二叉搜索树还是有序的。
删除节点是否有必要性
通过上面的删除分类讨论，我们发现删除其实是挺复杂的，那么其实我们可以不用真正的删除该节点，只需要在Node类中增加一个标识字段isDelete，
当该字段为true时，表示该节点已经删除，反之则没有删除。这样删除节点就不会改变树的结构了。
影响就是查询时需要判断一下节点是否已被删除。
遍历节点
遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历，中序遍历和后序遍历。而二叉搜索树最常用的是中序遍历。
①、中序遍历:左子树——》根节点——》右子树
②、前序遍历:根节点——》左子树——》右子树
③、后序遍历:左子树——》右子树——》根节点
缺点
在极端情况下，二叉搜索树退化成线性链表，所以平衡二叉树出现了。
平衡二叉树
平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
特点：
- 具有二叉查找树的全部特性。
- 每个节点的左子树和右子树的高度差至多等于1
平衡树基于这种特点就可以保证不会出现大量节点偏向于一边的情况了（插入或者删除时，会发生左旋、右旋操作，使这棵树再次左右保持一定的平衡）
至于左旋右旋操作不在本文讨论之内，不过多介绍。
红黑树
虽然平衡树解决了二叉查找树退化为近似链表的缺点，不过不是最佳方案。因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
显然，如果在那种插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树！！！
红黑树性质
-
性质1：每个节点要么是黑色，要么是红色。
-
性质2：根节点是黑色。
-
性质3：每个叶子节点（NIL）是黑色。
-
性质4：每个红色节点的两个子节点一定都是黑色。不能有两个红色节点相连。
-
性质5：任意一节点到每个叶子节点的路径都包含数量相同的黑结点。俗称：黑高！
红黑树示意图：
红黑树并不是一个完美平衡二叉查找树，从图上可以看到，根结点P的左子树显然比右子树高，但左子树和右子树的黑结点的层数是相等的，也即任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点(性质5)。
所以我们叫红黑树这种平衡为黑色完美平衡。
红黑树能自平衡，它靠的是什么？三种操作：左旋、右旋和变色
- 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
- 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变
- 变色：结点的颜色由红变黑或由黑变红。
左旋：
右旋：
红黑树插入
插入操作包括两部分工作：
1.查找插入的位置
2.插入后自平衡
注意：插入节点，必须为红色****，理由很简单，红色在父节点（如果存在）为黑色节点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。
但如果插入结点是黑色，那么插入位置所在的子树黑色结点总是多1，必须做自平衡。
在开始每个情景的讲解前，我们还是先来约定下:
红黑树插入节点情景分析
情景1：红黑树为空树
最简单的一种情景，直接把插入结点作为根结点就行
注意：根据红黑树性质2：根节点是黑色。还需要把插入结点设为黑色。
情景2：插入结点的Key已存在
处理：更新当前节点的值，为插入节点的值
情景3：插入结点的父结点为黑结点
由于插入的结点是红色的，当插入结点的黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。
情景4：插入节点的父节点为红色
再次回想下红黑树的性质2：根结点是黑色。如果插入节点的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。
这一点很关键，因为后续的旋转操作肯定需要祖父结点的参与。
插入情景4.1：叔叔结点存在并且为红结点
依据红黑树性质4可知，红色节点不能相连 ==> 祖父结点肯定为黑结点；
因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红
处理：
1.将P和U节点改为黑色
2.将PP改为红色
3.将PP设置为当前节点，进行后续处理
可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；
但如果PP的父结点是红色，则违反红黑树性质了。所以需要将PP设置为当前节点，继续做插入操作自平衡处理，直到平衡为止。
插入情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点
注意：单纯从插入前来看，叔叔节点非红即空（NIL节点），否则的话破坏了红黑树性质5，此路径会比其它路径多一个黑色节点。
插入情景4.2.1：新插入节点，为其父节点的左子节点（LL红色情况）
处理：
1.变颜色：将P设置为黑色，将PP设置为红色
2.对PP节点进行右旋
插入情景4.2.2：新插入节点，为其父节点的右子节点（LR红色情况）
处理：
1.对P进行左旋
2.将P设置为当前节点，得到LL红色情况
3.按照LL红色情况处理（1.变颜色 2.右旋PP）
插入情景4.3：****叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点
该情景对应情景4.2，只是方向反转，直接看图。
插入情景4.3.1：新插入节点，为其父节点的右子节点（RR红色情况）
处理：
1.变颜色：将P设置为黑色，将PP设置为红色
2.对PP节点进行左旋
插入情景4.3.2：新插入节点，为其父节点的左子节点（RL红色情况）
处理：
1.对P进行右旋
2.将P设置为当前节点，得到RR红色情况
3.按照RR红色情况处理（1.变颜色 2.左旋PP）
插入案例
推荐一个不错的网站，常见的数据结构和算法演示：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html