彻底理解红黑树（一）之二叉搜索树
彻底理解红黑树（一）之二叉搜索树
彻底理解红黑树（二）之插入
彻底理解红黑树（三）之删除
1. 二叉搜索树的定义
二叉搜索树（Binary Search Tree），（又：二叉查询树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
二叉搜索树
通俗地讲，以当前节点为根，其左右子树的特点：左小右大。当前节点为50时，其左子树所有节点均小于50，右子树所有节点均大于50：
50为根的二叉搜索树
节点50的左右子树也同样符合这种特点，以左子树为例（以30为根的树）：
30为根的二叉搜索树
同样的，其他的子树、子树的子树等均符合该规律（类似递归）。
2. 查找
根据左小右大的特点，查找一个元素时，从根节点出发：
（1）如果查找的元素比当前节点小，则到左子树找；
（2）如果查找的元素比当前节点大，则到右子树找；
（3）如果查找的元素等于当前节点，说明找到了；
（4）如果直至叶子节点都找不到对应的，说明该元素不存在该树中。
查找
查找35
3. 插入
插入元素时，主要是找到合适的位置进行插入（类似查找）：
- 插入的树为空树（无节点），直接创建节点即可；
- 插入的树非空树：
2.1 如果插入的元素比当前节点小，则到左子树插入；如果左子树/节点为null，插入该处；
2.2 如果插入的元素比当前节点大，则到右子树插入；如果右子树/节点为null，插入该处；
2.3 如果插入的元素和当前节点相等，说明该元素已经存在了，直接返回。
插入
插入50,30,70,60,65
4. 删除
4.1 前继节点和后继节点
二叉搜索树因为自身的特性（左小右大），中序遍历的结果必然是有序的。
比如以下这棵树，其遍历的结果为：【20, 30, 35, 40, 45, 50, 55, 60, 65 70, 80】
在二叉搜索树中，前继节点表示比当前节点小的最大值，后继节点表示比当前节点大的最小值，看例子就很容易明白：比如上面【20, 30, 35, 40, 45, 50, 55, 60, 65 70, 80】中，节点50的前继节点为45，后继节点为55。
在二叉搜索树中，寻找前后继节点很简单：
（1）寻找前继节点，当前节点左转一下，然后右转一直走到底（右子节点为null时终止）：
寻找50的前继节点
（2）寻找后继节点，当前节点右转一下，然后左转一直走到底（左子节点为null时终止）：
寻找50的后继节点
4.2 根据子节点数量进行删除处理
删除前首先要找到该节点，如果找不到，直接结束即可。
找到后，可以分为以下三种情景：
- 无子节点，即叶子节点，直接删除即可；
- 只有一个子节点，用该子节点接到删除节点的父节点即可；
- 有两个子节点，使用前或后继节点作为替换节点，对删除节点进行数据替换，然后转移至删除替换节点即可。而此时删除后继节点时，必然是情景1或2了；
看下例子：
情景1 叶子节点
情景2 子节点数量为1
情景3 子节点数量为2
关于情景3，无论使用前继节点还是后继节点，均可以达到同样的目的，选其一即可。
5. 二叉搜索树的问题
极端时，搜索的时间复杂度将会降低到 O(n)，比如以下这个例子：
连续插入10,20,30,40,50
而平衡二叉搜索树（AVL树、红黑树等）就是为了解决这个问题：平衡二叉树在进行插入、删除后，会进行自平衡，从而保证其查询的时间复杂度接近于O(log2n)。如红黑树连续插入10,20,30,40,50：
红黑树连续插入10,20,30,40,50
想知道红黑树在插入时怎么做到平衡的？请见下文：彻底理解红黑树（二）之插入
