Huffman Tree

哈夫曼树/最优树：带权路径长度WPL最短的树

• 哈夫曼树中没有度为1的结点，又称为严格的（正则的）二叉树

• 树带权路径长度：树中所有叶子结点的带权路径长度之和 $WPL = \sum_{k=1}^n w_k l_k$

哈夫曼算法

哈夫曼算法：构建最小加权路径二叉树

• 输入：给定的n个权值${w_1, w_2, \cdots, w_n}$

• 初始化n个单节点二叉树集合$F={T_1, T_2, \cdots, T_n}$
• 合并权重最小的两棵树，将其权重之和作为新树权重记录于新树 根节点中
• 重复，直至生成单独一棵树

特点

• 贪婪算法
• Huffman算法构建的最优二叉树是只有叶子节点有权值，若所有 节点都有权值的最优二叉查找树，需要使用动态规划算法， 参见cs_algorithm/data_structure/tree_search

哈夫曼编码

• 哈夫曼编码：编码总长度最短的二进制前缀编码
• 前缀编码：任意编码都不是其他编码的前缀，此时编码可以

• 前缀编码可以使用二叉树设计，叶子结点代表字符，根节点到 叶子结点路径上分支代表的二进制串即为其二进制编码

• 对给定出现频率$P[1..n]$的字符集$C[1..n]$，生成哈夫曼树 即可得到哈夫曼编码

链式存储

哈夫曼树

1
2
3
4

typedef struct HTNode{
	unsigned int weight;
	struct HTNode *parent, *lchild, *rchild;
}HTNode, *HuffmanTree;

选拔树

优胜树

优胜树：非叶结点取值是两个孩子中较小者的完全二叉树

• 根据定义，根节点的取值是整个树的最小值
• 从叶节点构建/重构优胜树的过程中
  • 每对兄弟结点捉对比赛，胜利者晋升为父亲结点
  • 胜者逐级向上直到根节点为止
  • 调整优胜树的时间效率$\in \Theta(logk)$

顺序存储结构

1

typedef SqBiTree SqVictTree;

• 数组实现的二叉树可以通过完全二叉树性质迅速计算父节点、 孩子节点位置

淘汰树

淘汰树：非叶结点值是两个孩子结点中较大者，即指向失败者的 选拔树

• 可以简化选拔树重构过程
• 需要额外结点记录/指向胜者

用途

归并多路有序序列

• 问题：k路有序（降序）序列，要将其归并为一组有序序列， 归并过程每轮输出一个最小关键字记录 （显然只能是当前k路序列中第一个记录）

• 以k路序列首k个元素建立k个叶节点的选拔树

• 构建选拔树，输出最小元素值

  

• 用其所属序列下个元素替换其所在叶节点值，重构选拔

  

• 重复n轮：所有k轮归并总时间为$\in \Theta(nlogk)$

)$

树&森林

Free tree

自由树：连通、无回路图，具有一些其他图不具有的重要 特性

• 边数总比顶点数少一：$|E|=|V|-1$

  • 这个是图为一棵树的必要条件，但不充分
  • 若图是连通的，则是充分条件

• 任意两个顶点之间总是存在简单路径

(Rooted)Tree

（有根）树：存在根节点的自由树

• $root$：根节点数据元素
• $F=(T_1, T_2, \cdots, T_m)$：森林
• $T_i=(r_i, F_i)$：根root的第i棵子树

• 在任意一棵非空树中

  • 有且仅有一个特定称为根的节点
  • 节点数n>1时，其余节点可以分为m个互不相交的有限集 ，每个集合本身又是一棵树，称为根的子树

• 树中任何两个节点间总存在简单路径，所以可以任选自由树 中某节点，作为有根树的根

• 有根树远远比自由树重要，所以也简称为树

  • 根一般放在树的顶层，第0层
  • 之后节点根据和根的距离放在相应层数

Forest

森林：无回路但不一定连通的图

• 其每个连通分量是一棵树
• 对树中每个节点，其子树集合即为森林

Ordered Tree

有序树：所有顶点的所有子女都是有序（不能交换次序）的有根树

应用

• 常用于描述层次关系

  • 文件目录
  • 企业的组织结构
  • 字典的实现
  • 超大型的数据集合的高效存储
  • 数据编码

• 用于分析递归算法

  • state-space tree：状态空间树，强调了两种算法设计 技术：回溯、分支界限

结构

• ancestor：从根到该顶点上的简单路径上的所有顶点
• proper ancestor：除自身外的所有祖先顶点
• parent：从根到顶点简单路径中，最后一条边的另一端节点
• parental：至少有一个子女的顶点
• child：
• sibling：具有相同父母的顶点
• leaf：没有子女的顶点
• descendent：所有以该顶点为祖先的顶点
• proper descendent：不包括顶点自身的子孙
• subtree：顶点的所有子孙、连接子孙的边构成以该顶点为根的 子树
• depth：根到该顶点的简单路径的长度
• height：根到叶节点的最长简单路径的长度

链式存储结构

• 链表结点代表树中一个顶点，其中至少包含：数据域、指向子女 的指针域
• 链表头指针指向二叉树根节点

双亲表存储

双亲表示法

• 利用除根节点外，每个结点只有一个双亲，给所有结点添加一个 指向双亲的指针域

1
2
3
4
5
6
7
8

typedef struct PTNode{
	TElemType data;
	int parent;
}PTNode;
typedef struct{
	PTNode nodes[MAX_TREE_SIZE];
	int r, n;
}PTree;

• 求结点双亲时是常数时间
• 求结点孩子时需要遍历整个结构

孩子链表存储

孩子表示法

• 把每个结点的孩子结点排列起来，视为线性表，以单链表作为 存储结构

  • 否则结点同构则浪费空间，不同构时操作不方便

    

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

