知识点梳理：数据结构与算法——高级数据结构

特殊矩阵

压缩思想：二维->一维

• 三角矩阵（对角线上/下为常数（不一定0））
• 稀疏矩阵：链式：十字链表；顺序：三元组表（一个元素：i,j,Aij；记录整体行数、列数、非0元个数T）

广义表

基本概念

线性表每个元素具有相同的数据类型

广义表：一个线性表中还包括一个或多个子表；一般记作 L = ( x 0 , x 1 , ⋯   , x n − 1 ) L=(x_0, x_1, \cdots, x_{n-1}) L=(x0​,x1​,⋯,xn−1​)

名称：L；长度：n

每个 x i x_i xi​是L的成员（ x i x_i xi​可以是单个元素：原子/广义表：子表）

广义表深度：表中元素都化解为原子后的括号层数

表头head= x 0 x_0 x0​；表尾tail= ( x 1 , ⋯   , x n − 1 ) (x_1, \cdots, x_{n-1}) (x1​,⋯,xn−1​)（表头是元素，表尾是表！！！）

分类

纯表：根结点到叶结点只有一条路径；任何元素（原子、子表）只能出现一次 【广义表的表示与latex中的forest表示相似】

可重入表（再入表）：表中元素可多次出现

循环表（递归表）：含回路，深度无穷大

线性表 ⊆ \subseteq ⊆纯表（树） ⊆ \subseteq ⊆再入表 ⊆ \subseteq ⊆图

广义表存储ADT：

tag=0(单元素)/1 (子表)	data/sublist(子表头指针)	next(后继结点)

增加头指针简化删除、插入（tag=-1）

Trie结构

消除BST的不平衡->改变关键码的划分方式

Trie（前缀树、字典树）:基于关键码分解的数据结构；有序树（与插入顺序无关）

关键码集合固定；对结点分层标记

时间复杂度只与表达这些元素的关键码长度有关，与元素个数无关（开始时就已确定可能出现的位置）

根结点不含字符

除根结点外每个结点一个字符，各不相同

根结点到某一结点路径经过字符连成结点对应的字符串

查找关键字效率与结点数无关，而取决于关键字字符数

Trie结构不是平衡的

应用：词频统计、前缀匹配、排序

PAT-tree：二叉Trie树，有压缩

最佳BST

基于用户访问习惯

普通的二叉搜索树：n个关键码不同排列BST树可能相同，有 C 2 n n − C 2 n n − 1 = 1 n + 1 C 2 n n C_{2 n}^{n}-C_{2 n}^{n-1}=\frac{1}{n+1} C_{2 n}^{n} C2nn​−C2nn−1​=n+11​C2nn​（Catalan数）种二叉搜索树

扩充二叉搜索树：每个外部结点代表其值处于原二叉搜索树的两个相邻结点关键码值之间的可能关键码的集合

最佳BST：

根据用户访问频率寻找ASL最小的二叉搜索树

构造方法：

任何子树都是最佳二叉搜索树->动态规划从下至上；逐步构造含i个关键码的最佳二叉搜索树

• 树定义T(i,j)：关键码： ( k e y i + 1 , k e y i + 2 , … , k e y j ) \left(ke y_{{i}+1}, {key}_{{i}+2}, \ldots, {key}_{{j}}\right) (keyi+1​,keyi+2​,…,keyj​)；

  内、外结点权值： ( q i , p i + 1 , q i + 1 , … , p j , q j ) \left({q}_{{i}}, {p}_{{i}+{1}}, {q}_{{i}+{1}}, \ldots, {p}_{{j}}, {q}_{{j}}\right) (qi​,pi+1​,qi+1​,…,pj​,qj​)

  查询代价（平均比较次数）：(根结点为第0层)

  C(i,j)= ∑ x = i + 1 j p x ( l x + 1 ) + ∑ x = i j q x l x ′ \sum_{x=i+1}^{j}p_x(l_x+1)+\sum^{j}_{x=i}q_xl'_x ∑x=i+1j​px​(lx​+1)+∑x=ij​qx​lx′​

• 对于子树T(i,j)：

  左子树：C(i,j)=W(i,j)+min(C(i,k-1)+C(k,j))（以k为根）(W(i,j)的意思是相当于每个结点加一层)

平衡BST（AVL）

基于树高平衡约束： ∣ h R − h L ∣ ≤ 1 |h_R-h_L|\leq 1 ∣hR​−hL​∣≤1

插入后失衡

• LL/RR

  单旋转（LL：-1结点转到-2位置；RR：1结点到2位置）

  

• LR/RL

  双旋/提升（最后那个不平衡结点提升到2位置（LR：-1；RL：1））

  

删除

与后继交换再删除

沿着被删除结点到根结点的路径调整变化（可能要向上回溯很多次）

情况：最下层不平衡发生在结点root开始的子树中；删除的是root左子树中的结点

初始时modified=true（意思是初始时每个结点在子树高度变化时失衡都会向上传递）

• b f ( r o o t ) = 0 bf(root)=0 bf(root)=0:bf改为1/-1，同时modified=false

  以root为根的子树高度不变，不影响祖先bf，调整结束

• b f ( r o o t ) ≠ 0 bf(root)\not=0 bf(root)​=0
  • 较高子树缩短：bf改为0，modified=true，继续向上修改
  • 较低子树缩短：root失衡
    • b f ( r i g h t ) = 0 bf(right)=0 bf(right)=0:单旋恢复root平衡，modified=false（子树高度未变，失衡不会向上传递）

      

    • b f ( r i g h t ) = b f ( r o o t ) bf(right)=bf(root) bf(right)=bf(root):单旋恢复root平衡，modified=true

      

    • b f ( r i g h t ) ≠ b f ( r o o t ) bf(right)\not=bf(root) bf(right)​=bf(root):双旋恢复root平衡，modified=true

      

      • right-left左重：

        

      • right-left右重：

        

      • right-left平衡：则最后root, right,right-left皆平衡，modified=true
    （right-left决定的是调整后左偏/右偏的结果，对操作没什么影响）

AVL Tree的扩展

放宽 Δ h \Delta h Δh的限制，使得调整次数变少

伸展树（splaying）

基于用户动态访问特征

不保证树高平衡

（据说这个东西多半是考应用（给出splaying tree的函数））

插入x：x移到根结点

删除x：x的父结点移到根结点

=>经常访问的结点就会在根结点附近活动

展开包括一系列旋转：（单、双，每次最多转两个，最后到根结点/根结点子结点（此时再单旋））

双旋转：

• 一字形（同构调整）：直接暴力转，调子树

  不会降低树结构高度

• 之字形（异构调整）：相当于提升

  使子树结构高度-1

伸展树不能保证每单个操作有效率（偶尔进行不常用的访问）

每次访问操作平均代价：O(log n)

比较