INT202 Complexity of Algroithms 算法的复杂度 Pt.2 Search Algorithm 搜索算法

1.树的数据结构

我们用链式结构（Linked structure）可以实现树形数据结构。在这种结构中，树的每个节点 v 由一个对象表示，该对象包含以下信息：
1.存储在节点 v 中的元素。
2.指向其父节点和子节点的引用（或位置）。

对于有根树来说，特别是当每个节点最多有$t$个子节点，并且树的深度是有限的情况，我们可以使用数组来存储有根树。
里以二叉树（Binary Tree）为例来说明。在二叉树中，每个节点最多有两个子节点。以下是如何将二叉树存储在数组$A$中的步骤：
1.根节点：树的根节点存储在数组的第一个位置，即$A[0]$。
2.子节点的存储：根节点的两个子节点（如果有的话）分别存储在数组的第2和第3个位置，即$A[1]$ 和$A[2]$。
3.子节点的子节点：接下来，$A[1]$的两个子节点（如果有的话）存储在数组的第4和第5个位置，即$A[3]$和$A[4]$；$A[2]$的两个子节点存储在数组的第6和第7个位置，即$A[5]$和$A[6]$。
4.继续递归：这个过程会递归地继续下去，每个节点的子节点都按照从左到右的顺序存储在数组中。

因此对于数组中位置为$A[i]$的节点，其两个子节点分别存储在$A[2i+1]$和$A[2i+2]$的位置。
对于数组中位置为$A[i]$的节点（除了根节点），其父节点存储在位置$A[\lfloor (i-1)/2\rfloor ]$。这里使用了向下取整的除法$\lfloor (i-1)/2\rfloor$（floor）来计算父节点的位置。
这种方法可以推广到每个节点最多有$t$个子节点的情况。在这种情况下，对于数组中位置为$A[i]$的节点，其子节点存储在$A[i\times t+1]$到 $A[i\times t+t]$的位置。同样，其父节点存储在位置 $A[\lfloor (i-1)/t\rfloor ]$。

1.1 有序数据(Ordered Data)

我们经常希望以某种方式（通常是数值顺序或字母顺序，但也可能采用其他排序方式）存储有序的数据。
这里研究了几种存储这类有序数据的方法，并在添加更多数据或删除数据时维护其顺序。
我们将讨论将数据高效排序到这样的有序集合中的有效方法以及存储数据时维护其有序性的方法，对于后者，与在已经接收到汇总数据作为输入后对数据进行排序是不同的。

1.1.1 有序字典（Ordered Dictonary）

有序字典（Ordered Dictionary）是一种数据结构，它不仅像常规字典（Dictionary）那样存储键值对（Key-Value Pairs），而且还维护这些元素的顺序关系。这里的“顺序”是指根据键（Key）来排序元素。
对于有序字典的几个常规操作如下。
1.findElement(k)：
这个操作用于查找键为 k 的元素在有序字典中的位置。它返回该元素的位置索引。
2.insertElement(k, e)：
这个操作用于在有序字典中插入一个新的键值对。键为 k，值为 e。插入操作会将新的键值对放置在正确的位置，以保持字典中元素的顺序。
3.removeElement(k)：
这个操作用于从有序字典中移除键为 k 的元素。移除操作会从字典中删除指定的键值对，并可能需要调整其他元素的位置以维持顺序。

因此有序字典可以用于实现以下功能：
维护一个按时间顺序排列的事件日志。
实现一个能够按顺序访问元素的缓存系统。
提供一个能够按字典顺序列出所有键的配置管理器。

1.1.1.1 排序表（Sorted Tables）

如果一个字典$D$是有序的，我们可以按照键的非递减顺序将其项存储在一个向量$S$中。这通常假设我们不会向字典中添加更多的项。
以这种方式将字典存储在向量中，比使用链表存储$S$可以更快地进行搜索。
查找表是一种通过排序序列实现的字典，由两部分组成。
1.我们将字典的项存储在一个基于数组的序列中，并按键排序。
2.我们使用一个外部比较器来比较键。

1.2 二分查找（Binary Search）