typedef struct CTNode{
	// 逻辑意义的结点，存储兄弟关系
	int child;
		// 结点位置，`nodes`中序号
	struct CTNode *next;
		// 指示下个兄弟结点
}*ChildPtr;
typedef struct{
	// 实际存储信息的结点
	TElemType data;
	ChildPtr firstchild;
		// 孩子链表头指针
}CTBox;
typedef struct{
	CTBox nodes[MAX_TREE_SIZE];
	int n, r;
		// 节点数，根节点位置
}CTree;

二叉链表存储

First Child-next Silbling Representaion：孩子兄弟/二叉链表 /二叉树表示法

• 每个节点只包含两个指针，左指针指向第一个子女，右指针指向 节点的下一个兄弟
• 节点的所有兄弟通过节点右指针被单独的链表连接

1
2
3
4

typedef struct CSNode{
	ElemType data;
	struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

• 可高效的将有序树改造成一棵二叉树，称为关联二叉树
• 易于实现某些操作
  • 寻找孩子结点

森林与二叉树转换

• 给定一棵树，可以以二叉链表为媒介导出树与二叉树之间的对应 关系，即可以找到唯一一棵二叉树和与之对应

  • 任何一棵树对应的二叉树，其右子树必然为空

• 将森林中各棵树的根节点看作兄弟结点，则可以得到森林和 二叉树的对应关系

森林转换为二叉树

森林$F={T_1, T_2, \cdots, T_M}$转换为二叉树的 $B=(root, LB, RB)$

• 若F为空，即m=0，则B为空树
• 若F非空
  • root即为森林中第一个树的根$ROOT(T_1)$
  • LB是从$T_1$中根节点的子树森林转换而成的二叉树
  • RB是从森林$F^{‘}$转换而来的二叉树

二叉树转换为森林

二叉树的$B=(root, LB, RB)$转换为森林 $F={T_1, T_2, \cdots, T_M}$

• 若B为空，即m=0，则F为空树
• 若B非空
  • F中第一棵树根$ROOT(T_1)$即为二叉树根root
  • $T_1$中根节点的子树森林$F_1$是由B的左子树LB转换来的 子树森林
  • F中除$T_1$外的其余树组成的森林$F^{‘}$是由B的右子树 RB转换而来的子树森林

树、森林遍历

• 以二叉链表作树、森林的存储结构式，树、森林的先（根）序 遍历、后（根）序遍历对应二叉树先序、后序遍历

Binary Tree

二叉树：所有顶点子女个数不超过2个，每个子女不是父母的 left child就是right child的有序树

• 二叉树的根是另一棵二叉树顶点的左（右）子女
• 左右子树也是二叉树，所以二叉树可以递归定义
• 涉及二叉树的问题可以用递归算法解决

特点

• 二叉树第i层之多有$2^{i-1}$个节点
• 深度为k的二叉树最多有$2^k-1$节点

• 对任何二叉树$T$，如果其终端节点数$n_0$，度为2的节点数为 $n_2$，则$n_0=n_2+1$

  $$\left. \begin{array}{r} 考虑节点数：n = n_0 + n_1 + n_2 \\ 考虑分支数：n = n_1 + 2n_2 + 1 \end{array} \right \} \rightarrow n_0 = n_2 + 1$$

  • $n, n_0, n_1, n_2$：总结点数、终端节点数、度1节点数 、度2节点数

顺序存储结构

完全二叉树

顺序存储结构：顺序存储完全二叉树结点元素

1
2

typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;

• 将完全二叉树编号为i的结点存储在一维数组中下标为i-1分量中
• 一般二叉树则将每个结点与完全二叉树结点相对照，存储在相应 分量中，并标记不存在的结点
  • 对某些二叉树空间利用效率极低
  • 所以顺序存储结构只适合完全二叉树

链式存储结构

• 二叉树的链表节点中至少包含3个域：数据域、左右指针域
• 链表头指针指向二叉树根节点
  • 为方便，也可以添加一个头结点，其lchild指针域指向 根结点

二叉链表

1
2
3
4

typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

• 含有n个结点的二叉链表中有n+1个空链域

三叉链表

1
2
3
4

typedef struct BiTriNode{
	TElemType data;
	struct BiTriNode *parent, *lchild, *rchild;
}BiTriNode, *BiTriTree;

• 在二叉链表基础上增加指向双亲结点的指针域

二叉线索链表

Threaded Binary Tree：线索二叉树/线索化树

• 使用二叉链表中的n+1个空链域存放二叉树遍历的前驱、后继 信息
• 附设标记域区分指针域存放子孙结点、前驱/后继

• 适合经常需要遍历的二叉树、查找遍历所得线性序列中前驱、 后继
  • 时间复杂度常数系数小
  • 无需设栈

1
2
3
4
5
6

typedef enum PointerTag{Link, Thread};
typedef struct BiThrNode{
	TElemType data;
	struct BitThrNode *lchild, *rchild;
	PointerTag LTag, RTag;
}BiThrNode, *BiThrTree;

• 后序线索化树找后继时需要知道双亲，应该使用带标志域的 三叉链表

Complete Binary Tree

• 满二叉树：深度为k且有$2^k-1$节点的二叉树，每层上的节点数 都是最大节点数

• 完全二叉树：essentially complete，树的每层都是满的，除 最后一层最右边的元素（一个或多个）可能有缺位

特点

• 只存在一棵n个节点完全二叉树，高度为 $\lfloor log_2 n \rfloor$

  • 深度为k、节点数为n的完全二叉树同深度为k的满二叉树中 1-n号节点一一对应
  • 叶子节点只可能在层次最大的两层上出现
  • 对任一节点，其左分支只能和右分支深度相同或大1

• 从上到下、从左到右对结点编号，即使用数组H存储完全二叉树 （从1开始编号，数组H[0]不存储节点值，或存放限位器）

  • 父母节点键会位于数组前$\lfloor n/2 \rfloor$个位置中 ，叶子节点位于后$\lceil n/2 \rceil$

  • 对位于父母位置i的键，其子女位于2i、2i+1，相应的对于 子女位置i的键，父母位于$\lfloor i/2 \rfloor$

