文山州住房和城乡建设局网站公司注册线上服务平台

树与二叉树

1. 满二叉树：每层的节点数都是该层能取到的最大值
2. 完全二叉树：在满二叉树的基础上，去掉最下层右面的一些连续叶子节点所形成的二叉树
3. AVL：平衡二叉树。树中任意节点的左子树和右子树高度之差的绝对值不超过1的二叉排序树称为平衡二叉树。（在查找章节中专门介绍）
4. BST（Binary Search Tree）：二叉排序树。即对于每个结点，它的左子树中所有结点值都比它小，它的右子树中所有结点值都比它大的二叉树。（在查找章节中专门介绍）
5. WPL：树的带权路径长度。记为 $WPL={\sum }_{i=1}^{n_0}{w}_i{l}_i$（其中$n_0$指树中叶子节点的个数，$w_i$指第i个叶子节点的权，$l_i$指第i个叶子节点到根节点的路径长度）

图

1. AOV（Activity On Vertex Network）：用DAG图表示一个工程，其顶点表示活动，用有向边$<V_i,V_j>$表示活动 $V_i$ 必须先于活动 $V_j$ 进行的这样一种关系（多用于求拓扑序列）
2. AOE（Activity On Edge Network）：在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销（如完成活动所需时间），称之为“用边表示活动的网络”，简称AOE网（多用于求关键路径）
3. DAG（有向无环图）
4. BFS（Breadth-First-Search）：广度优先搜索，类似于二叉树的层序遍历算法
5. DFS（Depth-First-Search）：深度优先搜索，类似于树的先序遍历
6. MST（Minimum-Spanning-Tree）：最小生成树。对于一个带权连通无向图G，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则称T为G的最小生成树

查找

1. ASL：平均查找长度。$ASL={\sum }_{i=1}^n{P}_i{C}_i$。$n$为查找表长度，$P_i$是查找第I个元素的概率，一般认为$P_i=\frac{1}{n}$；$C_i$是找到第i个元素所需要进行的比较次数。
2. 平衡因子：节点左子树和右子树的高度差为该节点的平衡因子
3. 装填因子：散列表中的概念，定义为一个表的装满程度，即装填因子$\alpha =\frac{表中记录数n}{散列表长度m}$