设计网站页面出现问题,安徽省铜陵市建设局网站,牙膏的网站建设,python基础教程入门树与二叉树
满二叉树#xff1a;每层的节点数都是该层能取到的最大值完全二叉树#xff1a;在满二叉树的基础上#xff0c;去掉最下层右面的一些连续叶子节点所形成的二叉树AVL#xff1a;平衡二叉树。树中任意节点的左子树和右子树高度之差的绝对值不超过1的二叉排序树称…树与二叉树
满二叉树每层的节点数都是该层能取到的最大值完全二叉树在满二叉树的基础上去掉最下层右面的一些连续叶子节点所形成的二叉树AVL平衡二叉树。树中任意节点的左子树和右子树高度之差的绝对值不超过1的二叉排序树称为平衡二叉树。在查找章节中专门介绍BSTBinary Search Tree二叉排序树。即对于每个结点它的左子树中所有结点值都比它小它的右子树中所有结点值都比它大的二叉树。在查找章节中专门介绍WPL树的带权路径长度。记为 W P L ∑ i 1 n 0 w i l i WPL\sum^{n_0}_{i1}w_il_i WPL∑i1n0wili其中 n 0 n_0 n0指树中叶子节点的个数 w i w_i wi指第i个叶子节点的权 l i l_i li指第i个叶子节点到根节点的路径长度
图
AOVActivity On Vertex Network用DAG图表示一个工程其顶点表示活动用有向边 V i , V j V_i, V_j Vi,Vj表示活动 V i V_i Vi 必须先于活动 V j V_j Vj 进行的这样一种关系多用于求拓扑序列AOEActivity On Edge Network在带权有向图中以顶点表示事件有向边表示活动边上的权值表示完成该活动的开销如完成活动所需时间称之为“用边表示活动的网络”简称AOE网多用于求关键路径DAG有向无环图BFSBreadth-First-Search广度优先搜索类似于二叉树的层序遍历算法DFSDepth-First-Search深度优先搜索类似于树的先序遍历MSTMinimum-Spanning-Tree最小生成树。对于一个带权连通无向图G生成树不同每棵树的权即树中所有边上的权值之和也可能不同。设R为G的所有生成树的集合若T为R中边的权值之和最小的生成树则称T为G的最小生成树
查找
ASL平均查找长度。 A S L ∑ i 1 n P i C i ASL\sum_{i1}^nP_iC_i ASL∑i1nPiCi。 n n n为查找表长度 P i P_i Pi是查找第I个元素的概率一般认为 P i 1 n P_i\frac{1}{n} Pin1 C i C_i Ci是找到第i个元素所需要进行的比较次数。平衡因子节点左子树和右子树的高度差为该节点的平衡因子装填因子散列表中的概念定义为一个表的装满程度即装填因子 α 表中记录数 n 散列表长度 m \alpha\frac{表中记录数n}{散列表长度m} α散列表长度m表中记录数n
