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

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

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

``````/* 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 */
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);
t = grandchild;
} else {
/* zig-zag case */
/* root goes to !dChild, child goes to dChild, grandchild goes to root */
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;
}``````

• a123456678
2019-07-17 19:32:52

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

0 0

1

21

33秒后我完全震惊了！

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

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

33

3

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

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

2

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

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入门教程》