应用

• 堆

二叉树高度

• 将空树高度定义为-1

算法

1
2
3
4
5
6
7
8

Height(T):
	// 递归计算二叉树的高度
	// 输入：二叉树T
	// 输出：T的高度
	if T = null_set
		return -1
	else
		return max{Height(T_left), Height(T_right)} + 1

特点

• 检查树是否为空是这个算法中最频繁的操作

• 算法时间效率

  • 树的节点数为n，则根据加法操作次数满足递推式 $A(n(T))=A(n(T{left})) + A(n(T{right})) + 1$， 得到$A(n(T)) = n$

  • 考虑为树中每个节点的空子树添加外部节点得到 扩展树，则外部节点数量x满足$x=n+1$

  • 检查树是否为空次数即为扩展树节点数目 $C(n(T))=n+x=2x+1$

二叉树遍历

• 不是所有关于二叉树的算法都需要遍历两棵子树，如：查找、 插入、删除只需要遍历两颗子树中的一棵，所以这些操作属于 减可变规模（减治法）

• 先序、中序、后序遍历都需要用到栈

• 中序遍历得到的序列称为中序置换/中序序列，先序、后序类似

递归版本

• Preorder Traversal：先序

  1 2 3 4 5 6

  PreOrder(T): visit(T) if T_left not null: PreOrder(T_left) if T_right not null: PreOrder(T_right)

• Inorder Traversal：中序

  1 2 3 4 5 6

  InOrder(T): if T_left not null: InOrder(T_left) visit(T) if T_right not null: InOrder(T_right)

• Postorder Traversal：后序

  1 2 3 4 5 6

  PostOrder(T): if T_left not null: PostOrder(T_left) visit(T) if T_right not null: PostOrder(T_right)

栈非递归

• 先序遍历

  • 深度优先入栈：左子树优先入栈

    • 节点先访问后入栈，栈内存已访问节点

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

    PreOrder(T): s = InitStack() cur = T while s.not_empty() or cur: while cur: visit(cur) s.push_back(cur) cur = cur.left cur = s.pop() cur = cur.right // 等价写法，仅使用`if`利用外层循环 PreOrder(T): s = InitStack() cur = T while s.not_empty() or cur: if cur: visit(cur) s.push_back(cur) cur = cur.left else: cur = s.pop() cur = cur.right

    • 基于对遍历性质的考虑
    • 扩展性较好，可以扩展到中序、后序遍历

  • 广度优先入栈：同层右、左节点先后入栈

    1 2 3 4 5 6 7 8 9 10

    PreOrder(T): s = InitStack() s.push_back(T) while s.not_empty(): cur = s.pop() if cur.right: s.push_back(cur.right) if cur.left: s.push_back(cur.left) visit(cur)

• 中序遍历

  • 深度优先入栈

    • 节点先入栈后访问，栈内存未访问节点

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

    InOrder(T): s = InitStack() cur = T while s.not_empty() or cur: while cur: s.push_back(cur) cur = cur.left cur = s.pop() visit(cur) cur = cur.right // 等价写法，仅使用`if`利用外层循环 InOrder(T): s = InitStack() cur = T while s.not_empty() or cur: if cur: s.push_back(cur) cur = cur.left else: cur = s.pop() visit(cur) cur = cur.right

• 后序：需要标记当前节点左、右子树是否被访问

  • 深度优先入栈

    • 节点先入栈后访问，栈内存未访问节点
    • 记录最后一次访问节点，判断右子树是否被访问 （若右子树被访问，右子节点必然是上个被访问节点）

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

    PostOrder(T): s = InitStack() cur = T last = NULL while s.not_empty() or cur: while cur: s.push_back(cur) cur = cur.left cur = s.top() // 检查右子树是否被访问过 if cur.right == NULL or cur.right == last: visit(cur) last = s.pop() // 此时再弹出`cur` cur = NULL // 置`cur`为`NULL`，否则 // 再次访问左子树，死循环 else: cur = cur.right

  • 或者为每个节点附设标志位

层次遍历

• 队列实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

  # 判断节点是否存在、再填充至队列 LevelTraversal(T): q = InitQueue() cur = T while q.not_empty() or cur: if cur.left: q.push_back(cur.left) if cur.right:d q.push_back(cur.right) visit(cur) cur = q.pop_first() # 先填充、再判断节点是否为`None` # 填充可保证、适合节点位置和满二叉树对应 LevelTraversal(T): q = InitQueue() q.push(T) # 层次遍历使用队列实现，所以无需像栈一样使用 # 两个判断条件`q.not_empty or cur` while q.not_empty(): cur = q.pop_first() # 弹出时判断节点是否有效 if cur: visit(cur) q.push_back(cur.left) q.push_back(cur.right)

• 严格分层遍历：记录队列长度、遍历固定长度

  1 2 3 4 5 6 7 8 9 10 11 12 13

  LevelTraversal(T): q = InitQueue() q.push(T) while q.not_empty(): # 记录当前开始时队列长度 # 每轮遍历该长度数目元素，严格分层遍历节点 for i=0 to len(q): cur_node = q.pop_left() visit(cur_node) if cur.left: q.push_back(cur.left) if cur.right: q.push_back(cur.right)

树的计数

• 二叉树相似：二者为空树或二者均不为空树，且其左右子树分别 相似
• 二叉树等价：二者不仅相似，而且所有对应结点上的数据元素 均相同

• 二叉树的计数：n个结点、互不相似的二叉树数量$b_n$
• 树和一棵没有右子树的二叉树一一对应，所以具有n个结点不同 形态的树的数目，等于具有n-1个结点互不相似的二叉树数目

数学推导

二叉树可以看作是根节点、i个结点的左子树、n-i-1个结点的右子树 组成，所有有如下递推

求解得

遍历性质

• 给定结点的前序序列、中序序列，可以唯一确定一棵二叉树

• n个结点，不同形态二叉树数目恰是前序序列为$1 \cdots n$ 二叉树能得到的中序序列数目

