二叉搜索树

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

节点度：节点拥有的子树数。上图中，62的度为2，37的度为1，36的度为0。

树的深度：从根节点开始（其深度为0）自顶向下逐层累加的。上图中，36的深度是5，29的深度是4，51的深度是3。

树的高度：从叶子节点开始（其高度为0）自底向上逐层累加的。36的高度是0，根节点62的高度是5。

平衡因子: 此节点往下 左子树深度 - 右子树深度=平衡因子

平衡二叉树

1.定义

平衡二叉树也叫自平衡二叉搜索树（Self-Balancing Binary Search Tree），所以其本质也是一颗二叉搜索树，不过为了限制左右子树的高度差，避免出现倾斜树等偏向于线性结构演化的情况，所以对二叉搜索树中每个节点的左右子树作了限制，左右子树的高度差称之为平衡因子，树中每个节点的平衡因子绝对值不大于1 ，此时二叉搜索树称之为平衡二叉树。

自平衡是指，在对平衡二叉树执行插入或删除节点操作后，可能会导致树中某个节点的平衡因子绝对值超过1 ，即平衡二叉树变得“不平衡”，为了恢复该节点左右子树的平衡，此时需要对节点执行旋转操作。

2.性质

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡的调整共有四种情况：分别为LL,LR,RR,RL。

下面我们通过不断插入数据来说明几种不同的旋转方式:

注意：橘黄色的结点为旋转中心，黑色结点的为离插入结点最近的失衡结点。

（1）LR型:在左孩子L的节点上插入了左孩子节点L的右孩子节点R

最开始插入数据16，3，7后的结构如上图所示，结点16失去了平衡，3为16的左孩子，7为失衡结点的左孩子的右孩子，所以为LR型，接下来通过两次旋转操作复衡，先通过以3为旋转中心，进行左旋转，结果如图所示，然后再以7为旋转中心进行右旋转，旋转后恢复平衡了。

（2）LL型:在左孩子L的节点上插入了左孩子节点L的左孩子节点L

在上面恢复平衡后我们再次插入数据11和9,发现又失去平衡了，这次失衡结点是16，11是其左孩子，9为其失衡结点的左孩子的左孩子，所以是LL型，以失衡结点的左孩子为旋转中心进行一次右旋转即可。

（3）RR型:在右孩子R的节点上插入了右孩子节点R的右孩子节点R

进一步插入数据26后又再次失衡了，失衡结点为7,很明显这是RR型，以失衡结点的右孩子为旋转中心左旋转一次即可。

（4）RL型:在右孩子R的节点上插入了右孩子节点R的左孩子节点L

再插入18后又再次失衡了，失衡结点为16，26为其右孩子，18为其右孩子的左孩子，为RL型，以失衡结点的右孩子为旋转中心，进行一次右旋转，然后再次已失衡结点的右孩子为旋转中心进行一次左旋转变恢复了平衡。

红黑树

红黑树是一种自平衡二叉查找树，与 AVL 树类似，提供 O(logN) 级别的查询、插入和删除节点复杂度。相对于 AVL 树单纯的对每个节点的平衡因子进行判断，红黑树给节点赋予了颜色属性，并通过对树中节点的颜色进行限制，来保持整棵树的平衡。

之前提到的自平衡二叉查找树，即 AVL 树，属于一种高度平衡的二叉查找树，对每个节点的平衡因子进行严苛的限制，所以 AVL 树能够提供 O(logN) 的节点查询复杂度。也因为对每个节点的平衡因子限制较大，所以插入和删除节点时，需要进行很频繁的平衡调节操作。

红黑树相对于 AVL 树，对树的高度限制较为宽松，所以红黑树的查找复杂度要略逊于 AVL 树。也因为对树高度的限制较小，所以插入和删除节点时需要较少的旋转操作即可达到平衡状态。

由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。

条件限制

红黑树中的节点存在颜色属性，通过对节点颜色的限制来保持树的平衡性。平衡的红黑树要求如下：

1. 节点是红色或者黑色；

2. 根节点是黑色；

3. 所有叶子都是黑色（叶子是NIL结点）；

4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）

5. 从任一节点到其后代的叶子节点路径中包含相同个数的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

是性质4导致路径上不能有两个连续的红色结点确保了这个结果。最短的可能路径都是黑色结点，最长的可能路径有交替的红色和黑色结点。因为根据性质5所有最长的路径都有相同数目的黑色结点，这就表明了没有路径能多于任何其他路径的两倍长。

