怎么理解下面这段代码,是关于Splaytrees的-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

怎么理解下面这段代码,是关于Splaytrees的

2016-06-08 23:01:34 1688 1

不太理解这段代码中treeLink()函数的操作,请大神们指点,那个*hook到底起了什么作用?

/* link operations for top-down splay */
/* this pastes a node in as !d-most node in subtree on side d */
static inline void
treeLink(struct tree ***hook, int d, struct tree *node)
{
    *hook[d] = node;
    /* strictly speaking we don't need to do this, but it allows printing the partial trees */
    node->child[!d] = 0;
    hook[d] = &node->child[!d];
}

/* splay last element on path to target to root */
static void
treeSplay(struct tree **root, int target)
{
    struct tree *t;
    struct tree *child;
    struct tree *grandchild;
    struct tree *top[TREE_NUM_CHILDREN];   /* accumulator trees that will become subtrees of new root */
    struct tree **hook[TREE_NUM_CHILDREN]; /* where to link new elements into accumulator trees */
    int d;
    int dChild;        /* direction of child */                   
    int dGrandchild;   /* direction of grandchild */

    /* we don't need to keep following this pointer, we'll just fix it at the end */
    t = *root;

    /* don't do anything to an empty tree */
    if(t == 0) { return; }

    /* ok, tree is not empty, start chopping it up */
    for(d = 0; d < TREE_NUM_CHILDREN; d++) {
        top[d] = 0;
        hook[d] = &top[d];
    }

    /* keep going until we hit the key or we would hit a null pointer in the child */
    while(t->key != target && (child = t->child[dChild = t->key < target]) != 0) {
        /* child is not null */
        grandchild = child->child[dGrandchild = child->key < target];

        treePrint(top[0]);
        puts("---");
        treePrint(t);
        puts("---");
        treePrint(top[1]);
        puts("===");

        if(grandchild == 0 || child->key == target) {
            /* zig case; paste root into opposite-side hook */
            treeLink(hook, !dChild, t);
            t = child;
            /* we can break because we know we will hit child == 0 next */
            break;
        } else if(dChild == dGrandchild) {
            /* zig-zig case */
            /* rotate and then hook up child */
            /* grandChild becomes new root */
            treeRotate(&t, dChild);
            treeLink(hook, !dChild, child);
            t = grandchild;
        } else {
            /* zig-zag case */
            /* root goes to !dChild, child goes to dChild, grandchild goes to root */
            treeLink(hook, !dChild, t);
            treeLink(hook, dChild, child);
            t = grandchild;
        }
    }

    /* now reassemble the tree */
    /* t's children go in hooks, top nodes become t's new children */
    for(d = 0; d < TREE_NUM_CHILDREN; d++) {
        *hook[d] = t->child[d];
        t->child[d] = top[d];
    }

    /* and put t back in *root */
    *root = t;
}
Go
取消 提交回答
全部回答(1)
  • a123456678
    2019-07-17 19:32:52

    你node的定义中左右孩子应该是放在了某个数组中,hood其实还是指向了某个节点。
    好好看下zig, zig-zig, zig-zag这三种的本质。

    0 0
相关问答

1

回答

高效运维最佳实践(03):Redis集群技术及Codis实践

柚子 2015-04-13 15:36:42 33405浏览量 回答数 1

21

回答

33秒后我完全震惊了!

sophi5a 2011-08-04 14:43:24 17343浏览量 回答数 21

15

回答

免费Docker镜像来袭,你造么?

豆妹 2014-11-21 15:49:57 23287浏览量 回答数 15

19

回答

600万女生的共同选择——阿里云助暖暖环球之旅畅通无阻

nono20011908 2014-08-07 18:38:47 27652浏览量 回答数 19

4

回答

kernel:unregister_netdevice: waiting for lo to become free. Usage count = 1

鲁二哥 2016-03-23 23:33:32 35675浏览量 回答数 4

33

回答

活动结束【有奖话题讨论】说说你写代码时踩过的那些坑

西秦说云 2016-06-30 10:05:59 17670浏览量 回答数 33

3

回答

2020年05月编程排行榜-C语言继2015年,重新成为编程排行榜第一名

huc_逆天 2020-05-06 13:43:42 35585浏览量 回答数 3

2

回答

【开源分享】5期 基于 Go 的分布式管理平台 Crawlab

问问小秘 2020-05-07 13:49:42 29676浏览量 回答数 2

4

回答

OSS一键开通CDN和实现域名设置上线完整体验

jack.cai 2015-08-12 10:47:57 17453浏览量 回答数 4

16

回答

Linux系统常用命令大全

2013-05-16 11:07:26 44209浏览量 回答数 16
+关注
0
文章
14879
问答
问答排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载