• 中序遍历过程实质是结点进栈、出栈的过程，序列$1 \cdots n$ 按不同顺序进栈、出栈能得到排列的数目即为中序置换数目 $C{2n}^n - C{2n}^{n-1} = \frac 1 {n+1} C_{2n}^n$

K-dimentional Tree

Kd树：循环遍历各维度，按该维度取值二分数据

• 对高维数据进行快速搜索二叉树

  • 超平面都垂直于轴的BSPTree

• Kd树对样本点的组织表示对k维空间的划分

  • 每个节点对应k维空间中超矩形区域
  • 构造kd树相当于用垂直于坐标轴超平面不断划分k维空间， 得到一系列超矩形区域

• Kd树构建目标

  • 树应该尽量平衡，即分割应尽量均匀
  • 最大化邻域搜索的剪枝

建树

• 输入：数据点$X_i, i=1,2,\cdots,N$

• 确定划分维度（轴）
  • 选择方差最大的轴，使得数据尽量分散
  • 按次序循环遍历所有轴：方便查找时定位轴
• 选择该维度上数值中位数作为划分点
  • 中位数查找方法
    • 各维度统一全体排序、记录
    • 抽样，使用样本中位数
  • 小于中位数的数据点划分至左子树，否则划分至右子树
• 递归建立左、右子树直至无法继续划分
  • 节点中包含数据项数量小于阈值

查找K近邻

• 输入：Kd树、目标点x

• 在Kd树中找出包含目标点x的叶节点，以之为近邻点

  • 从根节点出发，与节点比较对应坐标值，递归访问至叶节点 为止
  • 目标点在训练样本中不存在，必然能够访问到叶节点

• 沿树回溯，检查节点是否距离目标点更近，尝试更新

• 检查该节点另一子区域是否可能具有更近距离的点

  • 即考察以目标点为圆心、当前近邻距离为半径圆，同划分轴 是否相交
  • 则只需比较目标点同相应切分平面距离、近邻距离

• 若目标点同该对应切分平面距离小于近邻距离

  • 则将目标节点视为属于该子区域中的点
  • 从节点未访问子树开始重复以上步骤，进行近邻搜索

• 否则继续回退

• 退回到根节点时，搜索结束，近邻点

• 回溯过程中需要盘对子域是否访问过，可以通过标记、比较相应 轴坐标等方式判断
• k>1的情况类似，不过检测时使用最远近邻，新近邻需要和所有 原近邻依次比较

其他操作

插入新节点

• 从根节点出发，根据待插入节点、当前节点在对应维度取值确定 插入左、右子树
• 遍历直至叶子节点，插入

删除节点

• 简单方法：将待删除节点子节点组成新集合，对其重新构建， 将新子树挂载在原被删节点位置

• 分类讨论：设删除节点T对应划分维度为D

  • 节点无子树：直接删除
  • 节点有右子树
    • 在右子树寻找维度D取值最小节点P，替换被删除节点T
    • 在右子树递归处理删除节点P
  • 节点无右子树有左子树
    • 在左子树寻找维度D取值最小节点P，替换被删除节点T
    • 将T的左子树作为P的右子树
    • 在右子树递归处理删除节点P

查找维度D最小点

• 若当前结点切分维度为D：只需查找左子树
• 否则需要对左、右子树分别递归搜索

Vantage Point Tree

VP树：任选样本点，按照数据点与该点距离二分数据

• 对高维数据进行快速搜索二叉树

• VP树对样本点的组织表示对k维空间的划分

  • 每个节点对应k维空间中一个球形划分
  • 构造kd树相当于用以给定样本点为球心不断划分k维空间， 得到一系列球内、球外区域

建树

• 输入：数据$X_i, i=1,2,\cdots,n$

• 选择某数据点$X_v$作为划分球心
• 计算其他数据点距离$D_i = d(X_i, X_v)$
• 求出$D_i$中位数$M$
  • 与$X_v$距离$D_i \leq M$的数据点$D_i$划分至左子树
  • 与$X_v$距离$D_i \gt M$的数据点$D_i$划分至右子树

Rectangle Tree

R树：将空间划分为有重叠的

• B树高维推广
  • 类似B树将一维区间划分为多个不重叠的子区间
  • 同样是平衡树，所有叶子位于同一层上

• R树退化至1维有分割区间重叠问题，效果不如B树

性质

• $M$：节点中最大键数量
• $m \leq \frac M 2$：节点中条目最小数量

• 非根叶节点包含$m-M$索引记录：$I$表示可在空间中完全覆盖 节点中条目点的MBR

• 非根、非叶节点包含$m-m$个子节点：$I$表示可在空间中完全 覆盖节点中条目矩形的MBR

• 根节点条目数$[2, m]$，除非为叶子节点

• minimal bounding rectangle：MBR，最小边界矩形

节点结构

• 叶子节点结构：$(I, tuple-ids)$

  

  • $I((s_1, e_1), (s_2, e_2), \cdots, (s_n, e_n))$： n维空间中矩形
  • $tuple-ids$：节点包含的记录

• 非叶节点：$(I, child-pointer)$

操作

建树

矩形搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

SearchRect(T, S, ret):
	// 利用R树搜索矩形范围中包含的记录点
	// 输入：R树根节点T、待搜索矩形S
	// 输出：矩形S覆盖的条目

	if T.I join S == NULL:
		return

	// 若T不是叶子节点，检查其每个条目E
	if not T.is_leaf():
		for E in T.entries:
			// 对与S相交E.I对应条目E，递归调用搜索
			if T.I join S != NULL:
				SearchRect(E, S, ret)

	// 若T是叶子节点且T.I与S相交，检查其每个记录点
	elif T.I join S != NULL:
		for E in T.entries:
			if E in S:
				ret.add(E)

选择所属叶子

1
2
3
4
5
6
7
8
9
10
11
12
13