什么是 NIL

NIL节点也称为外部节点或空节点，它是红黑树中一种特殊的节点类型。NIL节点不存储实际的数据，它们的作用是协助维护红黑树的结构和性质，同时也简化了一些操作的实现。

在红黑树中，每个节点要么是红色的，要么是黑色的，而每个节点都有左子节点和右子节点。NIL节点是所有叶子节点的虚拟父节点，它们都是黑色的，且不包含任何子节点。这意味着，如果一个节点没有左子节点或右子节点，那么它的对应子节点就是一个NIL节点。

通过将红黑树的所有叶子节点都替换为NIL节点，我们可以保证红黑树的每个节点都至少有一个子节点。这样，我们就可以通过判断节点的子节点是否为NIL节点来处理边界情况，避免了在处理节点时需要特殊处理叶子节点的情况。

在红黑树中，NIL节点通常用一个特殊的指针表示，比如用 NULL 或 nullptr 表示。在某些实现中，NIL节点可能会占用一些内存空间，但是由于它们不包含任何实际的数据，因此这种内存开销通常可以忽略不计。

旋转

当对红黑树进行插入或删除时，就有可能破坏红黑树的性质，这时需要通过变色、左旋与右旋操作平衡红黑树。变色操作很简单，红变黑，黑变红，就不仔细介绍了，下面介绍左旋与右旋

左旋

此图是以X为旋转结点

定义：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

右旋

此图是以Y结点为旋转结点

定义：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

插入节点情况

待插入新节点颜色初始为红色，因为红色节点的插入不一定影响红黑树的平衡性，而黑色节点的插入一定会引起红黑树的不平衡。

新节点的插入有如下几种情形：

1. 新节点为根节点。

即当前红黑树为空树，插入新节点后，只需要变换节点颜色为黑色，即可满足红黑树的平衡限制条件；

2. 新节点的父节点为黑色。

若新节点不为根节点，则具有父节点，父节点颜色无外乎黑、红两种。当父节点颜色为黑色时，此时插入新节点不影响红黑树的平衡性，所以不需要调整操作；

3. 新节点的父节点为红色，同时叔父节点的颜色也为红色。

若父节点和叔父节点的颜色都为红色，则根据条件 4 ，祖父节点的颜色为黑色。因为新插入节点颜色为红色，违反了条件 4，此时只需要变换父节点和叔父节点的颜色为黑色，祖父节点的颜色为红色即可。变换颜色后，只需要考虑祖父节点颜色为红色，是否违反了条件限制，将祖父节点作为“新”节点，递归进行处理即可。

此时无所谓新节点是其父节点的左子节点或右子节点。

4. 新节点的父节点为红色，叔父节点的颜色不为红色。且新节点 N 是其父节点 P 的左子节点，同时父 P 节点 是祖父节点 G 的左子节点；或者新节点 N 是其父节点 P 的右子节点，同时父节点 P 是祖父节点 G 的右子节点。

不妨假设新节点 N 是其父节点 P 的左子节点，同时父节点 P 是祖父节点 G 的左子节点。因为父节点 P 为红色，所以祖父节点 G 颜色为黑色。此时以 P 节点为轴心执行一次右旋操作，并对父节点 P 和祖父节点 G 进行颜色变换。

旋转后的变色操作，保证了通过每个节点到后代叶子节点的路径上，包含的黑色节点个数不变，即满足了条件约束。

新节点 N 不一定只是一个单一的新插入节点，也可能是一颗二叉树的根节点，例如情形 3 的处理后，递归处理的“新”节点就是二叉树的根节点。空白的部分表示此处可能为空树或非空树，其实这里的叔父节点 U 也可以是空树或非空树。

5. 新节点的父节点为红色，叔父节点的颜色不为红色。且新节点 N 是其父节点 P 的右子节点，同时父节点 P 是祖父节点 G 的左子节点；或者新节点 N 是其父节点 P 的左子节点，同时父节点 P 是祖父节点 G 的右子节点。

不妨假设新节点 P 是其父节点 N 的右子节点，同时父节点 P 是祖父节点 G 的左子节点。因为父节点 P 为红色，所以祖父节点 G 颜色为黑色。此时以节点 N 为轴心执行一次左旋操作。

旋转操作前后，通过每个节点到后代叶子节点的路径上，所经过的黑色节点个数不发生变化。此时情形转变为情形 4，所以按照情形 4 进行处理即可。

