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

一、概要

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

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

二、扩张的两种数据结构

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

  动态顺序统计树在原红黑树的基础上增加一个数据域 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)设计一些新操作

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏猿人谷

【不做标题党,只做纯干货】HashMap在jdk1.7和1.8中的实现

Java集合类的源码是深入学习Java非常好的素材,源码里很多优雅的写法和思路,会让人叹为观止。HashMap的源码尤为经典,是非常值得去深入研究的,jdk1....

12330
来自专栏一枝花算不算浪漫

Java中常见数据结构Map之HashMap

39370
来自专栏owent

线段树相关问题 (引用 PKU POJ题目) 整理

如果(a < b – 1){分别计算a、b的次数和线段树[a + 1, b – 1)的次数,取大(小)的一项};

20720
来自专栏数据结构与算法

小米OJ刷题日志

$f[i][j]$表示第一个队列匹配到了$i$位置,第二个队列匹配到了$j$位置是否可行

56020
来自专栏Android知识点总结

Java总结之映射家族--Map概览

12440
来自专栏xcywt

《大话数据结构》一些基础知识

第一章 数据结构绪论 1.4 基本概念和术语 1.4.1 数据 数据:描述客观事物的符号,是计算机中可以操作的对象,是能被极端及识别,并输入给计算机处理的符号集...

35990
来自专栏Leetcode名企之路

【Leetcode】60. 第k个排列

给定 n 的范围是 [1, 9]。 给定 k 的范围是[1, n!]。 示例 1:

34920
来自专栏chenjx85的技术专栏

leetcode-55-跳跃游戏

1、给定一个vector,里面存放着非负的int型整数,每一个整数代表在这个位置上可以跳跃的步数,要求判断最终能不能跳跃到vector的最后一位。

5410
来自专栏程序员叨叨叨

5.3 结构类型

Cg 语言支持结构体(structure),实际上 Cg 中的结构体的声明、使用和 C++ 非常类似(只是类似,不是相同)。一个结构体相当于一种数据类型,可以定...

6520
来自专栏灯塔大数据

技术 | Python从零开始系列连载(二十四)

为了解答大家学习Python时遇到各种常见问题,小灯塔特地整理了一系列从零开始的入门到熟练的系列连载,每周五准时推出,欢迎大家学积极学习转载~

11320

扫码关注云+社区

领取腾讯云代金券