ChooseLeaf(T, E):
	// 在R树中寻找新索引条目所属叶子节点
	// 输入：R树根节点T、索引条目E
	// 输出：E所属R树中叶子节点

	if T.is_leaf():
		Assert(E.is_subset(T))
		return T

	else:
		for T_E in T.entries:
			if E.is_subset(T_E)
				return ChooseLeaf(T_E, E) or T_E

插入新条目

1
2
3
4
5
6
7
8
9
10
11
12

Insert(T, E):
	// 向R树中插入新条目
	// 输出：R树根T、新条目E

	L = ChooseLeaf(T, E)
	if L.has_slot():
		L.add(E)
	else:
		LL = L.split()
		L.add(E)
		P = L.get_parent()
		

调整树

1
2
3
4
5
6
7
8
9
10
11
12
13
14

AdjustTree(T, L):
	// 从不满足节点开始调整R树至满足要求
	// 输入：R树根T、不满足要求节点L
	// 输出：

	if L.is_root():
		return

	P = L.get_parent_node()
	if L.splitted():
		NN = L.get_split_node()
		if P.
	// 调整节点L在父节点中矩形框I大小
	addjust_I(P.L.I)

R*-tree

X-tree

SS-tree

SR-Tree

Metric-tree

总述

• 二叉查找树：最基础的查找树，但是不平衡时效率很差
• 自平衡查找树：使用旋转技术得到平衡二叉树
• 多路查找树：使用多叉树达到平衡

• 树高度一般即决定其查找、插入、删除效率
• 以代码复杂性、插入节点时间代价，换取查询时$logN$性能

Self-Balancing Binary Tree

自平衡查找树：如果节点插入、删除产生了一棵违背平衡要求的树， 就从称为旋转的一系列特定变换中选择一种，重新构造树使得 树满足平衡要求

• 不同的对平衡的定义产生了不同的实现
• 这种方案属于变治法中实例化简

Balance Factor

平衡因子：节点左、右子树高度差（一般右树-左数）

• AVL树中平衡情况下节点平衡因子只能为-1、+1、0

• 更新节点后可能存在不平衡节点，其平衡因子可能变为-2、+2

• 平衡因子也可以被定义为左右子树叶子数

Rotation

旋转需要使得二叉树平衡时，保证二叉树依然有序

• 左旋：节点平衡因子符号为正，即右子树高于左子树

  • 节点T下沉为其右儿子R的左儿子
  • 如果右儿子R本身有左子树RL，则左子树RL成为节点T 新右子树

• 右旋：节点平衡因子符号为负，即左子树高于右子树，

  • 节点T下沉为其左儿子L的右儿子
  • 如果左儿子L本身有右子树LR，则右子树LR成为节点T 新左子树

• 旋转只涉参与选择的至多3个节点指针变化，其余节点状态保持
• “旋转”行为确实类似：节点绕其子节点旋转，子节点旋转后上浮 成为父节点
• 参与旋转的两个节点也称为轴

分类

• AVL树
• 红黑树
• 分裂树

Multiway Search Tree

多路查找树：允许查找树中单个节点中不止包含一个元素

• 二叉查找树的推广，用于磁盘超大数据集的高效存取
• 此方案属于变治法中改变表现

分类

• 2-3树
• 2-4树
• B树
• B+树

Binary Search Tree

二叉查找树：分配给每个父母顶点的数字都比其左子树中数字大， 比右子树数字小

• 二叉树有序，保证二叉树能够快速找到中间元素，从而支持 二分查找

特点

• 对于n个顶点的二叉树，满足 $ \lfloor {log_{2}^{n}} \rfloor \leq h \leq n-1 $

• 二叉查找树的查找算法效率取决于二叉树的高度

  • 平均情况下，查找、插入、删除时间$\in Theta(logn)$

  • 最差情况下（严重不平衡的树，接近链表结构），树高度 h接近节点数n，查找、插入、删除时间$\in Theta(n)$

• 包含n个键的二叉查找树总数量 $c(n) = \frac 1 {n+1} C_{2n}^n, c(0)=1$

应用

• 查找

操作

查找

在给定二叉查找树中查找给定键值K

• 如果树为空，查找失败

• 若树不为空，将查找键K和树根节点K(r)比较

  • 相等则查找停止
  • $K < K(r)$：在左子树中继续查找
  • $K > K(r)$：在右子树中继续查找

特点

• 算法时间效率
  • 最差情况下，二叉树完全偏斜，需要进行n次比较
  • 随机情况下，查找n个随机键构造的二叉树比较次数$2logn$

插入

除非是空树，否则总是把新键K插入叶子节点中

• 通过查找K确定合适插入位置（叶子节点）
• 若K大于叶子节点键值，则作为右子女，否则作为左子女

最优二叉查找树

对集合中元素确定的查找概率，成功查找的平均比较次数最小的 二叉查找树（可以扩展到包含不成功查找）

• $a_i, i=1,2,\cdots,n$：从小到大互不相等的键
• $p_i, i=1,2,\cdots,n$：键查找概率
• $T_i^j$：由键$a_i, \cdots, a_j$构成的二叉树
• $C(i, j)$：成功查找的最小平均查找次数

动态规划构造

• 根据最优化法则，最优二叉查找树左右子树均是最优排列的

• 二叉树$Ti^j$有序，设树根为$a_1$，$a_2,..,a{k-1}$构成 的左子树、$a_{k+1},..,a_j$构成右子树均是最优排列的

递推式如下

• $1 \leqslant i \leqslant j \leqslant n$

  $$\begin{align} C(i, j) & = \min_{i \leqslant k \leqslant j} \{p_k + \sum_{s=i}^{k-1} p_s * (a_s在T_i^{k-1}中层数 + 1) + \sum_{s=k+1}^j p_s * (a_s在T_{k+1}^j中层数 + 1) \}\\ & = \min_{i \leqslant k \leqslant j} \{ \sum_{s=i}^{k-1} p_s * a_s在T_i^{k-1}中层数 + \sum_{s=k+1}^j p_s * a_s在T_{k+1}^j中层数 + \sum_{s=i}^j p_s \} \\ & = \min_{i \leqslant k \leqslant j} \{C(i, k-1) + C(k+1, j)\} + \sum_{s=i}^j p_s \end{align}$$