由插入节点的情形分析可知，插入节点时最多只会进行两次旋转操作，即情形 5 旋转后变为情形 4，情形 4 旋转变色后满足平衡条件。变色操作则可能递归进行到根节点。

删除节点情况

二叉查找树在进行节点删除时，若待删除节点的度为 2 时，则可以将删除操作“转移”到其后代度不为 2 的子节点上，所以后续讨论的待删除节点的度都不为 2。

节点删除有如下几种情形：

1. 待删除节点颜色为红色。

因为待删除节点的度为 0 或 1，根据条件 5 可知，该待删除节点为叶子节点，所以直接删除该节点并不影响二叉树的平衡性。

2. 待删除节点为黑色，度为 1。

根据条件 5 可知，若待删除节点度为 1，则子节点颜色为红色。此时可以直接删除该节点，用子节点来填充该节点位置，对子节点进行颜色变换即可。

3. 待删除节点为黑色，度为 0。

情形 1, 2 中的节点删除场景较为简单，可以直接进行节点删除操作，最多只需要通过节点颜色变换即可保持二叉树的平衡性（注意根节点的变化）。若待删除节点度为 0，此时不妨对二叉树先进行一番预平衡操作，然后再进行节点删除，以此保证删除节点后二叉树处于平衡状态。

下面以 N 表示待删除节点，以 P 表示待删除节点的父节点，以 S 表示待删除节点的兄弟节点，以 SL表示兄弟节点的左子节点，以 SR 表示兄弟节点的右子节点。不妨以 N 节点作为 P 节点的左子节点进行讨论，对称的情况下处理过程类似。

3.1 兄弟节点 S 为黑色， SR节点为红色。

兄弟节点 S 的右子节点 SR 为红色，则兄弟节点 S 为黑色，父节点 P 颜色不确定。此时以节点 S 为轴心执行左旋操作，并对部分节点执行颜色变换操作。

左旋操作后，变换 SR 节点颜色。若 P 节点为红色，则左旋操作后，对 P 节点和 S 节点进行颜色变换。此时删除节点 N 之后，通过其他节点的路径上黑色节点个数不变，满足平衡条件。

3.2 兄弟节点 S 为黑色，SL 节点为红色，SR节点不为红色。

兄弟节点 S 的左子节点 SR 为红色，则兄弟节点 S 为黑色，父节点 P 颜色不确定， SR 节点不存在或存在为黑色。此时以节点 SL 为轴心执行右旋操作，并对 S 和 SL 节点执行颜色变换操作。

执行右旋操作后可以发现，此时情形演变为情形 3.1，所以此时再次对待删除节点 N 进行平衡操作即可。

3.3 兄弟节点 S 为黑色，S 节点没有红色子节点，且父节点 P 为黑色。

兄弟节点 S 和父节点 P 为黑色，且兄弟节点 S 没有红色子节点，此时对 S 进行颜色变换。

对兄弟节点 S 进行颜色变换后，可以发现，忽略待删除节点 N，此时父节点 P 处于和待删除节点 N 同样的处境，即通过该节点的路径上黑色节点个数减一。所以此时将父节点 P 作为新的节点 N 进行同样的预平衡操作。

3.4 兄弟节点 S 为黑色，S 节点没有红色子节点，且父节点 P 为红色。

兄弟节点 S 为黑色，且没有红色子节点，父节点 P 为红色，此时只需要对节点 S 和 P 进行颜色变换即可。

对兄弟节点 S 和父节点 P 进行颜色变换后，可以发现，忽略待删除节点 N ，此时通过各节点的路径上黑色节点个数不变，即二叉树处于平衡状态。

3.5 兄弟节点 S 为红色。

兄弟节点 S 为红色，则此时父节点 P 为黑色。此时以 S 节点为轴心进行左旋操作，并对节点 S 和 P 进行变色操作。

旋转并进行节点颜色变换后，可以发现，此时的二叉树同样处于平衡状态，所以这一步的旋转与颜色变换操作只是一个过渡处理，并没有起到预平衡的作用，即删除节点 N 之后，二叉树仍然是不平衡的。但是经过该步的处理之后，二叉树的状态演变为情形 3.1，3.2 或者 3.4 中的一种，所以可以对待删除节点 N 再次进行预平衡处理。

节点删除的所有情况如上，由各个情形描述可知，节点删除最多经过三次旋转即可达到平衡状态，即情形 3.5 旋转后变为情形 3.2，情形 3.2 旋转后变为情形 3.1，情形 3.1 旋转后满足平衡条件。变色操作则可能递归进行到根节点。