我们现在介绍一种查找方法——二分查找。
它通过元素在数组中的排名（rank）来访问数组 S 中的元素。这里的“排名”指的是元素在有序数组中的位置。
排名为$i$的元素的键不小于排名从$1$到$i-1$的所有元素的键，并且不大于排名从$i+1$到$n$的所有元素的键。这意味着数组是按照键的非递减顺序排序的。
二分查找是在数组$S$中的一个递减范围内进行的。这意味着随着搜索的进行，搜索的范围会逐渐缩小。
具体过程如下：
在数组$S$中查找特定元素$k$时，当前考虑的$S$的范围被定义为一对排名：low 和 high。
1.初始化：low=1 和 high=n，其中$n$是数组$S$的大小。
key(i) 表示排名为 i 的元素的键。elem(i) 表示排名为 i 的元素。
2.计算中间位置：为了减小搜索范围，我们将目标键$k$与当前搜索范围的中间位置的键进行比较。计算中间位置 mid = ⌊(low + high) / 2⌋。这里使用了向下取整除法来确保得到一个整数索引。
3.三种可能情况：

1. 如果$k$等于 key(mid)，这意味着我们已经找到了目标元素，搜索成功完成。
2. 如果$k$小于 key(mid)，这意味着目标元素（如果存在）必须位于中间位置的左侧。因此，我们将搜索范围的上限 high 更新为 mid−1，然后继续搜索。
3. 如果$k$大于 key(mid)，这意味着目标元素（如果存在）必须位于中间位置的右侧。因此，我们将搜索范围的下限 low 更新为 mid+1，然后继续搜索。
4. 继续搜索：在每种情况下，我们都更新了搜索范围，使得下一次迭代时搜索范围更小。这个过程会重复进行，直到找到目标元素或者搜索范围为空（即 low 大于 high），后者表示目标元素不在数组中，因为我们已经遍历完了所有数组中的元素。

因此其伪代码如下。

BINARYSEARCH(S, k, low, high)// Input is an ordered array of elements.// Output: Element with key k if it exists, otherwise an error.if low > highreturn NO_SUCH_KEYelsemid ← ⌊(low + high) / 2⌋if k = key(mid)return elem(mid)elseif k < key(mid)return BINARYSEARCH(S, k, low, mid - 1)elsereturn BINARYSEARCH(S, k, mid + 1, high)

下图给出了BINARYSEARCH(S, 19, 1, size(S))的过程。

1.2.1 二分查找的时间复杂度

在每次递归调用中，执行的是固定数量的操作。因此每次递归调用的运行时间是常数级别的。二分查找的运行时间与执行的递归调用次数成正比。
数组$A$中仍需搜索的候选项数量为 high − low + 1 。
此外每次递归调用至少将剩余候选项的数量减少一半。
即
(mid - 1) - low + 1 = ⌊(low + high) / 2⌋ - low ≤ (high - low + 1) / 2 或
high - (mid + 1) + 1 = high - ⌊(low + high) / 2⌋ ≤ (high - low + 1) / 2
这里可能有人想问为什么等式后面不用 + 1 ，因为我们比较了mid元素，所以不需要计算这个元素。这里high − low + 1就是我们理解的输入 n，因此 (high - low + 1) / 2就是 n / 2。

这里我们将使用递归法来描述其运行时间。
最初，候选项的数量是$n$（数组的长度）。
在第一次调用 BinarySearch 后，候选项的数量最多减少到 $n/2$。
在第二次调用后，候选项的数量最多减少到$n/4$。
以此类推，每次递归调用后，候选项的数量都会减半。
所以我们可以定义一个函数$T(n)$来表示这个方法的运行时间。

其中$b$是一个常数，表示更新 low 和 high 以及其他开销所需的时间。
这个递归方程表明，每次递归调用后剩余的候选项数量最多为$n/2^i$
执行的最大递归调用次数是满足以下条件的最小整数$m$：$n/2^m<1$
换句话说，$m>lo{g}_2^n$。
因此，我们有$m=\lceil lo{g}_2^n\rceil +1$，其中 $\lceil x\rceil$ 表示对 $x$ 向上取整。
这意味着 BinarySearch(A, k, 1, n) 的运行时间是$O(logn)$。
这里补充说明一下为什么在时间复杂度中一般不需要底，因为我们可以使用换底公式修改这里的底，所以我们一般都忽略这里的底。
因此如果现在是三分之一，同样它的运行时间是$O(logn)$。

