彻底理解红黑树（一）之二叉搜索树
彻底理解红黑树（二）之插入
彻底理解红黑树（三）之删除

1. 二叉搜索树的定义

二叉搜索树（Binary Search Tree），（又：二叉查询树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

二叉搜索树

通俗地讲，以当前节点为根，其左右子树的特点：左小右大。当前节点为50时，其左子树所有节点均小于50，右子树所有节点均大于50：

50为根的二叉搜索树

节点50的左右子树也同样符合这种特点，以左子树为例（以30为根的树）：

30为根的二叉搜索树

同样的，其他的子树、子树的子树等均符合该规律（类似递归）。

2. 查找

根据左小右大的特点，查找一个元素时，从根节点出发：
（1）如果查找的元素比当前节点小，则到左子树找；
（2）如果查找的元素比当前节点大，则到右子树找；
（3）如果查找的元素等于当前节点，说明找到了；
（4）如果直至叶子节点都找不到对应的，说明该元素不存在该树中。

查找 查找35

3. 插入

插入元素时，主要是找到合适的位置进行插入（类似查找）：

1. 插入的树为空树（无节点），直接创建节点即可；
2. 插入的树非空树：
   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. 只有一个子节点，用该子节点接到删除节点的父节点即可；
3. 有两个子节点，使用前或后继节点作为替换节点，对删除节点进行数据替换，然后转移至删除替换节点即可。而此时删除后继节点时，必然是情景1或2了；

看下例子：

情景1 叶子节点 情景2 子节点数量为1 情景3 子节点数量为2

关于情景3，无论使用前继节点还是后继节点，均可以达到同样的目的，选其一即可。

5. 二叉搜索树的问题

极端时，搜索的时间复杂度将会降低到 O(n)，比如以下这个例子：

连续插入10,20,30,40,50

而平衡二叉搜索树（AVL树、红黑树等）就是为了解决这个问题：平衡二叉树在进行插入、删除后，会进行自平衡，从而保证其查询的时间复杂度接近于O(log₂n)。如红黑树连续插入10,20,30,40,50：

红黑树连续插入10,20,30,40,50

想知道红黑树在插入时怎么做到平衡的？请见下文：彻底理解红黑树（二）之插入