术语表

下表列出了书中出现的重要术语。建议记住各个名词的英文叫法，以便阅读英文文献。

表   数据结构与算法的重要名词

English	简体中文
algorithm	算法
data structure	数据结构
code	代码
file	文件
function	函数
method	方法
variable	变量
asymptotic complexity analysis	渐近复杂度分析
time complexity	时间复杂度
space complexity	空间复杂度
loop	循环
iteration	迭代
recursion	递归
tail recursion	尾递归
recursion tree	递归树
big-$O$ notation	大 $O$ 记号
asymptotic upper bound	渐近上界
sign-magnitude	原码
1’s complement	反码
2’s complement	补码
array	数组
index	索引
linked list	链表
linked list node, list node	链表节点
head node	头节点
tail node	尾节点
list	列表
dynamic array	动态数组
hard disk	硬盘
random-access memory (RAM)	内存
cache memory	缓存
cache miss	缓存未命中
cache hit rate	缓存命中率
stack	栈
top of the stack	栈顶
bottom of the stack	栈底
queue	队列
double-ended queue	双向队列
front of the queue	队首
rear of the queue	队尾
hash table	哈希表
hash set	哈希集合
bucket	桶
hash function	哈希函数
hash collision	哈希冲突
load factor	负载因子
separate chaining	链式地址
open addressing	开放寻址
linear probing	线性探测
lazy deletion	懒删除
binary tree	二叉树
tree node	树节点
left-child node	左子节点
right-child node	右子节点
parent node	父节点
left subtree	左子树
right subtree	右子树
root node	根节点
leaf node	叶节点
edge	边
level	层
degree	度
height	高度
depth	深度
perfect binary tree	完美二叉树
complete binary tree	完全二叉树
full binary tree	完满二叉树
balanced binary tree	平衡二叉树
binary search tree	二叉搜索树
AVL tree	AVL 树
red-black tree	红黑树
level-order traversal	层序遍历
breadth-first traversal	广度优先遍历
depth-first traversal	深度优先遍历
pre-order traversal	前序遍历
in-order traversal	中序遍历
post-order traversal	后序遍历
balanced binary search tree	平衡二叉搜索树
balance factor	平衡因子
heap	堆
max heap	大顶堆
min heap	小顶堆
priority queue	优先队列
heapify	堆化
top-$k$ problem	Top-$k$ 问题
graph	图
vertex	顶点
undirected graph	无向图
directed graph	有向图
connected graph	连通图
disconnected graph	非连通图
weighted graph	有权图
adjacency	邻接
path	路径
in-degree	入度
out-degree	出度
adjacency matrix	邻接矩阵
adjacency list	邻接表
breadth-first search	广度优先搜索
depth-first search	深度优先搜索
binary search	二分查找
searching algorithm	搜索算法
sorting algorithm	排序算法
selection sort	选择排序
bubble sort	冒泡排序
insertion sort	插入排序
quick sort	快速排序
merge sort	归并排序
heap sort	堆排序
bucket sort	桶排序
counting sort	计数排序
radix sort	基数排序
divide and conquer	分治
hanota problem	汉诺塔问题
backtracking algorithm	回溯算法
constraint	约束
solution	解
state	状态
pruning	剪枝
permutations problem	全排列问题
subset-sum problem	子集和问题
$n$-queens problem	$n$ 皇后问题
dynamic programming	动态规划
initial state	初始状态
state-transition equation	状态转移方程
knapsack problem	背包问题
edit distance problem	编辑距离问题
greedy algorithm	贪心算法