1.3 二叉搜索树（Binary Search Tree）

我们前面学习了二分查找，它通过元素在数组中的排名（rank）来访问数组 S 中的元素，又学习了有序的数据结构，因此我们可以将它们结合起来，就是下面我们要介绍的二叉搜索树。
二叉搜索树是一种基于树形数据结构的存储结构。
在二叉搜索树中，每个内部节点（Internal Node）存储一个元素$e$（或更一般地，一个键$k$，该键定义了排序规则，以及一些元素$e$）。
给定一个存储元素$e$的节点$v$，二叉搜索树具有以下性质：
1.所有在$v$的左子树（Left Subtree）中的元素都小于或等于$e$。
2.所有在$v$的右子树（Right Subtree）中的元素都大于或等于$e$。
如下图所示。

根节点存储元素 3，左子节点存储元素 1，右子节点存储元素 4。左子树中的元素小于根节点的元素，右子树中的元素大于根节点的元素。

1.3.1 搜索过程

得益于这一个特性，我们可以按照以下方式进行搜索。
为了搜索一个键$k$，我们从根节点开始沿着一条向下的路径进行搜索。
访问的下一个节点取决于当前节点的键与键$k$的比较结果。
如果我们到达一个叶子节点（即没有子节点的节点），而该键没有找到，则返回 NO_SUCH_KEY 表示没有找到该键。
伪代码如下：

Algorithm findElement(k, v)if T.isExternal(v)return NO_SUCH_KEYif k < key(v)return findElement(k, T.leftChild(v))else if k = key(v)return element(v)else { k > key(v) }return findElement(k, T.rightChild(v))

例如findElement(4)，搜索过程如下图所示。

从根节点6开始，因为4小于6，所以搜索路径向左移动到节点2，因为2小于4，所以搜索路径向右移动到节点4，找到了键为4的节点。

1.3.1.1 时间复杂度

对于这里的时间复杂度我们发现一个有趣的现象，如下图所示，这里有两棵树，但是它们储存的是同样的数据。

在运行findElement(4)时，上面只需要比较两次就能找到键为4的节点，但是下面需要三次。
首先这里的复杂度与前面的候选项的数量减少的速度有关。
因此时间复杂度与树的高度$h$相关。每一层的搜索时间是$O(1)$，即常数时间。
总时间复杂度是$O(h)$，即与树的高度成正比。

在最坏情况下，二叉搜索树可能退化成链表结构，此时树的高度为$n$（节点数）。
因此，在最坏情况下，搜索的时间复杂度为$O(n)$。
下图展示了一个退化的二叉搜索树，其中每个节点只有一个子节点，导致高度为$n$。前面的例子也是这样的情况。

在平衡二叉搜索树中，树的高度为 logn（对数级别）。
因此，在平衡情况下，搜索的时间复杂度为 O(logn)。
下图展示了一个平衡的二叉搜索树，其中树的高度远小于节点数 n。

因此我们可以发现如果我们的二叉搜索树不是平衡情况的话，那我们就不会有高效的搜索性能，就会出现像前面例子那样的情况。
为了保持高效的搜索性能，通常需要通过自平衡机制（如AVL树、红黑树等）来确保二叉搜索树的高度尽可能低，后面会进行介绍。
总结如下：
在二叉搜索树中，搜索操作的时间复杂度取决于树的高度$h$。
在最坏情况下（树退化成链表），时间复杂度为$O(n)$。
在平衡情况下（树高度为$logn$），时间复杂度为$O(logn)$。

1.3.2 相关操作

我们现在回到数据结构的角度，我们来看看二叉搜索树怎么实现相关操作。

1.3.2.1 插入操作

1. 首先，insertItem(k, e) 是我们的插入操作。执行这个操作后我们需要在树中搜索键 k。这里的 k 是要插入的元素的键，而 e 是与键 k 关联的值。
2. 假设键 k 还不在树中，我们继续搜索直到找到一个叶子节点 w。这个叶子节点 w 是搜索键 k 的过程中遇到的最后一个节点，由于 k 不在树中，所以这个节点没有键 k。
3. 我们在叶子节点 w 处插入键 k。由于 w 之前是一个叶子节点，它没有子节点。
   下图展示了insert 5的例子。
   
   
   注意插入后，键 5 被插入到适当的位置，并创建了两个新的子节点（用红色方框表示）。
   前面是假设键 k 不存在，如果 k 存在呢，如果键 k 已经在二叉搜索树（BST）中存在，通常我们不会在该位置再次插入相同的键，因此忽略这次操作。
   说到这个操作的时间复杂度，这里主要还是寻找插入位置，因此它取决于树的高度。在平均情况下，既如果树是平衡的，插入操作的时间复杂度是$O(logn)$，其中 n 是树中节点的数量。然而，在最坏情况下，如果树退化成链表，插入操作的时间复杂度会退化到$O(n)$。

