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)
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 == NULLor cur.right == last: visit(cur) last = s.pop() // 此时再弹出`cur` cur = NULL// 置`cur`为`NULL`，否则 // 再次访问左子树，死循环 else: cur = cur.right
# 判断节点是否存在、再填充至队列 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)
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-1do // 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$
SelectionSort(A[0..n-1]): // 选择排序排序数组 // 输入：可排序数组A[0..n-1] // 输出：升序排序数组A[0..n-1] for i = 0 to n-1 do min = i for j = i to n-1 do if A[j] < A[min] min = j swap A[i] and A[min]
BubbleSort(A[0..n-1]): // 冒泡排序排序数组 // 输入：可排序数组A[0..n-1] // 输出：升序排序数组A[0..n-1] for i = 0 to n-2 do for j = 0 to n-2-i do if A[j+i] < A[j] swap A[j] and A[j+1]
InsertionSort(A[0..n-1]) // 用插入排序对给定数组排序 // 输入：n个可排序元素构成数组 // 输出：非降序排序数组 for i = 1 to n-1 do v = A[i] j = i - 1 while j >= 0and A[j] > v do A[j+1] = A[j] j = j - 1 A[j+1] = v // 上一步比较元素已经赋值给其后，所以应该覆盖其值
ShellSort(A[0..n-1]) // 用插入排序对给定数组排序 // 输入：n个可排序元素构成数组 // 输出：非降序排序数组 h = 1 while h < n/3 h = h*3 + 1 // 获取初始h值，之后每轮h变为1/3 while h >= 1: for i = h to n-1: v = A[i] j = i - h while j >= 0and A[j] > v do A[j] = A[j-h] j = j - h A[j+h] = v h = h/3
特点
Shell排序全衡量子数组规模、有序性，更加高效
h递增序列
子数组部分有序程度取决于h递增序列的选择
不同的h递增序列对算法效率有常数倍的变动，但是在实际
应用中效果不明显
Shell排序是唯一无法准确描述其对于乱序数组性能特征的排序
方法
减常量法
归并排序
Mergesort
将需要排序的数组A[0..n-1]均分的
对两个子数组递归排序，然后把排序后的子数组合并为有序
数组
1 2 3 4 5 6 7 8 9 10
Mergesort(A[0..n-1]): // 递归调用MergeSort对数组排序 // 输入：可排序数组A[0..n-1] // 输出：非降序排列数组A[0..n-1] if n > 1: copy A[0..floor(n/2)-1] to B[0..floor(n/2)-1] copy A[floor(n/2)..n-1] to C[0..ceiling(n/2)-1] Mergesort(B[0..floor(n/2)-1]) Mergesort(C[0..ceiling(n/2)-11]) Merge(B, C, A)
Merge
初始两只指针指向待合并数组首个元素
比较两个元素大小，将较小元素添加到新数组中，被复制元素
的数组指针右移
重复直到某一数组处理完毕，将未处理完数组复制到新数组尾部
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Merge(B[0..p-1], C[0..q-1], A[0..p+q-1]): // 将两个有序数组合并为新的有序数组 // 输入：有序数组B[0..p-1]、C[0..q-1] // 输出：存放有B、C中元素的有序数组A[0..p+q-1] while i < p and j < q: if B[i] <= C[j] A[k] = B[i] i = i + 1 else: A[k] = C[j] j = j + 1 k = k + 1 if i == p: copy C[j..q-1] to A[k..p+q-1] else: copy B[i..p-1] to A[k..p+q-1]
ComparisonCountingSort(A[0..n-1]) // 用比较计数法排序 // 输入：可排序数组A[0..n-1] // 输出：将A中可排序数组按照升序排列数组 for i = 0 to n-1 do count[i] = 0 for i = 0 to n-2 do for j = i+1 to n-1 do if A[i] < A[j] count[j] += 1 else count[i] += 1 for i = 0 to n-1 do S[count[i]] = A[i]
特点
算法效率
算法比较次数为$n(n-1)/2$
占用了线性数量的额外空间
算法使得键值的可能移动次数最小化，能够直接将键值放在在
有序数组最终位置
输入增强
分布计数排序
待排序元素来自于某个已知小集合$[l..u]$
算法
扫描列表，计算、存储列表中元素出现频率于数组$F[l..u]$中
再次扫描列表，根据值填入相应位置
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
DistributionCountingSort(A[0..n-1], l, u): // 分布计数法排序，对元素来自有限范围整数的数组排序 // 输入：数组[0..n-1]，数组中整数位于l、u间 // 输出：A中元素构成非降序数组S[0..n-1] for j = 0 to u-l do D[j] = 0 for i = 0 to n=1 do D[A[i]-l] += 1 for j = 1 to u-l do D[j] += D[j-1] // 存储各元素最后出现索引+1 for i = n-1 downto 0 do j = A[i] - l S[D[j]-1] = A[i] D[j] -= 1 // 更新应该存储的位置，类似于压栈 return S
特点
算法效率
如果元素值范围固定，效率为线性（不是基于比较的排序，
$nlogn$没有限制）
用空间换时间，其实可以看作是hash
利用了输入列表独特自然属性
变治法（输入增强）
应用
判断线性表元素是否唯一
寻找线性表众数
快速查找
线性表顺序统计量
寻找列表中第k小的元素
也即：求出给定列表中k个最小元素问题
采用partitioning的思路，需要将给定列表根据某个值先行划分
Lumuto划分算法
QuickSelect算法
算法
对划分完后出数组，s为分割位置
若：s == k-1，则中轴p就是第k小元素
若：s < k-1，则应该是数组右边划分第k-s小元素
若：s > k-1，则应该是数组左边划分第k小元素
这样就得到规模更小的问题实例
1 2 3 4 5 6 7 8 9 10 11
QuickSelect(A[l..r], k) // 用基于划分递归算法解决选择问题 // 输入：可排序数组A[0..n-1]的子数组A[l..r]、整数k // 输出：A[l..r]中第k小元素 s = Partition(A[l..r]) if s = l+k-1 return A[s] elif s > l+k-1 QuickSelect(A[l..s-1], k) else QuickSelect(A[s+1..r], l+k-1-s)
LomutoPartition(A[l..r]) // 采用Lomuto算法，用首个元素作中轴划分数组 // 输入：可排序数组A[0..n-1]的子数组A[l..r] // 输出：A[l..r]的划分、中轴位置 p = A[l] s = l for i = l+1 to r if A[i] < p s = s+1 swap(A[s], A[i]) swap(A[l], A[s]) return s
