认识达内从这里开始

认真做教育专心促就业

python数据结构解析（2）

发布：达内编程培训
来源：互联网
时间：2018-08-24 10:58

    字典树
    字典树，又称为基数树或前缀树，是一种用于存储键值为字符串的动态集合或关联数组的查找树。树中的节点并不直接存储关联键值，而是该节点在树中的位置决定了其关联键值。一个节点的所有子节点都有相同的前缀，根节点则是空字符串。
    树状数组
    树状数组，又称为二进制索引树（Binary Indexed Tree,BIT），其概念上是树，但以数组实现。数组中的下标代表树中的节点，每个节点的父节点或子节点的下标可以通过位运算获得。数组中的每个元素都包含了预计算的区间值之和，在整个树更新的过程中，这些计算的值也同样会被更新。
    时间复杂度
    区间求和：O（log（n））
    更新：O（log（n））
    线段树
    线段树是用于存储区间和线段的树形数据结构。它允许查找一个节点在若干条线段中出现的次数。
    时间复杂度
    区间查找：O（log（n））
    更新：O（log（n））
    堆
    堆是一种基于树的满足某些特性的数据结构：整个堆中的所有父子节点的键值都满足相同的排序条件。堆分为最大堆和最小堆。在最大堆中，父节点的键值永远大于等于所有子节点的键值，根节点的键值是最大的。最小堆中，父节点的键值永远小于等于所有子节点的键值，根节点的键值是最小的。
    时间复杂度
    索引：O（log（n））
    查找：O（log（n））
    插入：O（log（n））
    删除：O（log（n））

删除最大值/最小值：O（1）

    哈希
    哈希用于将任意长度的数据映射到固定长度的数据。哈希函数的返回值被称为哈希值、哈希码或者哈希。如果不同的主键得到相同的哈希值，则发生了冲突。
    Hash Map:hash map 是一个存储键值间关系的数据结构。HashMap 通过哈希函数将键转化为桶或者槽中的下标，从而便于指定值的查找。
    冲突解决
    链地址法（Separate Chaining）：在链地址法中，每个桶（bucket）是相互独立的，每一个索引对应一个元素列表。处理HashMap 的时间就是查找桶的时间（常量）与遍历列表元素的时间之和。
    开放地址法（Open Addressing）：在开放地址方法中，当插入新值时，会判断该值对应的哈希桶是否存在，如果存在则根据某种算法依次选择下一个可能的位置，直到找到一个未被占用的地址。开放地址即某个元素的位置并不永远由其哈希值决定。
    图
    图是G =（V,E）的有序对，其包括顶点或节点的集合 V 以及边或弧的集合E,其中E包括了两个来自V的元素（即边与两个顶点相关联 ,并且该关联为这两个顶点的无序对）。
    无向图：图的邻接矩阵是对称的，因此如果存在节点 u 到节点 v 的边，那节点 v 到节点 u 的边也一定存在。

有向图：图的邻接矩阵不是对称的。因此如果存在节点 u 到节点 v 的边并不意味着一定存在节点 v 到节点 u 的边。

以上就是潍坊IT培训给大家做的内容详解，更多关于IT知识的学习，请继续关注潍坊IT培训。

< 上一篇：python数据结构解析（1）

下一篇：python数据结构解析（3） >