1.3.2.2 删除操作

下列的删除算法旨在尽量减少树结构的重组和失衡。该算法会返回经过删除操作后得到的新的二叉搜索树。

1. 首先，找到需要被删除的节点，我们称之为 remNode。
2. 如果 remNode 是一个叶子节点（即没有子节点），则可以直接删除它，通过返回 null 来表示该位置为空。
3. 如果 remNode 只有一个子节点，可以通过返回其子节点来删除 remNode。这样，子节点将取代 remNode 的位置。
4. 如果 remNode 有两个子节点，需要找到 remNode 的中序后继（inorder successor）。中序后继是指在中序遍历中出现在 remNode 之后的节点，它具有比 remNode 大的最小键值。将中序后继的键复制到 remNode 中，然后删除中序后继节点。（由于中序后继是 remNode 右子树中键值最小的节点，它最多只有一个左子节点。因此，删除中序后继节点的操作可以简化为步骤2或步骤3。）
   最后，返回更新后的 remNode。

叶子节点的情况，示例如下。

remNode 有一个子节点的情况。

remNode 有两个子节点的情况。

1.3.3 复杂度

当使用二叉搜索树实现一个包含$n$个元素的字典时，所需的空间是$O(n)$。这意味着存储所有节点（每个节点包含一个元素）所需的空间与元素数量成正比。
查找元素的方法 findElement 的时间复杂度是 $O(h)$，其中$h$是树的高度。其中最坏情况是$O(n)$，最好情况是$O(logn)$。

因此对于不同的树可能会有不同的效率，尤其是在树不平衡的时候。
在最坏的情况下，二叉搜索树的高度$h$可能与节点数$n$一样大。这种情况通常发生在所谓的“退化树（degenerate tree）”中，即每个父节点只有一个关联的子节点，这与链表类似。
二叉搜索的主要优势是其对数时间复杂度的搜索效率（即$O(logn)$的搜索时间）。然而，如果二叉搜索树没有保持平衡，这种优势可能会丧失，甚至在最坏的情况下，搜索时间可能退化到线性时间$O(n)$。

1.3.4 多路搜索树（Multi-Way Search Tree）

多路搜索树是一种有序树，它扩展了二叉搜索树的概念，允许每个内部节点有多个子节点。
每个内部节点至少有两个子节点，并存储$d-1$个键-元素对 ($k_i$,$o_i$)，其中$d$是子节点的数量。
为什么是d-1？因为它是搜索树，它依旧满足左子树中的元素都小于或等于该节点，右子树中的元素都大于或等于该节点。
因此对于$d$个子节点，就有$d-1$个空，因此就需要$d-1$个键-元素对。

因此其的性质如下：
对于一个有子节点$v_1,v_2,\dots ,v_d$的节点，存储键$k_1,k_2,\dots ,k_{d-1}$。

1. $v_1$的子树中的键都小于$k_1$。
2. $v_i$的子树中的键都小于$k_{i-1}$和$k_i$之间$(i=2,...,d-1)$。
3. $v_d$的子树中的键都大于$k_{d-1}$。

其叶子节点不存储任何元素，仅作为占位符。
所以多路搜索树的例子如下。

我们可以发现30大于27小于32所以位于中间的子树下。

1.3.4.1 多路搜索树的中序遍历（Inoder-Traversal）

我们可以将二叉搜索树的中序遍历概念扩展到多路搜索树。
在访问节点$v$的项 ($k_i$,$o_i$) 时，我们是在递归遍历以$v_i$和$v_{i+1}$​为根的子树之间进行的。这里$v_i$和$v_{i+1}$是节点$v$的相邻子节点。
其实就是从左到右按顺序。
前面的中序遍历顺序如下。

