二叉搜索树概念
给定一段数据，如何快速查询某一个值是否在数据中存在，如何进行查找？
最简单最直接的是顺序查找，依次从头到尾进行查询，这样的时间复杂度是O(n), 你可能会说，二分查找，但是二分查找的前提是一段有序的数据，这样查找的时间复杂度为O(\log n) 。还有没有别的方法？
对于一段数据，我们可以通过构建二叉搜索树的方式存储数据，这样进行查找就十分迅速。二叉搜索树的原理是什么，例如下面的树是一个二叉搜索树：
对于每一个节点，其左子树的每一个值都比节点值小，右子树的每一个节点都比节点值大，其判断方法在之前讲过。二叉搜索树的操作方法有查询，插入，构建，删除。
查询
给定一个值进行查询时，先从根节点开始，如果这个值比比根节点小，则从左子树继续开始查找；否则从右子树开始查找，如果正好等于了，那就查找到了，动画如下：
插入
和查询类似，例如上面动画的9，如果没有这个元素就插入进去，如果有这个元素，就不要动。标准的二叉搜索树不允许出现重复元素。
构建
给定一段数据，从头到尾遍历，将数据一个一个插进去，就能够实现树的构建：
删除
在二叉搜索树（BST）中，删除操作相对复杂，因为需要考虑不同情况下的节点删除。主要有三种情况：
删除叶节点（没有子节点）：直接删除该节点。
删除只有一个子节点的节点：用该节点的子节点代替它。
删除有两个子节点的节点：找到该节点的中序后继（即右子树中最小的节点）或中序前驱（即左子树中最大的节点），用这个节点的值替换要删除的节点值，然后递归删除中序后继或前驱节点。
AVL树
同样的数据不同的顺序，直接构建出的二叉搜索树相同吗？
上面的问题答案为不相同，比如说有这么一段数据，它是顺序排序的，从头到尾构建出的二叉平衡树是一条链。如果我们想要进行查询操作时，最差时间复杂度为O(n) ，有没有什么办法进行优化？
想要实现高效的搜索操作，我们需要这个二叉搜索树是一个平衡树，平衡树的判别方法之前也有讲过。这样的话，所有的数据查询时间复杂度都为O(\log n) 。
AVL树佳能满足我们的需求，AVL树是一种平衡二叉搜索树，通过严格的平衡条件（左右子树高度差不超过1）来保持平衡。AVL树的查询操作和普通的二叉搜索树一样，但是其插入，构建和删除有了很大的区别。介绍插入操作前，需要了解两个树的操作：左旋和右旋。
左旋
左旋是围绕某个节点进行的旋转操作，使该节点的右子节点成为新的根节点，而该节点成为其右子节点的左子节点。
左旋操作步骤
假设我们要对节点 𝑥 进行左旋，且 𝑥 的右子节点为 𝑦：
将 𝑦 的左子树（即 𝑦 的左子节点）作为 𝑥 的右子树。
将 𝑥 作为 𝑦 的左子节点。
更新 𝑥 的父节点，使其指向 𝑦。
右旋
右旋是围绕某个节点进行的旋转操作，使该节点的左子节点成为新的根节点，而该节点成为其左子节点的右子节点。
右旋操作步骤
假设我们要对节点 𝑦 进行右旋，且 𝑦 的左子节点为 𝑥：
将 𝑥的右子树（即 𝑥 的右子节点）作为 𝑦 的左子树。
将 𝑦 作为 𝑥 的右子节点。
更新 𝑦 的父节点，使其指向 𝑥。
你可能发现了：左右旋并不会破坏搜索树的性质。
平衡因子
平衡因子是AVL树中用于判断节点平衡状态的重要指标。它是通过计算节点的左子树高度和右子树高度之差得出的一个值。具体来说，平衡因子的计算公式为：平衡因子=左子树高度−右子树高度。例如下图：
以11为例，其左子树的高度为2，右子树的高度为4，其平衡因子就为-2。以下节点同理。当一个节点的平衡因子绝对值大于等于2时，表明该节点发生了失衡。失衡有不同种类：
| 失衡类型 | 描述 | 平衡因子的表现 |
|---|---|---|
| LL型失衡 | 插入节点位于当前节点的左子树的左子树上。 | 当前节点的平衡因子为2，左子节点的平衡因子为1。 |
| RR型失衡 | 插入节点位于当前节点的右子树的右子树上。 | 当前节点的平衡因子为-2，右子节点的平衡因子为-1。 |
| LR型失衡 | 插入节点位于当前节点的左子树的右子树上。 | 当前节点的平衡因子为2，左子节点的平衡因子为-1。 |
| RL型失衡 | 插入节点位于当前节点的右子树的左子树上。 | 当前节点的平衡因子为-2，右子节点的平衡因子为1。 |
例如下面就是失衡的一种：
插入
AVL树插入规则如下：
执行标准的二叉搜索树插入操作，将新节点插入到合适的位置。
在向上回溯时，检查每个祖先节点的平衡因子（即左子树高度减去右子树高度的值）是否为-1、0或1。如果不是，则需要通过旋转操作来重新平衡树。
如果插入操作导致某个节点的平衡因子超出了范围（-1、0、1），则需要进行以下四种旋转操作之一来恢复平衡：
| 失衡类型 | 恢复平衡方式 |
|---|---|
| LL型失衡 | 对当前节点进行右旋。 |
| RR型失衡 | 对当前节点进行左旋。 |
| LR型失衡 | 先对当前节点的左子节点进行左旋，然后再对当前节点进行右旋。 |
| RL型失衡 | 先对当前节点的右子节点进行右旋，然后再对当前节点进行左旋。 |
具体的动画实现可以见构建过程。
构建
将数据依次插入就完成了构建，以下是动画实现：
删除
AVL树删除元素的步骤如下：
先按照二叉搜索树删除元素的步骤进行删除；
依次遍历删除元素的祖先元素，如果出现不平衡，根据失衡的种类进行操作；
操作完成后继续检查失衡，直到平衡为止。
推荐视频：
红黑树
尽管AVL树能够满足我们查询效率快速的需求，但是其也存在几个缺点，首先其插入删除麻烦，插入删除节点可能导致多次调整，最坏情况下的时间复杂度为O(\log n) 。其次内存开销也比较大，每个节点都要维护一个高度信息，以便计算平衡因子。
为了解决这些痛点，引入了红黑树。红黑树的插入和删除效率更高，内存开销也比较小（只需存储一个红或黑的状态）。但是理解起来比AVL树复杂的多得多。这部分内容需要慢慢消化。
红黑树是一种自平衡二叉搜索树，具有以下性质：
每个节点是红色或黑色。
根节点是黑色。
所有叶子节点（NIL节点）是黑色。
如果一个节点是红色，则它的两个子节点都是黑色（即红节点不能有红色子节点）。
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些性质确保了红黑树的高度近似平衡，从而保证了查找、插入和删除操作的时间复杂度为O(\log n)。
以上是一颗红黑树，满足红黑树的所有性质。注意叶子节点也就是空节点没有标识出来。
性质简记口诀：左根右，根叶黑，不红红，黑路同。解释如下：元素大小排序是左根右，红黑树的根节点和叶子节点（空节点）是黑节点，不能连续出现两个红节点，每一条支路黑色节点的数目相同。
插入
插入元素想要不破坏红黑树的性质，就需要对树进行一些调整。这里确定插入的都是红节点。
假设插入的节点为 𝑧：
插入节点 𝑧 并将其颜色设为红色。
如果 𝑧 是根节点，将其颜色改为黑色。
如果 𝑧的父节点 𝑝(𝑧) 是黑色，则插入完成。
如果 𝑧 的父节点 𝑝(𝑧) 是红色，则需要进行以下修复操作：
Case 1: 𝑧 的叔叔节点 𝑢 是红色。
将 𝑧 的叔父爷变色；
重新判断爷爷节点。
Case 2: 𝑧 的叔叔节点 𝑢 是黑色。
根据自己，父亲和爷爷的位置分类判断，例如父亲是爷爷的右孩子，标记为R_型，自己是父亲的左孩子，标记为RL型，根据类型做AVL树一样的旋转操作。
将旋转点和中心点变色。
如果违反了不红红，那么就看叔叔节点。
详细的动画演示可以见构建过程。
构建
依次将元素插入完成构建。
删除
红黑树的删除操作更难一些，在正式开始之前，先讨论一下几种特殊的情况。
我们知道普通二叉搜索树删除有以下几种情况：
删除元素有左孩子和右孩子；
删除元素有一个孩子；
删除元素为叶节点。
当删除元素有两个孩子的时候，我们会用中序前驱或中序后继进行替换，直到成为有一个孩子或为叶节点的情况。因此，我们讨论红黑树的删除时，只需讨论这两种情况即可。
首先讨论只有一个孩子的情况：红黑树只有一个孩子只有以下两种情况：1. 父亲节点是黑色，左孩子是红色；2. 父亲节点是黑色，右孩子是红色。
为什么呢，如果父子节点都为红，则违反了不红红；如果父子节点都为黑，则这条支路的黑色节点比其他支路会多，违反了黑路同；如果父节点是红色，子节点是黑色，那么另一个子节点少一个黑色节点，也违反了黑路同。
如果要删除父节点的话，直接拿子节点代替即可，并将子节点置黑。
最为复杂的是删除叶节点，先将删除的叶节点变为双黑节点，然后执行以下规则：
Case 1：兄弟节点s是红色
将父（p）兄（s）变色，变色后父节点向双黑节点旋转；
重新执行规则以进行调整。
Case 2：兄弟节点s是黑色
根据父（p）兄（s）兄弟节点的子节点（r）进行判断：若s在p的左孩子，为L_型，子节点r 至少有一个红在左，为LL型；仅有一个红在右，为LR型。若s在p的右孩子，为R_型，子节点r 至少有一个红在右，为RR型；仅有一个红在左，为RR型。
LL型，RR型，先变色：r变s色，s变p色，p变黑，然后再按照AVL树的规则进行旋转。删除双黑变单黑。
LR型，RL型，先变色：r变p色，p变黑，然后按照AVL树的规则旋转。删除双黑变单黑。
若兄弟节点的所有子节点都为黑色，则兄弟节点变色，双黑上移到父节点。
红色遇双黑变黑，根节点遇双黑变单黑，黑色遇双黑从头进行调整。
下面是动画演示：
推荐视频：
多叉搜索树B树和B+树会在未来讲到。
评论区