• $1 \leqslant i \leqslant n+1, C(i, i-1)=0$：空树

• $1 \leqslant i \leqslant n, C(i, i)=p_i$：单节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

OptimalBST(P[1..n])
	// 动态规划法构建最优二叉查找树
	// 输入：P[1..n]n个键查找概率
	// 输出：在最优BST中查找成功的平均比较次数，最优BST子树根表
	for i = 1 to n do
		C[i, i-1] = 0
		C[i, i] = P[i]
		R[i, i] = i
	C[n+1, n] = 0
		// 初始化平均查找次数表、子树根表
	for d = 1 to n-1 do
		// d为二叉树节点数
		for i = 1 to n-d do
			// n-d是为了控制j的取值
			j = i + d
			minval = \infty
			for k = i to j do
				// 遍历设置二叉树根节点
				if C[i, k-1] + C[k+1, j] < minval
					minval = C[i, k-1] + C[k+1, j]
					kmin = k
			R[i, j] = kmin
			sum = P[i]
			for s=i+1 to j do
				sum += P[s]
			C[i, j] = minval + sum
	return C[1, n], R

算法特点

• 算法效率
  • 算法时间效率为立方级
  • 算法空间效率为平方级

AVL Tree

AVL树：要求其节点在左右子树高度差不能超过1的平衡二叉树

• 基本思想：总能通过一次简单的节点重排使树达到平衡

  • 如果树插入操作使得一棵AVL树失去平衡，利用旋转对树作 变换
  • 若有多个这样的节点，找出最靠近新插入的叶子节点不平衡 结点，然后旋转以该节点为根的子树

• AVL树高度h即为其查找、插入效率

  • 包含n个节点AVL树高度h满足 $\lfloor log_2 n \rfloor \leq h < 1.4405log_2(n+2) - 1.3277$

  • 最差情况下，操作效率$\in \Theta(logn)$

  • 平均而言，在n不是太小时，高度h平均为 $1.01log_2 n + 0.1$（几乎同折半查找有序数组）

• AVL树缺点（平衡代价），阻碍AVL树成为实现字典的标准结构

  • 需要频繁旋转
  • 维护树的节点平衡
  • 总体比较复杂

旋转

按照节点平衡符号进行旋转：+左旋、-右旋

• 单旋：不平衡节点、不平衡子节点不平衡因子符号相同

  • 全为+：不平衡节点左旋
  • 全为-：不平衡节点右旋

• 双旋：不平衡节点、不平衡子节点不平衡因子符号不同

  • 先旋转不平衡子节点
  • 再旋转不平衡节点

• 优先考虑最底层、不平衡节点

插入节点

AVL树插入关键：查找不平衡节点

• 节点中应有存储其平衡因子的实例变量
• 插入过程中经过每个节点返回当前节点子树深度是否变化
• 比较节点平衡因子、子节点深度变化返回值判断是否平衡

• 插入过程中查询的每个节点都有可能不平衡
• 自下而上返回深度变化情况，优先旋转最底层不平衡节点

4种插入情况

根据插入情况的不同，对最靠近新插入叶子节点的不平衡点T

LL

插入T左儿子L的左子树LL：平衡因子全-

• 即T到最底层叶节点（只可能有一个）的路径为LL（中间省略）
• R-rotation：右单转，对T做一次右旋即可平衡

RR

插入T右儿子R的右子树R：平衡因子全+

• 即T到最底层叶节点（只可能有一个）的路径为RR（中间省略）
• L-rotation：左单转，对T做一次左旋即可平衡

LR

插入T左儿子L的右子树R：平衡因子-+

• 即T到最底层叶节点（只可能有一个）的路径为LR（中间省略）
• LR-rotation：左右双转
  • 先对左儿子L做一次左旋，变成LL模式
  • 在LL模式下，再对T做一次右旋

RL

插入T右儿子R的左子树L：平衡因子+-

• 即T到最底层叶节点（只可能有一个）的路径为RL（中间省略）
• RL-rotation：右左双转
  • 先对右儿子R做一次右旋，变成RR模式
  • 在RR模式下，再对T做一次左旋

实现

删除节点

• 在AVL树中删除键相对而言比较困难，但也是对数级的

实现

Red-Black Tree

红黑树：能够容忍同一节点的一棵子树高度是另一棵的2倍

Splay Tree

分裂树：

2-3树

2-3树：可以包含两种类型的节点2节点、3节点，树的所有叶子节点 必须位于同一层

• 2-3树的高度即决定其查找、插入、删除效率

  • 节点数为n的2-3数高度h满足 $log_3(n+1)-1 \leq h \leq log_2(n+1) - 1$
  • 最差、平均情况下，操作效率$\in \Theta(logn)$

• 2-3树总是高度平衡

  • 所有叶子节点位于同一层，即树根到其路径长度相同
  • 2-3树平衡代价
    • 树中节点可以有1或2个键，需要处理2种节点类型
    • 拆分3节点的情况有很多种

• 节点类型

  • 2节点：只包含1个键K、2个子女

    • 左子女：作为所有键都小于K的子树的根
    • 右子女：作为所有键都大于K的子树的根

  • 3节点：两个有序键$K_1 < K_2$、3个子女

    • 最左边子女：作为键值小于$K_1$的子树的根
    • 中间子女：作为键值位于$[K_1, K_2]$之间子树的根
    • 最右边子女：作为键值大于$K_2$的子树的根

• 类似的还有2-4树

查找

• 如果根是2节点，当作二叉树查找

  • 若K等于根键值，停止
  • 若K小、大于根键值，在左、右子树中查找

• 若根是3节点

  • 和两个键值比较，有相等，停止
  • 否则能确定应该在3棵子树中哪棵继续查找

