【算法导论】第十一课 扩充的数据结构、动态有序统计和区间树
浏览数：37 /
时间：2015年06月08日
本节课主要讲了如何构造自己想要的数据结构，或者扩充已有数据结构的功能，以实现想要的特定功能
比如设计一个动态结构，满足功能寻找第k大的数
其做法是维护每个结点的子结点个数来推导其秩，而不维护其秩，因为动态操作会使得其难以维护红黑树的插入操作 1.树插入 2.rebalance
构造自己需要的扩充数据结构的基本流程
1.选择一个基本的数据结构 例如红黑树2.决定要添加到结点的基本信息 例如实现查询第k大数功能，应添加的基本信息为所有子树结点之和，而非直接保存该结点键值的秩
3 维持 插入+旋转/删除+旋转
4 封装为函数，实现其功能
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