1.3.4.2 搜索过程

与二叉搜索树的搜索过程类似。
考虑一个内部节点，它有$d$个子节点$v_1,v_2,...,v_d$和$d-1$个键$k_1,k_2,...,k_{d-1}$
四种可能情况：

1. 如果$k=k_i$（其中$i=1,\dots ,d-1$）,则搜索成功终止，因为找到了键$k$。
2. 如果$k<k_1$,则在子节点$v_1$中继续搜索，因为所有在$v_1$子树中的键都小于$k_1$。
3. 如果$k_{i-1}<k<k_i$（其中$i=2,\dots ,d-1$）,则在子节点$v_i$中继续搜索，因为所有在$v_i$子树中的键都在$k_{i-1}$和$k_i$之间。
4. 如果$k>k_{d-1}$,则在子节点$v_d$中继续搜索，因为所有在$v_d$子树中的键都大于$k_{d-1}$。
   下图展示了搜索30的例子。
   
   由于30大于24，所以选择27 32的节点。又因为30在27和32之间，因此选择30节点，30等于30，所以搜索成功终止。

1.3.4.3 (2, 4) 树/(2, 4) trees

(2,4) 树是一种多路搜索树，具有以下性质：

1. 节点大小属性（Node-Size Property）：每个内部节点最多有四个子节点。
2. 深度属性（Depth Property）：所有外部节点（叶子节点）具有相同的深度。换句话说所有叶子节点都在同一层。

根据子节点的数量，(2,4) 树中的内部节点可以是：

1. 2-node（2-节点）：有恰好两个子节点和一个键。
2. 3-node（3-节点）：有恰好三个子节点和两个键。
3. 4-node（4-节点）：有恰好四个子节点和三个键。

如图所示，这是一个(2,4)树。其中根节点是一个4-节点，后续省略。

这里我们介绍一个定理：一个存储$n$个元素的 (2,4) 树的高度是$O(logn)$。
证明如下：
设$h$是存储$n$个元素的 (2,4) 树的高度。
在深度$i=0,\dots ,h-1$的每一层至少有$2^i$个元素，而在深度$h$的层上没有元素。
因此，树中元素的总数$n$至少是$1+2+4+\dots +2^{h-1}$。
即$n\ge 1+2+4+\dots +2^{h-1}=2^h-1$。
因此$h\le log(n+1)$

根据这个定理我们可以得到在存储$n$个元素的 (2,4) 树中进行搜索的时间复杂度是$O(logn)$。

1.3.4.3.1 相关操作

1.3.4.3.1.1 插入操作

当我们向 (2,4) 树中插入一个新的元素 (k,o) 时，我们首先搜索键$k$，找到应该插入的位置，这通常是某个叶子节点。
在插入过程中，我们保持 (2,4) 树的深度属性，即所有叶子节点都位于相同的深度。
但是在插入新元素后，可能会引发一个溢出问题（overflow）。具体来说，如果插入新元素导致某个节点$v$（原本是4-节点）现在有5个子节点，那么这个节点就变成了一个5-节点，这违反了 (2,4) 树的节点大小属性（每个内部节点最多有4个子节点）。
如下图所示。

这里如果我们尝试插入键 17，可能会在某个节点$v$处引发溢出。假设节点 $v$原本是一个4-节点，包含键 15、18、24，并且有4个子节点。当我们尝试插入键 17 时，节点$v$将变成一个5-节点，包含键 15、17、18、24，并且有5个子节点。

1.3.4.3.1.2 分裂操作

因此我们介绍分裂操作。
当一个5-节点$v$出现时，我们通过分裂操作来处理这个溢出。
设$v_1,v_2,\dots ,v_5$是节点$v$的子节点，$k_1,k_2,\dots ,k_4$是节点$v$的键。