插入节点

除非是空树，否则总是把新键K插入叶子节点中

• 查找K确定合适的插入位置（叶子节点）

• 若叶子节点2节点，根据大小关系将K作为第一个键或第二个键 插入

• 若叶子节点3节点，把叶子分裂为两个节点：3个键中最小的放入 第一个叶子中，最大的放入第二个叶子中，中间的键提升到原 叶子节点父母中

  

  • 若叶子就是根，则需要创建新根容纳中间键
  • 中间键的提升可能会导致父母节点分裂，并引起祖先链条上 多个节点的分裂

删除节点

B树

B树：允许节点可以有$1~m-1$个键（$2~m$个子女）

1
2
3
4
5
6
7

#define BTREE_M
typedef struct BTNode{
	unsigned int degree;				// 节点实际包含键数
	KeyType key_slots[BTREE_M-1];		// 节点存储键数组
	struct BTNode ptr_slots[BTREE_M];	// 指向子女节点指针
	struct BTNode * ptr_parent;			// 父节点指针
}BTNode, *BTNodePtr;

• $m$：B树阶数，节点允许最大子女数

  • 节点最多允许有$m-1$个条目
  • $m=2$即为二叉树、$m=3$即为2-3树

• 键：用于构建树的关键字，和具体条目类似于键值对

• 根节点具有$2~m$个子女，除非为叶子节点

• 非根、非叶节点具有$[\lceil m/2 \rceil, m]$个子女

  • 即具有$[\lceil m/2 \rceil - 1, m]$个有序键

  • 其中子树$T_0$所有键小于$K_1$，子树$T_1$中所有键大于 等于$K_1$小于 $K_2$，以此类推

• B树是完美平衡的：所有叶子节点在同一层上

查找

算法

• 输入：B树、目标查找键
• 输出：查找键所属B树节点（若存在）

• 从根节点开始，比较查找键k和节点中键序列大小

  • 节点中键有序，若B树阶数足够大，可考虑折半查找

• 若在节点键序列中找到匹配键，则查找成功、返回

• 否则根据比较结果选择合适分支，顺着指针链前进，在相应子女 节点中进行查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

BTreeSearch(T, k):
	// 在B树中搜索键
	// 输入：B树根节点T、目标查找键k
	// 输出：目标键所在节点、目标键在节点中序号
	i = 0
	cur = T

	// 遍历寻找目标键对应键、分支
	while i < cur.degree and k > cur.key_slots[i]:
		i += 1

	if i < cur.degree and k == cur.key_slots[i]:
		return cur, i
	elif cur.is_leaf():			// 未找到目标键
		return cur, -1
	else:
		return BTreeSearch(cur.ptr_slots[i], k)

分裂

算法

• 输入：待分裂节点父节点、待分裂节点序号

• 计算待分裂节点分裂中心

  • 将分裂中心右侧数据移动至新节点

• 将节点分裂中心、新节点提升至父节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

BTreeNodeSplit(T, ptr_idx):
	// 分裂B树中节点
	// 输入：待分裂节点父节点`T`、待分裂节点序号`ptr_idx`

	nnode = BTreeNode()
	fnode = T.ptr_slots[ptr_idx]

	// 分裂中心
	mid = fnode.degree // 2

	// 复制右半部分键至新节点
	nnode.key_slots[:fnode.degree - mid] = fnode.key_slots[mid:fnode.degree]
	fnode.key_slots[mid:fnode.degree] = NULL

	// 若原节点非叶子节点，复制右半部分指针至新节点
	if not fnode.is_leaf():
		nnode.ptr_slots[:fnode.degree + 1 - mid] = fnode.ptr_slots[mid: fnode.degree + 1]
		fnode.ptr_slots[mid: fnode.degree+1] = NULL

	// 修改两节点度
	nnode.degree = fnode.degree - mid
	fnode.degree = mid

	// 将分裂中心提升至父节点
	// 修改父节点指向子女节点指针
	T.key_slots.insert(fnode.key_slots[mid], ptr_idx)
	T.ptr_slots.insert(nnode, ptr_idx+1)	// 原节点指针不变

插入

• 输入：B树根T、待插入键K
• 假设B树中不存在键K，否则查找、更新对应值即可

• 根据需要插入键K，查找需要插入的叶子节点L
• 若叶子节点L键数小于m-1，直接插入结束
• 否则以叶子节点键值中位数mid为中心分裂
  • 将mid插入叶子节点L父节点P中
  • 将mid左子支指向分裂后左子树、右子支指向分裂后右子树
• 对父节点尝试操作

1
2
3
4
5
6
7
8
9
10
11
12
13

BTreeInsert(T, k)
	// 向B树中插入不存在键K
	// 输入：B树根T、待插入键k

	// 找到键`k`应该插入的叶子节点`L`
	L, _ = BTreeSearch(T, k)
	L.key_slots.insert_in_order(k)


	// 若节点已满、须分裂
	while L.is_full():
		BTreeNodeSplit(L.parent_ptr, L.get_index())
		L = L.parent_ptr

• 此实现是考虑节点都有空位容纳新键，节点插入新键后再 判断是否需要分裂

删除#todo

应用

• 类似一般查找树，把数据记录插入初始为空的树中构造B树

B+树

B+树：B树的一种变形树

• 其中非叶节点只有索引作用，跟记录相关信息均存放在 叶结点中
• B+树中所有叶结点构成有序链表，可以按照键次序遍历

查找

算法

• 从根开始，比较查找键K和节点中键大小，选择合适指针，顺着 指针链前进

• 指针链指向可能包含查找键的叶子节点，在其中查找K

  • 父母节点、叶子节点都是有序的，如果B树次数足够 大，可以考虑使用折半查找

算法效率

以B树作索引存储大型数据文件为例

• 查找指定查找键访问B树节点数量为B树高度$h+1$ （即磁盘访问次数）

