在上一节中,我们为树结点添加size域表示每颗子树的大小,即包含的结点个数,扩张了
二叉查找树为其增加顺序统计量的查找功能。更为自然的想法是直接添加顺序统计量rank域
到每个树结点上。这一节我们就来看下在这样的设计下,如何扩张来完成上一节相同的功能。
当我们插入一个结点到二叉树中,假设它的顺序统计量为5,那么之前二叉树中顺序统计量
大于5的结点都要更新。也就是说插入一个新结点到对应的位置后,要不断地查找其后继,
完成rank域的更新。所以可以结合习题14.2-1,再添加两个指针域prev和next指向前趋和后继,
使查找前趋和后继在O(1)内完成。
下面来看具体代码。
// 添加三个新域
typedef struct _BSTNode {
struct _BSTNode *left, *right, *parent;
int key;
char *value;
struct _BSTNode *prev, *next;
int rank;
} BSTNode;
// 对于prev和next指针的维护,插入结点分两种情况:
// 1.新插入结点newNode是其父结点P的左子结点,说明P->prev < newNode < P
// 2.新插入结点newNode是其父结点P的右子结点,说明P < newNode < P->next
//
// 对于rank域,如果newNode没有前趋,那么rank置为1,否则置为newNode前趋的rank值加1
// 之后开始迭代更新,将newNode的所有后继的rank值都加1。
void bst_insert(BSTNode **root, BSTNode *newNode)
{
// Locate insert location
BSTNode *pNode = NULL;
BSTNode *node = *root;
while (node != NULL) {
pNode = node;
if (newNode->key < node->key)
node = node->left;
else
node = node->right;
}
// Link newNode to pNode
newNode->parent = pNode;
// Link pNode to newNode
// 新逻辑:维护prev, next
if (pNode == NULL) {
*root = newNode;
} else if (newNode->key < pNode->key) {
pNode->left = newNode;
// newNode is between pNode->prev and pNode
if (pNode->prev != NULL)
pNode->prev->next = newNode;
newNode->prev = pNode->prev;
pNode->prev = newNode;
newNode->next = pNode;
}
else {
pNode->right = newNode;
// newNode is between pNode and pNode->next
if (pNode->next != NULL)
pNode->next->prev = newNode;
newNode->next = pNode->next;
newNode->prev = pNode;
pNode->next = newNode;
}
// 新逻辑:维护rank域
if (newNode->prev == NULL)
newNode->rank = 1;
else
newNode->rank = newNode->prev->rank + 1;
BSTNode *succesor = newNode;
while ((succesor = succesor->next) != NULL) {
succesor->rank += 1;
}
}
// Select和Rank操作变得格外简单
BSTNode *bst_os_select(BSTNode *node, int i)
{
while (node != NULL) {
if (node->rank == i)
return node;
else if (node->rank > i)
node = node->left;
else
node = node->right;
}
return NULL;
}
int bst_os_rank(BSTNode *node)
{
return node->rank;
}
通过这一节和上一节的对比,可以看出在步骤(2)中对基础数据结构添加不同的域,会对
步骤(3)和(4)改写和添加新的操作产生很大影响。因此,在扩张数据结构时可以采用
试错法,尝试添加不同的域,权衡各种方案的优劣。
分享到:
相关推荐
算法导论第二十四章答案 算法导论第二十四章答案 算法导论第二十四章答案
算法导论第四章答案算法导论第四章答案算法导论第四章答案算法导论第四章答案
能用代码表示的都用代码表示,不能表示的写出思路,思路都没写的就是我也做不出来
算法导论 第二十五章 答案 算法导论 第二十五章 答案 算法导论 第二十五章 答案
算法导论中文版,主要讲述算法中可能用的数据结构,还有一些针对数据结构的算法。
算法导论英文原版,数据结构与算法,算法导论英文原版,数据结构与算法
算法导论第15章-动态规划的课后习题参考答案,对于算法爱好者而言,是不错的参考资料。
能用代码表示的都用代码表示,不能表示的写出思路,思路都没写的就是我也做不出来。
最近在研习算法导论,发现课后习题的精彩程度甚至不亚于正文,对于算法导论的爱好者而言,这是一份不错的参考资料
算法导论(现代计算机常用数据结构和算法)
请参考算法导论第三版英文版Introduction to Algorithms 3rd Edition,本程序为第10章到第14章常用数据结构的c/c++实现。 IDE环境为vc++ 6.0。 主要包括: 队列 双向链表 哈希表 二叉搜索树
算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业...
第14章 数据结构的扩张 第四部分 高级设计和分析技术 导论 第15章 动态规划 第16章 贪心算法 第17章 平摊分析 第五部分 高级数据结构 概述 第18章 B树 第19章 二项堆 第20章 斐波那契堆 第21章 用于不相交集合的数据...
31~35章
这个是数据结构的算法导论电子书 。。英文版滴~
动态规划算法 数据结构 算法导论 编程思想 程序员指定用书
所有代码都是在我学习这本书时亲手敲出来的,并且调试正确了,包括:第三部分到第六部分(即10-26章),外加第七部分31和32章所有的算法和数据结构以及编程习题还有思考题的C++实现源代码; 第一、二部分学习的较早...
第十四章 扩充的数据结构(Augmenting Data Structures) 第四部分(Part IV) 高级的设计与分析技术(Advanced Design and Analysis Techniques) 第十五章 动态规划(Dynamic Programming) 第十六章 ...
能用代码表示的都用代码表示,不能表示的写出思路,思路都没写的就是我也做不出来