1. 替换节点：节点$v$被两个新节点$v\prime$ 和$v\prime \prime$替换。其中$v\prime$是一个3-节点，键$k_1,k_2$和子节点$v_1,v_2,v_3$。$v\prime \prime$是一个2-节点，包含键$k4$ 和子节点$v4,v5$。
2. 插入键到父节点：键$k_3$被插入到父节点$u$中。这可能会导致父节点 $u$也变成5-节点，从而可能需要进一步的分裂操作。
3. 可能的进一步分裂：如果父节点$u$也变成5-节点，这种溢出可能会继续向上传播，直到树的根节点。在某些情况下，可能需要创建一个新的根节点。
   刚刚的问题就如下图所示。
   
   下图给出了一个更为复杂的例子，其中分裂后父节点继续溢出，一直到树的根节点。
   
   这里添加17后因为溢出所以分裂，但是根节点溢出了。
   
   所以这里继续分裂，从而创建了一个新的根节点。
   通过这种方式，(2,4) 树始终保持平衡。虽然分裂操作可能需要递归地进行，但它确保了树的高度不会超过$O(logn)$，其中$n$是树中元素的数量。这保证了树的操作（如搜索、插入和删除）都能在对数时间内完成。

1.3.4.3.1.3 删除操作

在 (2,4) 树中，删除操作通常被简化为在具有叶子子节点的节点中进行删除。这是因为在这种情况下，删除操作不会影响到树的结构平衡。
如果要删除的元素不在具有叶子子节点的节点中，我们可以用它的中序后继（或等效地，用它的中序前驱）替换要删除的元素，然后删除这个后继（或前驱）元素。
如下图所示，删除键24。

以删除键24为例，我们首先找到它的中序后继，这里是27。我们将24替换为27，然后删除27。

同样的，删除操作可能会遇到下溢问题（Underflow）。即当从节点$v$中删除一个元素后，该节点变成了一个 1-节点，即它只有一个子节点且没有键。这违反了 (2,4) 树的节点大小属性，因为内部节点至少应有两个子节点。
为了处理节点$v$的下溢，我们需要考虑两种情况。
情况1：$v$的相邻兄弟节点（siblings）是2-节点。
我们将节点$v$与其相邻的兄弟节点$w$合并，并将父节点$u$中的一个键移动到合并后的节点$v\prime$中。这种操作称为融合（Fusion），它通过合并两个节点来解决下溢问题，并保持树的平衡。
如下图所示。

同样它可能会传播到父节点$u$中，解决方式也与前面分裂类似。
情况2：$v$的相邻兄弟节点（siblings）是3-节点或4-节点。
我们将兄弟节点$w$的一个子节点移动到节点$v$,再将父节点$u$中的一个键移动到节点$v$，将兄弟节点$w$中的一个键移动到父节点$u$。
转移操作完成后，不会发生下溢，所有涉及的节点都至少有两个子节点，符合 (2,4) 树的节点大小属性。
如下图所示。

1.3.5 AVL树（AVL树）

AVL树是一种自平衡的二叉搜索树。
它具有以下性质。
高度平衡属性（Height-Balance Property）：对于AVL树中的任何节点$n$，其左子树和右子树的高度之差最多为1。这个属性确保了树的平衡性，防止树退化成链状结构。

下图展示了一个AVL树。

因此其也具有以下定理。
定理：存储$n$个键的AVL树的高度是$O(logn)$。
证明如下：
$n(h)$表示高度为$h$的AVL树中内部节点的最小数量。
如图所示。