• 次数为m、高度为h的B树能够包含最少节点数为 $n \geqslant 4 \lceiling m/2 \rceiling ^ {h-1} -1$， 即$h \leqslant \lfloor log_{[m/2]} \frac {n+1} 4 \rfloor + 1$

• 所以在B树中查找，访问磁盘次数$\in O(logn)$

  • 实际应用中，磁盘访问次数很少超过3，因为B树的根、甚至 是第一层节点会存储在内存中减少磁盘访问次数

插入

算法

• 查找新记录键K对应的叶子节点

• 若叶子节点中还有空间存放此记录，在保持键有序的情况下插入

• 若节点中没有空间

  • 将节点分裂，后半部分记录放在新节点中
  • 新节点中最小键$K^{‘}$、指向其的指针插入原叶子节点 父母节点中（原叶子节点键、指针之后）
  • 插入过程可以一直回溯到树根，甚至直到树根分裂

其他考虑

• 查找新记录对应叶子节点时就分裂满节点，可以避免递归分裂
• 将满叶子节点中部分键移动给兄弟节点，同时替换父母节点中的 键值（保证B树特点），增加少许复杂度以节约空间

算法特点

• 算法效率
  • 算法时间效率$\in O(logn)$

应用

• B+树是存储结构化记录数据集合最重要的索引结构
  • 所有数据记录（键）按照升序存储在叶子节点中，其父母 节点作为索引
  • B+树中节点常常对应磁盘中页
  • 考虑到访问磁盘页面是比较内存中键值比较时间多好几个 数量级，磁盘访问次数是衡量B树效率的主要指标

标

Heap

堆/大根堆：每个节点包含一个键、且大于等于其子女键、基本完备 的二叉树

• 认为非叶子节点自动满足大于其子女键值
• 根到某个叶子节点路径上，键值序列递减（允许键值相等则是 非递增）
• 键值之间没有从左到右的次序，即树的同一层节点间没有任何 关系，或者说左右子树之间没有任何关系

堆特性

• 完全二叉树特性参见完全二叉树
• 堆的根总是包含了堆的最大元素
• 堆的节点及该节点子孙也是一个堆

• 堆这种数据结构经常被用于实现优先队列

最小堆

min-heap：（最大）堆的镜像

• 堆的主要特性最小堆也满足，但
  • 最小堆根节点包含最小元素
• 可通过给元素取反构造（最大）堆得到最小堆

堆算法

Bottom-Up Heap Construction

自底向上堆构造：先利用所有元素构造二叉树，从倒数第二层开始 修改使得整棵树满足堆要求

算法

• 将给定线性表对应为（初始化）一棵完全二叉树
• 对二叉树进行堆化，从最后父母节点开始、到根为止，算法检查 节点键是否满足大于等于其子女键
  • 若不满足，交换节点键K和其子女最大键值
  • 在新位置上检查是否满足大于子女键值，直到满足为止
• 对以当前节点为根的子树满足堆化条件后，算法对节点直接前趋 进行检查，直到树根满足堆化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

HeapAdjust(H[0..n-1], cur):
	// 左右子树已经为堆，仅根节点元素不一定满足
	// 输入：待调整堆H、根节点cur，cur左右子树已经为堆
	// 输入：调整后堆
	while 2*cur+2 < n:

		// 获取左右子女中最大者
		if 2*cur+2 < n:
			_tmp = argmax(H[2*cur+1], H[2*cur+2])
		else:
			_tmp = 2*cur+1

		// 交换自身和最大子女
		if H[_tmp] > H[cur]:
			swap(H[cur], H[_tmp])
			cur = _tmp
		else:
			// 从底向上建堆，左、右子树均为堆
			// 则此时已经满足堆性质
			break

	return H

HeapBottomUp(H[0..n-1]):
	// 用自底向上算法，从给定数组元素中构造一个堆
	// 输入：可排序数组H[0..n-1]
	// 输出：堆H[0..n-1]
	for i=floor((n-1)/2) to 0:
		HeapAdjust(H, i)
	return H

算法特点

• 算法效率
  • 时间效率：最差情况，每个位于树第i层节点会移到叶子层 h中，每次移动比较两次，则总键值比较次数 $C_{worst}=2(n-log_2(n+1))$ （将各层叶子节点可能交换次数加总即差比数列求和）

Top-Down Heap Construction

自顶向下堆构造算法：先利用部分元素构建堆顶，把新键连续插入 已经构造好的堆末尾，修改使之满足堆要求

算法

• 把包含键K的新节点附加在当前堆最后一个叶子节点
• 将K与其父母进行比较
  • 若后者大于K，算法停止
  • 否则交换这两个键，并比较K和其新父母，直到K不大于其 父母或是达到了树根

算法特点

• 算法效率
  • 操作所需键值比较次数小于堆高度$h \approx log_2 n$， 则总比较次数$\in \Theta(nlogn)$

删除堆根节点

算法

• 根键和堆中最后一个键K交换
• 堆规模减1（删除原根键）
• 按照自底向上堆构造算法，把K沿着树向下筛选使得新树满足 堆化

算法特点

• 算法效率
  • 效率取决于树堆化所需比较次数，不可能超过树高度两倍， 即$\in O(logn)$

堆排序算法

算法

• 为给定数组构造堆
• 删除最大键，即对堆应用n-1此根删除操作

算法特点

• 算法效率

  • 根删除阶段算法所需比较次数

    $$\begin{align} C(n) & \leq 2\sum_{i=1}^{n-1} \lfloor log_2i \rfloor \\ & \leq 2 \sum_{i=1}^{n-1} log_2(n-1) \\ & = 2(n-1)log_2(n-1) \end{align}$$

  • 两阶段总效率$\in O(nlogn)$

  • 详细分析证明，无论最差情况、平均情况下，时间效率 $\in \Theta(nlogn)$

• 堆排序时间效率和归并排序、快排时间效率属于同一类，但是 堆排序是在位的（不需要额外存储空间）

• 随机实验表明：堆排序比快排慢、和归并排序相比有竞争力