星海's Blog

老头初学编程
算法导论思考题 13-4 Treap

算法导论 动态顺序统计树练习题 14.1-3 14.1-4 14.1-5

星海 posted @ 2012年11月20日 00:04 in 数据结构与算法分析 , 2437 阅读
 *
 *    Description:  算法导论 第14章 动态顺序统计树练习题解答(伪代码)
 *
 *        Version:  1.0
 *        Created:  2012年11月19日 22时59分16秒
 *         Author:  sd44
 *   Organization:  
 *
 * =====================================================================================
 */

// 14.1-3 OS-SELECT的非递归

OS-SELECT(ptr x, int i) {
  if (i > x->size)
    return NULL;
  int r;
  ptr tmp = x;
  while (1) {
    r = tmp->left->size + 1;
    if (i < r) {
      tmp = tmp->left;
    } else if (i > r) {
      i = i - r;
      tmp = tmp->right;
    }
    else
      return r;
  }
}

// 14.1-4 OS-KEY-RANK(T, k) 较为简单,稍微修改树的find(元素)操作即可,
// 题目要求为递归形式,我实现的是非递归形式。
// 解答:
//
 r为动态集合中k的秩。。

 r初始化为0.
 如果k比当前节点的元素值大,则向右子节点移动,并记录当前节点左子结点的size且
 +1。r += currentNode->left->size + 1;
 如果k比当前节点的元素值小,则向左子结点移动,不对r进行加减操作。
 如果k等于当前节点的元素时,r += currentNode->left->size + 1;


//14.1-5 如何在O(lg N)的时间内,确定x在树的线性序中第i个后继。
//解答:
//
首先,find找到x在顺序统计树中的节点node。
如果node右节点的size大于i,则进入右结点,node = node->right,递归找第i个后继

如果node右结点的size小于i,则i = i - node->right->size,此时分两种情况:
1, 如果node为其父的右结点,则上移,node = node->parent

2, 如果node为其父的左节点,则上移,node = node->parent,i = i - 1。如果i == 1,返回此时的node(为原来node的parent)。
 否则递归找第i个后继

Avatar_small
John 111 说:
2021年4月08日 19:55

Positive site, where did u come up with the information on this posting?I have read a few of the articles on your website now, and I really like your style. Thanks a million and please keep up the effective work. https://testogen-review.web.app

Avatar_small
John 111 说:
2021年4月14日 23:07 Cheap Flights Find Cheap Flight For Your Searching for cheap airfare and Last Minte Travel deals your cheap flight deals are almost ready Pay the remaining amount up to 72 hours before your flight's departure. Save money & time on your next flight booking with cheap flights.com Average trip savings calculated based on the price. For domestic flights, mondays showed the highest average airline ticket prices and for international flights, avoid booking on fridays. cheap air flights
Avatar_small
John 111 说:
2021年4月23日 23:31 Took me time to read all the comments, but I really enjoyed the article. It proved to be Very helpful to me and I am sure to all the commenters here! It’s always nice when you can not only be informed, but also entertained! Cuet kuet ruet Admission Website
Avatar_small
John 111 说:
2021年4月23日 23:38

Your website is really cool and this is a great inspiring article. hacker experience

Avatar_small
John 111 说:
2021年5月06日 04:43

New web site is looking good. Thanks for the great effort. magic mushroom capsules

Avatar_small
SS 说:
2021年5月14日 13:48

I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. Thanks... blue american staffordshire terrier puppies for sale near me

Avatar_small
SMITHSEO 说:
2021年5月16日 18:17

Believe it or not, it is the type of information I’ve long been trying to find. It matches to my requirements a lot. Thank you for writing this information. Dank vapes

Avatar_small
SMITHSEO 说:
2021年5月19日 18:28

An fascinating discussion is value comment. I think that it is best to write extra on this matter, it won’t be a taboo topic however generally people are not enough to talk on such topics. To the next. Cheers sphynx cat

Avatar_small
seo service UK 说:
2024年2月24日 14:10

 like review sites which grasp the cost of conveying the fantastic helpful asset for nothing out of pocket. I genuinely revered perusing your posting. Much obliged to you


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter