数据结构期末 · 线性表与树

这张图讲什么

「数据结构期末 · 线性表与树」是 SeekFlaw 编辑团队整理的思维导图,分 6 个一级分支:线性表:顺序表与链表;栈和队列;串与 KMP;二叉树;线索树、哈夫曼树与树森林;二叉排序树与平衡二叉树,共 84 个节点、83 张记忆卡,含 6 张配图、5 个视频片段。

这张图按「线性表 → 栈和队列 → 串与 KMP → 二叉树 → 线索树、哈夫曼树与树森林 → 二叉排序树与平衡树」六块展开。建议顺序:先把链表操作的指针顺序和栈队列的空满判断练熟,再做二叉树的性质与遍历计算,最后练哈夫曼构造和平衡树旋转。

5 个要点

  • 线性表:顺序表与链表——线性表题目的核心是比较顺序存储与链式存储的复杂度,以及链表操作中指针修改的先后顺序。
  • 栈和队列:栈后进先出、队列先进先出。
  • 串与 KMP:串的重点是模式匹配。
  • 二叉树:二叉树要熟练的三件事:性质计算(n0=n2+1、完全二叉树编号)、三种遍历及层序、由遍历序列还原树。
  • 线索树、哈夫曼树与树森林:这一枝分三块:线索二叉树利用空指针域存前驱后继;哈夫曼树和编码要会构造并算 WPL;树与森林要会与二叉树互相转换。

适用:大学期末复习。用法:点开任一节点先自己答,再翻面核对。

配图:单链表插入结点;双向链表插入结点;循环队列的队头队尾;二叉树三种遍历的访问次序;权为1、2、3、4的哈夫曼树;AVL 的 RR 与 LR 旋转。

更新于

一句话:这张图把「数据结构期末 · 线性表与树」整理成 84 个节点、83 张记忆卡;点开节点翻面就能看答案。

覆盖顺序表与链表、栈与队列、串与 KMP、二叉树性质与遍历、线索二叉树、哈夫曼树、二叉排序树与平衡二叉树,适合本科期末复习。点开任一节点翻面看答案,登录后可存进自己的空间,按遗忘曲线复习。

SeekFlaw 求瑕是面向初中、高中、考研、考公考前速记的思维导图与记忆卡平台:把课件、讲义变成思维导图,节点翻面就是记忆卡,按遗忘曲线安排复习。

84 个节点 · 83 张记忆卡 · 5 个视频片段。作者:SeekFlaw 编辑团队;发布于 2026-11-17。

先看这 3 条

  1. 顺序表有什么特点:顺序表逻辑相邻的元素物理上也相邻,可 随机存取 :按位序访问 O(1),按值查找 O(n),插入删除要移动元素,O(n);需要 预先分配连续空间 。
  2. 串、子串、空串、空格串各指什么:串是零个或多个字符组成的有限序列; 子串是主串中连续的一段 ;长度为 0 的是空串;由空格字符组成的是空格串, 长度不为 0 。
  3. 二叉排序树的定义和中序性质是什么:它是空树,或满足左子树所有结点的关键字小于根、右子树所有结点的关键字大于根,且左右子树也是二叉排序树。

线性表:顺序表与链表

  • 顺序表有什么特点:顺序表逻辑相邻的元素物理上也相邻,可 随机存取 :按位序访问 O(1),按值查找 O(n),插入删除要移动元素,O(n);需要 预先分配连续空间 。 易错 顺序表的存储密度为 1,但 扩容时要整体搬迁 。
  • 顺序表插入、删除各要移动多少元素:在第 i 个位置插入(i 取 1 到 n+1),要移动 n-i+1 个元素 ;删除第 i 个(i 取 1 到 n),要移动 n-i 个 。 例 长为 10 的顺序表在第 4 位插入,移动 7 个元素。 考法 等概率时,插入平均移动 n/2…
  • 顺序表与链表怎么选:经常随机访问、表长变化不大, 用顺序表 ; 经常插入删除 、表长变化大,用链表。 存储密度:顺序表为 1,链表小于 1(有指针域) 空间:顺序表要预分配,链表按需分配 按位序查找:顺序表 O(1),链表 O(n) 易错 链表插入删除本身 …
  • 头指针与头结点有什么区别:头指针指向链表第一个结点, 一定存在 ;头结点是放在首元结点之前、 不存数据 的附加结点, 可有可无 。带头结点使首元位置的插入删除与其他位置一致。 区分 带头结点的空表: L->next==NULL ;不带头结点的空表: L==NULL…
  • 单链表在 p 之后插入结点 s 怎么写:先 s->next=p->next; ,再 p->next=s; 。 顺序不能颠倒 ,否则先改了 p->next 就找不到原来的后继 。 例 链为 p→x,插入 s 后变为 p→s→x。 图:单链表在 p 之后插入 s,顺序是 ① s→n…
  • 单链表删除 p 的后继怎么写:令 q=p->next; ,再 p->next=q->next; ,最后 free(q); 。 先保存 q ,才能在改指针后释放它。 条件 p 必须有后继 ( p->next 非空)。
  • 只知道结点 p,怎样在 O(1) 时间删除 p:令 q 为 p 的后继, 把 q 的数据复制到 p ,再删除 q: q=p->next; p->data=q->data; p->next=q->next; free(q); ,不需要从头找前驱。 易错 p 是尾结点时不能这样做 ,只能从…
  • 头插法与尾插法建表有什么区别:头插法每次把新结点插到头结点之后,所建表 与输入次序相反 ;尾插法借助尾指针追加,所建表 与输入次序一致 。建 n 个结点的表都是 O(n)。 例 依次读入 1、2、3:头插得 3→2→1,尾插得 1→2→3。
  • 单链表如何原地逆置:利用头插思想:扫描原表,把每个结点依次插到头结点之后,时间 O(n), 额外空间 O(1) 。 步骤 1. 令 p 指向首元结点,头结点 next 置空 2. 用 q 记住 p->next 3. 把 p 插到头结点之后 4. p=q,重复…
  • 双向链表怎么插入、删除:在 p 之后插入 s 要改 4 个指针 ;删除 p 要改它前驱的 next 和后继的 prior。 步骤 插入: s->next=p->next; s->prior=p; p->next->prior=s; p->next=s; , 最后…
  • 循环链表怎么判空和判尾:循环单链表尾结点的 next 指回头结点。遍历的结束条件是 回到起点,不是 NULL ;带头结点时,空表是 L->next==L ,p 是尾结点是 p->next==L 。 记法 只设尾指针 r 时, r->next 是头结点, r->n…

栈和队列

  • 顺序栈 top 指针有哪些常见约定:栈是只在栈顶插入删除的线性表。常见约定一: top 初值为 -1,入栈 s[++top]=x ,空栈 top==-1 ,栈满 top==MaxSize-1 。约定二: top 初值为 0(指向下一个空位),入栈 s[top++]=x ,空…
  • n 个元素按序入栈,合法的出栈序列有多少种:有 $\frac{1}{n+1}\binom{2n}{n}$ 种( 卡特兰数 )。判断某序列是否合法:若某元素先出栈,则比它先入栈而尚未出栈的元素,必须按入栈次序的 逆序出栈 。 例 入栈次序 1,2,3,合法出栈序列有 123、132、…
  • 括号匹配怎样用栈判断:从左到右扫描:遇左括号入栈;遇右括号时看栈顶是否是对应的左括号,是则弹出,否则或栈空即不匹配; 扫描完栈必须为空 才合法。 例 {[()]} 合法; ([)] 在遇到 ) 时栈顶是 [ ,不匹配,非法。
  • 中缀表达式怎么转后缀表达式:从左到右扫描:操作数直接输出;运算符先把栈顶优先级 大于或等于它 的运算符弹出输出,再入栈; ( 入栈, ) 弹到 ( 为止;最后弹出全部运算符。 例 a+b*c-d 转成 abc*+d- ; (a+b)*c 转成 ab+c* 。 条件 …
  • 后缀表达式怎么求值:扫描后缀式:操作数入栈;运算符弹出两个操作数运算( 先弹出的是右操作数 ),结果再入栈;最后栈里唯一的数就是结果。 例 3 4 + 2 * :3、4 入栈, + 得 7,2 入栈, * 得 14。再如 8 2 3 * - :先算 2*3=…
  • 循环队列怎样判空、判满:本图采用「 少用一个单元 」的约定: front 指向队头元素, rear 指向队尾元素的下一位置;空队列 front==rear ;队满 (rear+1)%MaxSize==front ; 最多存 MaxSize-1 个 元素。 区分 …
  • 循环队列入队、出队与元素个数怎么算:入队: Q[rear]=x; rear=(rear+1)%MaxSize; ;出队:取走 Q[front] ,再 front=(front+1)%MaxSize; ;元素个数 (rear-front+MaxSize)%MaxSize 。 …
  • 链队列有什么要注意的:链队列用队头指针 front 和队尾指针 rear :入队接在 rear 之后,出队删去队头。带头结点时空队列满足 front==rear (都指向头结点)。 易错 出队若删掉的是最后一个结点,要把 rear 重新指回头结点,否则 rea…
  • 栈和队列有什么区别,各有什么应用:栈 后进先出 ,只在栈顶操作;队列 先进先出 ,队尾入、队头出。栈用于括号匹配、表达式、递归、深度优先搜索;队列用于层次遍历、广度优先搜索、缓冲区。 区分 两者都是 操作受限的线性表 ,都可用顺序或链式存储实现。
  • 怎样用两个栈实现一个队列:设入队栈 s1、出队栈 s2:入队时压入 s1;出队时若 s2 为空 ,就把 s1 全部弹出再压入 s2 ,然后弹出 s2 的栈顶。 例 依次入队 1、2、3,s1 自底向上为 1,2,3;出队时倒入 s2,s2 栈顶为 1,弹出得 1,…

串与 KMP

  • 串、子串、空串、空格串各指什么:串是零个或多个字符组成的有限序列; 子串是主串中连续的一段 ;长度为 0 的是空串;由空格字符组成的是空格串, 长度不为 0 。 例 字符互不相同、长为 n 的串,非空子串有 n(n+1)/2 个,再算空串则加 1。 abc 的非空子串是…
  • 朴素模式匹配怎么进行,复杂度如何:主串指针 i 与模式指针 j 逐个比较,失配时 i 回退到本趟起点的下一位 ,j 回到开头,重新比。 最坏时间 O(nm) ,n 是主串长、m 是模式长。 例 主串 aaaaab ,模式 aaab :起点 1、2 各比较 4 次后失配,起…
  • KMP 的核心思想是什么:主串指针 i 不回退 ;失配时模式指针 j 退到 next[j] ,利用已匹配部分的前后缀信息,跳过不可能成功的比较。匹配 O(n),求 next 为 O(m), 总共 O(n+m) 。 条件 next[j] 只与模式串自身有关, 与主串…
  • next 数组怎么求,采用什么约定:本图采用 下标从 1 开始 的教材约定: next[1]=0 ;j 不小于 2 时, next[j] 等于「模式前 j-1 个字符的 最长相等真前缀与真后缀的长度 」加 1。失配时令 j=next[j];若 j 变为 0,则 i、j 都加…
  • 例:求模式 abaabc 的 next 数组:abaabc 的 next 为 0 1 1 2 2 3 (j 从 1 到 6)。 步骤 - j=2:前 1 个字符 a,无真前后缀,k=0,next=1 j=3:前 2 个 ab,k=0,next=1 j=4:前 3 个 aba,公共 a…
  • 例:用 KMP 在主串中匹配:主串 abaabaabc ,模式 abaabc (next 为 0 1 1 2 2 3),匹配成功, 起点位置为 4 , 共比较 10 次 。 步骤 1. i=1 到 5 与 j=1 到 5 都相等,i=6 时主串 a 与模式 c 失配(…
  • nextval 是对 next 的什么改进:若 p[j]==p[next[j]] ,在 j 处失配后跳到 next[j] 必然再次失配 ,所以直接令 nextval[j]=nextval[next[j]] ;否则 nextval[j]=next[j] 。 例 模式 aaaab :n…

二叉树

  • 二叉树各层与全树最多有多少结点:第 i 层(i 从 1 起)至多 $2^{i-1}$ 个结点;高度为 h 的二叉树至多 $2^h-1$ 个结点,取到时即 满二叉树 ;n 个结点的二叉树高度 至少为 $\lceil\log_2(n+1)\rceil$。 例 h=4:第 4…
  • 叶子数 n0 与度为 2 的结点数 n2 有什么关系:任何非空二叉树都有 $n_0=n_2+1$。推导:总结点数 $n=n_0+n_1+n_2$,又分支数 $n-1=n_1+2n_2$, 联立消去 n 得结论。 例 度为 2 的结点有 5 个,则叶子有 6 个;若另有 3 个度为 1 的结点…
  • 完全二叉树的编号规律是什么:按层从上到下、每层从左到右,根编号为 1:结点 i 的左孩子是 2i,右孩子是 2i+1,双亲是 $\lfloor i/2\rfloor$( 孩子编号不超过 n 时才存在 )。 例 n=11:结点 5 的左孩子是 10、右孩子是 11;结…
  • n 个结点的完全二叉树高度和叶子数怎么算:高度为 $\lfloor\log_2 n\rfloor+1$,等于 $\lceil\log_2(n+1)\rceil$;叶子数为 $\lceil n/2\rceil$,叶子编号从 $\lfloor n/2\rfloor+1$ 到 n。度为…
  • 满二叉树与完全二叉树怎么区分:满二叉树每一层都是满的,高度 h 时恰有 $2^h-1$ 个结点, 没有度为 1 的结点 ;完全二叉树只要求编号 1 到 n 的结点与同高度满二叉树位置一一对应,叶子只在最后两层且 最后一层靠左 。 区分 满二叉树一定是完全二叉树 ,反之…
  • 二叉树与度为 2 的树有什么不同:二叉树是有序树,左右子树次序固定,只有一个孩子时也要分左右;度为 2 的树是一般的树, 子树不分左右 。度为 2 的树 至少有 3 个结点 ,二叉树可以只有 1 个或为空。 例 只有一个根和一个孩子的结构,作为二叉树有「左孩子」与「右孩子…
  • 二叉树怎么存储,二叉链表有多少空指针:顺序存储把结点按完全二叉树编号放进数组,适合完全二叉树,一般二叉树需补空位浪费空间;链式存储常用二叉链表,每个结点含 lchild 、 rchild 。 例 n 个结点的二叉链表共 2n 个指针域,其中 n-1 个非空 (每条边占一个),…
  • 前序、中序、后序遍历的次序是什么:前序:根、左、右; 中序:左、根、右 ;后序:左、右、根。每个结点访问一次,时间 O(n), 递归栈空间 O(h) ,h 为树高。 例 设 A 的左孩子为 B、右孩子为 C,B 的左右孩子为 D、E,C 只有右孩子 F。前序 ABDECF…
  • 层序遍历怎么实现:用队列:根入队;循环取队头访问,再把它的左、右孩子依次入队,直到队空。 例 设二叉树 A(B(D,E),C(,F))(A 的左孩子 B、右孩子 C,B 的左右孩子 D、E,C 只有右孩子 F),依次出队:A、B、C、D、E、F。 区分 前…
  • 非递归中序遍历怎么写:用栈保存待访问的根: 一路向左入栈 ,到空后弹出访问, 再转向它的右子树 。 步骤 1. p 非空:p 入栈, p=p->lchild 2. p 为空且栈非空:弹出栈顶并访问, p= 该结点的 rchild 3. p 为空且栈空时结束 例…
  • 由遍历序列能否唯一确定二叉树:前序加中序、后序加中序、层序加中序都能唯一确定; 前序加后序一般不能 (结点只有一个孩子时分不出左右)。 例 前序 ABDEC、中序 DBEAC:根为 A,中序分出左子树 DBE、右子树 C;左子树前序为 BDE,根为 B,中序中 D 在…
  • 哪些二叉树的两种遍历序列相同:前序与中序相同:每个结点都没有左孩子( 右斜树 );中序与后序相同:每个结点都没有右孩子( 左斜树 );前序与后序相同: 只有一个结点 (或空树)。 例 三个结点的右斜树 A→B→C,前序、中序都是 ABC。
  • 用递归求二叉树高度和叶子数的思路:高度: 空树为 0 ,否则为 max(左子树高度,右子树高度)+1 ;叶子数:空树为 0,叶子结点为 1,否则等于左右子树叶子数之和。 例 前面的树:D、E 的高度为 1,B 为 2,F 为 1,C 为 2,A 为 3;叶子为 D、E、F…

线索树、哈夫曼树与树森林

  • 为什么要线索化,ltag 与 rtag 是什么意思:二叉链表有 n+1 个空指针域 ,改存结点在某种遍历次序下的前驱和后继(线索),就能 不用栈和递归 地顺序遍历。 ltag=0 表示 lchild 是左孩子, ltag=1 表示它是前驱线索; rtag=1 表示 rchild 是后继线索。
  • 例:中序线索化后各线索指向哪里:树仍用前面那棵(A 的左孩子 B、右孩子 C,B 的孩子 D、E,C 只有右孩子 F),中序序列 DBEACF。线索:D 的右线索指向 B;E 的左线索指向 B、右线索指向 A;C 的左线索指向 A;F 的左线索指向 C, 共 5 条 。…
  • 中序线索树中怎样找前驱和后继:线索二叉树每个结点有 ltag 、 rtag :为 1 表示对应指针是线索,为 0 表示指向孩子。找后继:若 rtag=1 ,右指针就是后继;否则后继是 右子树中最左下的结点 。找前驱对称:若 ltag=1 ,左指针就是前驱;否则是 左子…
  • 前序、中序、后序线索树分别便于找前驱还是后继:中序线索树的 前驱和后继都容易找 ;前序线索树找后继容易,找前驱 要知道双亲 ;后序线索树找前驱容易,找后继要知道双亲。 条件 没有双亲指针(三叉链表)时,上述「要知道双亲」的情形只能借助栈或从根重新遍历。
  • 带权路径长度 WPL 怎么计算:叶子的权值乘以它 到根的路径长度 ( 经过的边数 ),对所有叶子求和:$WPL=\sum w_i l_i$。 例 权 1、2、3、4 的一棵树:4 在深度 1,3 在深度 2,1 和 2 在深度 3,则 WPL=4*1+3*2+1*3+2…
  • 哈夫曼树怎样构造:每次从森林中取 根权值最小的两棵树 合并,新根权值为二者之和,原来两棵删除、新树加入森林,重复到只剩一棵。 例 权 1、2、3、4:合并 1+2 得 3;森林 {3,3,4},合并两个 3 得 6;森林 {4,6},合并得 10。WPL …
  • 哈夫曼树的结构特点有哪些:n 个叶子的哈夫曼树共 2n-1 个结点 ,只有度 0 和度 2 的结点, 没有度为 1 的结点 ; 权值大的叶子离根近 ;它是带权路径长度最小的二叉树。 例 5 个叶子的哈夫曼树共 9 个结点,其中 4 个是内部结点。
  • 哈夫曼编码怎么得到,有什么特点:在哈夫曼树上约定左分支记 0、右分支记 1(也可相反,须说明),从根到叶的路径就是该字符的编码。它是 前缀编码 ,任一编码都不是另一个编码的前缀, 译码无歧义 ;权大的字符编码短。 例 权 1、2、3、4 的哈夫曼树(1+2 合并得 3,…
  • 树怎样转换成二叉树:规则是「 左孩子右兄弟 」:结点的第一个孩子作为它的左孩子,下一个兄弟作为它的右孩子。单棵树转换后 根结点没有右孩子 。 例 根 R 有三个孩子 a、b、c:转换后 a 是 R 的左孩子,b 是 a 的右孩子,c 是 b 的右孩子。 条件…
  • 树、森林的遍历与二叉树遍历怎么对应:树的 先根遍历对应其二叉树的前序 遍历,树的 后根遍历对应其二叉树的中序 遍历;森林的先序、中序遍历分别对应其二叉树的前序、中序遍历。 例 树根 R 有三个孩子 a、b、c:先根 Rabc,后根 abcR;转换成的二叉树(R 的左孩子 a…
  • 森林转成二叉树后,叶子怎么数:森林中的叶子对应二叉树中「 没有左孩子 」的结点,因为左孩子表示第一个孩子,没有孩子就是叶子。 例 树 R(a,b,c) 转换后,a、b、c 都没有左孩子,对应 3 个叶子;R 有左孩子,不是叶子。
  • 树有哪几种存储结构:双亲表示法:数组存结点和其双亲下标, 找双亲 O(1),找孩子要遍历 。孩子表示法:每个结点挂孩子链表,找孩子方便,找双亲要遍历。孩子兄弟表示法:每结点存第一个孩子和下一个兄弟, 本质是二叉链表 。 区分 孩子兄弟表示法找某结点的所有孩子…
  • 二叉树怎样还原成树或森林:这是「左孩子右兄弟」的逆过程:若结点 x 是某个结点 y 的左孩子,则沿 x 的 右链上的所有结点 (x 的右孩子、右孩子的右孩子……)都变成 y 的孩子;最后去掉原来的右链连线。若根有右链, 还原的是森林 。 例 二叉树:根 R 的左孩…
  • 并查集的 Find 与 Union 怎么做:并查集用树表示集合,用双亲数组存储:Find 沿双亲找到所在集合的根;Union 把一个集合的 根挂到另一个的根下 。Kruskal 用它判断两端点是否同属一个连通分量。 记法 不优化时 Find 最坏 O(n);按秩(或大小)合并使树高…
  • 树的结点数与度数有什么关系:树的结点数等于所有结点的 度数之和加 1 。度为 m 的树第 i 层至多 $m^{i-1}$ 个结点。 例 度为 3 的树有 2 个度为 3、1 个度为 2、2 个度为 1 的结点,则总数为 1+(3·2+2·1+1·2)=11,叶子数为…

二叉排序树与平衡二叉树

  • 二叉排序树的定义和中序性质是什么:它是空树,或满足左子树所有结点的关键字小于根、右子树所有结点的关键字大于根,且左右子树也是二叉排序树。 中序遍历得到递增序列 。 例 依次插入 5、3、8、1、4:根为 5,3 在左、8 在右,1、4 是 3 的左右孩子;中序为 1 3 …
  • 二叉排序树怎样查找和插入:查找:与根比较,小则进左子树,大则进右子树,相等则成功,走到空则失败。插入:先查找,在失败位置的空指针处接新结点, 新结点总是叶子 。 例 依次插入 5、3、8、1、4 得到的树(根 5,3 在左、8 在右,1、4 是 3 的左右孩子)中…
  • 二叉排序树怎样删除结点:叶子直接删;只有一个孩子则由孩子顶替;有两个孩子则用 中序后继 (右子树最小结点)或 中序前驱 (左子树最大结点)的值替换它,再删除那个后继或前驱结点。 例 依次插入 5、3、8、1、4 得到的树(根 5,3 在左、8 在右,1、4 是 …
  • 二叉排序树的查找效率怎么样:平均 O(log n),取决于形态:接近完全二叉树时高度约 $\lceil\log_2(n+1)\rceil$; 最坏是单支树 ,高度 n, 查找 O(n) 。 例 关键字依次有序插入 1、2、3、4,得到右斜单支树,查找各结点比较 1、…
  • 平衡二叉树的定义与平衡因子:AVL 树是二叉排序树,且每个结点左右子树高度差的 绝对值不超过 1 。平衡因子等于左子树高度减右子树高度, 取值只能是 -1、0、1 。 易错 平衡因子的符号约定各教材不同(左减右或右减左),本图采用左减右。
  • 失衡后四种旋转怎么判断:以 最小失衡子树 (离新结点最近、平衡因子绝对值达 2 的结点 A)为准,看新结点插在 A 的哪个孩子的哪棵子树:LL(左孩子的左子树)右旋;RR 左旋; LR 先对 A 的左孩子左旋 ,再对 A 右旋;RL 先对 A 的右孩子右旋,再对…
  • 例:RR 型与 LR 型怎么转:依次插入 1、2、3:插入 3 后根 1 失衡( RR 型 ),对 1 左旋,得 2 为根、1 为左孩子、3 为右孩子。依次插入 3、1、2:插入 2 后根 3 失衡( LR 型 ),先对 1 左旋使 2 上来,再对 3 右旋,同样得到 …
  • 例:依次插入 10、20、30、40、50 构造 AVL:最终树为: 根 20 ,左孩子 10,右孩子 40,40 的左孩子 30、右孩子 50。 步骤 1. 插入 10、20、30: 10 失衡(RR) ,左旋得 20(10,30) 2. 插入 40:作为 30 的右孩子,无失衡 3. 插入 …
  • 高度为 h 的 AVL 树最少有多少结点:设最少结点数为 $N_h$,则 $N_h=N_{h-1}+N_{h-2}+1$,$N_0=0$,$N_1=1$。 例 N2=2,N3=4,N4=7,N5=12。所以 12 个结点的 AVL 树 高度最多为 5 (N6=20 超过 12)。
  • AVL 的删除与效率怎么样:查找、插入、删除都是 O(log n)。与插入不同,删除后的失衡 可能沿着到根的路径多次出现 ,需要 逐层向上检查并旋转 。 区分 普通二叉排序树最坏 O(n),AVL 靠旋转把高度控制在 O(log n)。

本图由 SeekFlaw 编辑团队整理。发现错误,欢迎到学习论坛指出。

打开这张导图:点节点翻面看答案 →