《数据结构扩张》是《算法导论》第三部分的最后一章。在介绍学习了这么多种数据
结构之后,简要介绍了当这些基本数据结构不满足需求时,如何扩张它们来满足需求。
这才是学习算法的目的,能够根据需求选择合适的数据结构和算法,并在无法满足需求
时能够扩张它。这才是对算法的思想和本质的学习!
可以将本章看做深入学习的前奏吧,因为紧接着就要开始进入第四部分《高级设计和分析
技术》了。那么赶快来看看如何扩张数据结构,然后就进入高级部分的学习吧!
1.如何扩张数据结构?
1)选择基础数据结构
2)确定要在基础数据结构中添加哪些信息
3)验证可用基础数据结构上的基本操作来维护新添加的信息
4)设计新的操作
下面来看一个简单的数据扩张的例子 - 动态顺序统计树。《算法导论》中选用红黑树
作为基础数据结构,这里为了简单,用最简单的二叉查找树来实现。这样我们可以集中
注意力在数据结构扩张的方法上。
2.动态顺序统计树
在第九章《中位数和顺序统计》中,我们曾研究过如何求数组中的元素的顺序统计量。
如查找最大值、最小值、第 i 小的值等等。其中求第 i 小元素时采用了随机快速排序的
RANDOMIZED-PARTITION划分方法,从而达到了Θ(n)的期望运行时间。
本节要研究的是动态顺序统计量,与之前的有些类似,首先我们来看面对这个需求,
如何选择合适的数据结构,并在必要时进行简单的扩张。
1)选择基础数据结构
我们面对的需求是维护动态集合,即数据可能会频繁的插入和删除,固定长度的数组
显然不适合这种情形。所以我们可以选择二叉查找树作为基础数据结构,但基本的
二叉查找树实现顺序统计功能是很低效的,所以还要添加新的域来扩张它。
2)确定要在基础数据结构中添加哪些信息
我们选择在每个结点添加一个新的size域,来保存每棵子树的大小(包含的结点树,包括
此根结点自身)。更自然的想法是新加一个rank域,直接保存每个结点的顺序统计量,
但这样插入和删除时可能会麻烦一些,参见习题14.1-6。
3)验证可用基础数据结构上的基本操作来维护新添加的信息
如前所述,添加size而不是rank域是为了只对原有数据结构略作改动,就足以维护附加信息,
这是比较理想的情况。如果添加rank域,当插入一个最小元素时,所有结点的rank域都要变。
4)设计新的操作
新的操作就是我们需求中所需的,OS-SELECT求顺序统计量为 i 的结点和OS-RANK求一个
结点的顺序统计量。
3.实现源码
下面来看实现代码,这里只列出BST实现的改动部分,着重来看新加的操作和对BST的影响。
typedef struct _BSTNode {
struct _BSTNode *left, *right, *parent;
int key;
char *value;
int size;
} BSTNode;
void bst_insert(BSTNode **root, BSTNode *newNode)
{
// Locate insert location
BSTNode *pNode = NULL;
BSTNode *node = *root;
while (node != NULL) {
pNode = node;
node->size += 1;//维护size域
if (newNode->key < node->key)
node = node->left;
else
node = node->right;
}
// Link newNode to pNode
newNode->parent = pNode;
// Link pNode to newNode
if (pNode == NULL)
*root = newNode;
else if (newNode->key < pNode->key)
pNode->left = newNode;
else
pNode->right = newNode;
}
BSTNode *bst_delete(BSTNode **root, BSTNode *delNode)
{
BSTNode *pNode = delNode;//维护size域
while ((pNode = pNode->parent) != NULL)
pNode->size -= 1;
// Real delete node: delNode or its successor
// (if delNode has both left and right child)
BSTNode *realDelNode;
if (delNode->left && delNode->right)
realDelNode = bst_successor(delNode);
else
realDelNode = delNode;
// Child of real delete node
BSTNode *childNode;
if (delNode->left)
childNode = realDelNode->left;
else
childNode = realDelNode->right;
// Link realDelNode child and parent
if (childNode)
childNode->parent = realDelNode->parent;
if (realDelNode->parent == NULL)
*root = childNode;
else if (realDelNode == realDelNode->parent->left)
realDelNode->parent->left = childNode;
else
realDelNode->parent->right = childNode;
// Copy successor data to delNode (override)
// if real delete node is not delNode but its successor
if (realDelNode != delNode) {
delNode->key = realDelNode->key;
delNode->value = realDelNode->value;
delNode->size = realDelNode->size;//维护size域
}
return realDelNode;
}
BSTNode *bst_os_select(BSTNode *node, int i)
{
if (node == NULL)
return NULL;
int r = 1;
if (node->left != NULL)
r = node->left->size + 1;
if (i == r)
return node;
else if (i < r)
return bst_os_select(node->left, i);
else
return bst_os_select(node->right, i - r);
}
int bst_os_rank(BSTNode *root, BSTNode *node)
{
int r = 1;
if (node->left != NULL)
r += node->left->size;
while (node != root) {
if (node == node->parent->right)
r += node->parent->left->size + 1;
node = node->parent;
}
return r;
}
4.运行情况详细分析
现在以查找第 i = 17小的元素来看OS-SELECT的执行过程。
| |
| |
[ 3, 7, 10, 12, 14,14, 16, 17, 19, 20,21, 21, 26, 28, 30,35, 38, 39,41, 47]
1.从根结点26开始,其顺序统计量 r = 26左子结点size + 1 = 13 < i,则递归OS-SELECT(26右子结点, i - r),
即OS-SELECT(结点41,4)。
[ 3, 7, 10, 12, 14,14, 16, 17, 19, 20,21, 21,26, 28, 30,35, 38, 39,41, 47]
2.根结点变为41,i = 4,r = 5 + 1 = 6 > i,递归OS-SELECT(41的左子结点, i ),即OS-SELECT(结点30, 4)。
[3, 7, 10, 12, 14,14, 16, 17, 19, 20,21, 21, 26,28, 30,35, 38, 39,41, 47]
3.根结点变为30,i = 4,r = 1 + 1 = 2 < i,递归OS-SELECT(结点38, 2)。
[ 3, 7, 10, 12, 14,14, 16, 17, 19, 20,21, 21, 26,28, 30,35, 38, 39,41, 47]
4.根结点变为38,i = 2,r = 1 + 1 = 2 == i,找到了!结点38即为顺序统计量17的元素。
[3, 7, 10, 12, 14,14, 16, 17, 19, 20,21, 21, 26, 28, 30,35,38, 39,41, 47]
看到OS-SELECT的实现了吧,跟第九章的RANDOMIZED-SELECT多么相似。从根结点开始遍历,
首先计算根节点的顺序统计量设为r,若比 i 小则继续处理根节点的左子树,否则处理右子树。
我们可以将每次递归处理的根节点node看做RANDOMIZED-PARTITION返回的划分元素A[q],
若 i 比A[q]的顺序统计量小则继续处理较小的数组部分,否则处理大的那部分。如出一辙!
分享到:
相关推荐
算法导论第二十四章答案 算法导论第二十四章答案 算法导论第二十四章答案
算法导论第四章答案算法导论第四章答案算法导论第四章答案算法导论第四章答案
算法导论第15章-动态规划的课后习题参考答案,对于算法爱好者而言,是不错的参考资料。
动态规划算法 数据结构 算法导论 编程思想 程序员指定用书
能用代码表示的都用代码表示,不能表示的写出思路,思路都没写的就是我也做不出来
算法导论中文版,主要讲述算法中可能用的数据结构,还有一些针对数据结构的算法。
算法导论 第二十五章 答案 算法导论 第二十五章 答案 算法导论 第二十五章 答案
算法导论英文原版,数据结构与算法,算法导论英文原版,数据结构与算法
第14章 数据结构的扩张 第四部分 高级设计和分析技术 导论 第15章 动态规划 第16章 贪心算法 第17章 平摊分析 第五部分 高级数据结构 概述 第18章 B树 第19章 二项堆 第20章 斐波那契堆 第21章 用于不相交集合的数据...
能用代码表示的都用代码表示,不能表示的写出思路,思路都没写的就是我也做不出来。
最近在研习算法导论,发现课后习题的精彩程度甚至不亚于正文,对于算法导论的爱好者而言,这是一份不错的参考资料
算法导论(现代计算机常用数据结构和算法)
请参考算法导论第三版英文版Introduction to Algorithms 3rd Edition,本程序为第10章到第14章常用数据结构的c/c++实现。 IDE环境为vc++ 6.0。 主要包括: 队列 双向链表 哈希表 二叉搜索树
算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业...
第十四章 扩充的数据结构(Augmenting Data Structures) 第四部分(Part IV) 高级的设计与分析技术(Advanced Design and Analysis Techniques) 第十五章 动态规划(Dynamic Programming) 第十六章 ...
31~35章
这个是数据结构的算法导论电子书 。。英文版滴~
算法导论,第九章,chp9中位数和顺序统计量,C#和C++代码实现。