我们可以发现$n(1)=1$，$n(2)=2$。
对于$n>2$，高度为$h$的AVL树包含根节点、一个高度为 $h-1$的子树和另一个高度为$h-2$的子树。
所以我们得到$n(h)=1+n(h-1)+n(h-2)$。
已知$n(h-1)>n(h-2)$，则$n(h)>2n(h-2)$。
我们可以根据递推关系得到$n(h-2)>2n(h-4)$，$n(h-4)>2n(h-6)$，最终得到 $n(h)>2^{i}n(h-2i)$。
解决基础情况得到：$n(h)>2^{h/2-1}$ 。根据$h$是偶数还是奇数，$h-2i=1$或$h-2i=2$，即$i$取$\lceil h/2\rceil -1$。
两边取对数我们便得到$h<2logn(h)+2$(左右互换并且常数搬运到另一边）。
因此，AVL树的高度是$O(logn)$。

根据这个定理我们可以保证了以下两点。
1.由于AVL树的高度是$O(logn)$，因此在AVL树中进行搜索操作的时间复杂度也是 $O(logn)$。
2.在AVL树中进行插入和删除操作需要更仔细的实现，以维护高度平衡属性，我们将使用旋转操作（rotation）来调整树的平衡属性。

1.3.5.1 相关操作

在进行相关操作的时候要注意保持AVL树的高度平衡属性。

1.3.5.1.1 插入操作

在AVL树中进行插入操作，开始时与在普通的二叉搜索树（BST）中插入类似，即在树中添加一个新的外部节点（叶子节点）。
当树的高度平衡属性被破坏时，从新创建的节点开始，沿着树向上遍历，直到找到第一个不平衡的节点$x$，其祖父节点$z$是导致不平衡的节点。
由于$z$是因为其子节点$y$的子树中的插入操作而变得不平衡，为了重新平衡以$z$为根的子树，需要进行结构重组。
我们根据中序遍历的顺序，将节点$x$、$y$和$z$重命名为$a$、$b$和$c$。
然后将节点$b$替换节点$z$，$b$的子节点现在是$a$和$c$。而$a$和$c$的子节点分别是原来$x$、$y$和$z$的四个子树。
因此这里会有两种情况。
1.单旋转（Single Rotation）：
这是一个左旋转操作，围绕节点$a$进行。在这种情况下，节点$z$被替换为节点 $b$，并且节点$b$的子节点现在是$a$和$c$，其中$a$和$c$的子节点分别是原来 $x$、$y$和$z$的四个子树。
2.双旋转（Double Rotation）：
这是一个先右旋转后左旋转的操作，围绕节点$c$进行。首先对$c$进行右旋转，然后对$a$进行左旋转。这种操作用于更复杂的不平衡情况，其中直接的单旋转无法恢复平衡。
图例如下。

其实是按照前面说的将其第一层保持为$b$，下一层是$a$和$c$，剩余节点位置不动。$a$、$b$、$c$是因为它们的大小关系确定的，所以根据左子树小于该节点，右子树大于该节点，这里三者的大小的中间者就是$b$，也就当作这里最后结果的根节点。

因此重组的算法如下。
输入：二叉搜索树$T$中的一个节点$x$，该节点既有父节点$y$又有祖父节点$z$。
输出：经过涉及节点$x$、$y$和$z$的三节点重组（对应于单次或双次旋转）后的树$T$。
步骤如下：

1. 将节点$x$、$y$和$z$按中序遍历的顺序排列为 ($a$,$b$,$c$)。
   并且将$x$、$y$和$z$的四个子树（不包括$x$、$y$和$z$本身）按中序遍历的顺序排列为 ($T_0$ ,$T_1$,$T_2$ ,$T_3$)。
2. 用一个新的子树替换以 z 为根的子树，新子树的根是$b$。
3. 将$a$设置为$b$的左子节点，并将$T_0$和$T_1$分别设置为$a$的左子树和右子树。
4. 将$c$设置为$b$的右子节点，并将$T_2$和$T_3$分别设置为$c$的左子树和右子树。

下图给出了一个例子。

添加54导致了不平衡，所以 62 是$x$，50 是$y$，78 是$z$。根据它们的大小关系我们重组后得出下面的树。

1.3.5.1.2 删除操作

同样删除操作与普通的二叉搜索树（BST）类似，但也可能会遇到AVL树的高度平衡属性被破坏。
如下图所示。

这里删除 32 导致了不平衡。
我们使用前面的重组算法将树重新平衡。这里选择$x$的不同会有不同的结果，但是得出来的AVL树重新恢复平衡就行。
下图展示了不同的情况。

第一种情况是以 78 为$x$，第二种情况是以 50 为$x$，两种结果都是有效的AVL树重新平衡操作后的结果。

所有关于$n$个元素的AVL树的操作的复杂度都是$O(logn)$。

总结如下：
1.单次重新结构化操作的时间复杂度是$O(1)$。
2.搜索操作的时间复杂度是$O(logn)$，因为AVL树的高度是$O(logn)$。
3.插入操作的时间复杂度是$O(logn)$，其中初始搜索（找到插入位置）的时间复杂度是$O(logn)$，在树中重新结构化以维持高度平衡的时间复杂度也是$O(logn)$。
4.删除操作的时间复杂度同样是$O(logn)$，其中初始搜索（找到要删除的元素）的时间复杂度是$O(logn)$，在树中重新结构化以维持高度平衡的时间复杂度也是$O(logn)$。