算法导论第十四章 数据结构的扩张

简介: 一、概要   我们在教科书上所学的所有数据结构都是最常规、最精简的数据结构,即便如此,基本上所有能遇上的问题都能用这些数据结构来解决。但是有一些特殊的问题,需要对现有的数据结构进行些许改造才能应付,这种改造是很细微的,且改造所添加的信息必须能被该数据结构上的常规操作所更新和维护。

一、概要

  我们在教科书上所学的所有数据结构都是最常规、最精简的数据结构,即便如此,基本上所有能遇上的问题都能用这些数据结构来解决。但是有一些特殊的问题,需要对现有的数据结构进行些许改造才能应付,这种改造是很细微的,且改造所添加的信息必须能被该数据结构上的常规操作所更新和维护。比如在链表上添加一个数据域来记录结点的位置、在一棵二叉搜索树上添加一个指针域来记录结点的后继指针,等等。

  本章介绍两种通过扩张红黑树构造出的数据结构,一种是动态顺序统计树;另一种是区间树。然后介绍了如何扩张现有数据结构的一个通用方法。本章不想花太多时间和言语来描述,思想很简单,告诉我们怎么样根据实际问题,扩张现有数据结构,而不是自己去实现一种新的数据结构。

二、扩张的两种数据结构

  简单总结下通过红黑树扩张的两种数据结构:动态顺序统计树和区间树。

  动态顺序统计树在原红黑树的基础上增加一个数据域 x.size,其等于 x 左右孩子的节点数。通过这一小小的改造,就可以利用红黑树解第9章介绍的顺序统计,其所有操作的时间复杂度降到O(lgn)。对于改造的动态顺序统计数,有两个比较重要的函数:一就是求第 k 小的数:Select(x, k); 二是求节点 x 的排名:Rank(T, x),这两个操作都能在O(lgn)内完成。需要注意的是,对新添加的属性 x.size,原有数据结构的操作都要对 size属性进行维护,如添加一个元素的时候,相应树枝上的元素的size属性也应该做更新,删除亦是。如下是一棵动态顺序统计树:

  区间树则是对红黑树扩张以便支持由区间构成的动态集合操作,红黑树用到的关键字值是区间树的区间左端点值。以下是一个区间树及其所表示的区间:

  区间树的节点还扩展了一个域max,就是以该节点为根的子树的所有区间元素的右端点的最大值。该域很容易在O(1)的时间内维护,那就是左子结点的max、右子结点的max和自身区间的右端点三者的最大值。

  区间树提供一些与区间有关的操作,比如判断一个区间有没有与区间树中的任何一个区间元素有交集,判断一个点是否落在区间树中的任意一个区间元素中。

关于如何扩张数据结构的方法:

  书上介绍了四个扩张的步骤:

1)选择一种基础数据结构

2)确定基础数据结构中需要维护的附加信息。

3)检验基础数据结构上的基本修改操作能否维护附加信息。

4)设计一些新操作

关于本章中部分课后习题的解答可以参见本文:http://www.cnblogs.com/yiyezhai/archive/2013/01/29/2879729.html

目录
相关文章
|
16天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
58 4
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
90 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
14天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
22天前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
82 23
|
13天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
37 1
|
2月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
38 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
22天前
|
算法 vr&ar 计算机视觉
数据结构之洪水填充算法(DFS)
洪水填充算法是一种基于深度优先搜索(DFS)的图像处理技术,主要用于区域填充和图像分割。通过递归或栈的方式探索图像中的连通区域并进行颜色替换。本文介绍了算法的基本原理、数据结构设计(如链表和栈)、核心代码实现及应用实例,展示了算法在图像编辑等领域的高效性和灵活性。同时,文中也讨论了算法的优缺点,如实现简单但可能存在堆栈溢出的风险等。
35 0
|
2月前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
40 4
|
2月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
24 0
数据结构与算法学习十四:常用排序算法总结和对比
|
2月前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
37 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题