数据结构
2016-06-01 13:23:05 0 举报AI智能生成
高级数据结构课程知识点总结
作者其他创作
大纲/内容
随机化数据结构
hash 表
跳表
参数化数据结构
通过实例说明
寻找S中第i小的元素和查询给定元素x的秩
红黑树->OS树：节点存key、size
查询与给定区间有重叠的区间集合
红黑树->区间树
Child Topic
压缩数据结构
无损压缩
哈夫曼编码
按频繁次数建立树，越频繁离跟越近，查找速率越快
FP树
寻找频繁模式
困难：数据量大，多次遍历慢
solution：1频繁->2频繁->。。。
有损压缩
minimum count
elephants and ants
找出频繁率大于k的所有项
难点：数据量大，存在很多不频繁的项不用统计
分布式数据结构
键值对查询方式
算法实例
can
chord
baton
动态数据结构
复杂度分析
分摊分析
聚集分析
动态表
记账分析
势函数
1
例子
动态表
MTFlist
伸展树
数据结构实例
次线性O(logN)
跳表
AVL
B/B+树 logm(N)
红黑树
二项堆
排序
快排
希尔排序
计算逆序
查找
跳表
AVL树
红黑树
B/B+树
MTFlist
伸展树
哈夫曼树
PF树
R树
hash表
研究问题
目标
研究数据的组织和表示，以达到次线性的访问、更新、聚集
困难
size:数据本身可能很大
数据内部的逻辑可能很复杂
结构化数据
半结构化数据
非结构化数据
访问数据的方式pattern
存放数据的介质
内存
磁盘
分布式存储
基本策咯
空间换时间
时间换时间（头一次的麻烦换取以后的轻松访问）
0 条评论
下一页
