【半原创】内核中的数据结构:SplayTree(发在PEDIY论坛,好像得了个优秀)

标 题: 【半原创】内核中的数据结构:SplayTree
作 者: elapseyear
时 间: 2012-02-22,13:01:25
链 接: http://bbs.pediy.com/showthread.php?t=146816

内核中的数据结构:

Splay Tree
Splay Tree(伸展树)是Binary Search Tree(二叉搜索树), Daniel Sleator和Robert E.Tarjan发明。但此操作可能会花费O(n)时间,但m次操作的最坏情况为O(m*log2(n))。
Splay Tree是在节点访问后,此节点将成为该树的根。如此节点位置深,则根到该节点路径上会有很多较深节点。旋转后,这些节点的深度会减少。
查找频率高的item经常在靠近树根的位置。每次查找后,对树进行重构,把item挪倒离树根近地方。Splay tree是自调整形式的二叉查找树,会沿着某个节点到树根间的路径,通过一系列旋转把此节点搬移到树根。

RtlSplay 主要例程,完成节点到Splay树根的操作。
RtlDelete 删除节点,重新平衡。
RtlIsRoot 节点是否是Splay树根。
RtlRealPredecessor 返回节点的pre节点。
RtlInsertAsLeftChild

PRTL_SPLAY_LINKS
RtlSplay( IN PRTL_SPLAY_LINKS Links )
{
PRTL_SPLAY_LINKS L;
PRTL_SPLAY_LINKS P;
PRTL_SPLAY_LINKS G;
// while links is not the root we need to keep rotating it toward
// the root
L = Links;

while (!RtlIsRoot(L)) {

P = RtlParent(L);
G = RtlParent(P);
if (RtlIsLeftChild(L)) {
if (RtlIsRoot(P)) {
/*
we have the following case

P L
/ \ / \
L c ==> a P
/ \ / \
a b b c
*/

// Connect P & b
//

P->LeftChild = L->RightChild;
if (P->LeftChild != NULL) {P->LeftChild->Parent = P;}
// Connect L & P

L->RightChild = P;
P->Parent = L;

// Make L the root

L->Parent = L;

} else if (RtlIsLeftChild(P)) {

/* we have the following case

| |
G L
/ \ / \
P d ==> a P
/ \ / \
L c b G
/ \ / \
a b c d
*/

// Connect P & b

P->LeftChild = L->RightChild;
if (P->LeftChild != NULL) {P->LeftChild->Parent = P;}
// Connect G & c

G->LeftChild = P->RightChild;
if (G->LeftChild != NULL) {G->LeftChild->Parent = G;}

// Connect L & Great GrandParent

if (RtlIsRoot(G)) {
L->Parent = L;
} else {
L->Parent = G->Parent;
*(ParentsChildPointerAddress(G)) = L;
}

// Connect L & P

L->RightChild = P;
P->Parent = L;

//
// Connect P & G
//

P->RightChild = G;
G->Parent = P;

} else { // RtlIsRightChild(Parent)

/*
we have the following case

| |
G L
/ \ / \
a P G P
/ \ / \ / \
L d ==> a b c d
/ \
b c
*/

//
// Connect G & b
//

G->RightChild = L->LeftChild;
if (G->RightChild != NULL) {G->RightChild->Parent = G;}

//
// Connect P & c
//

P->LeftChild = L->RightChild;
if (P->LeftChild != NULL) {P->LeftChild->Parent = P;}

//
// Connect L & Great GrandParent
//

if (RtlIsRoot(G)) {
L->Parent = L;
} else {
L->Parent = G->Parent;
*(ParentsChildPointerAddress(G)) = L;
}

//
// Connect L & G
//

L->LeftChild = G;
G->Parent = L;

//
// Connect L & P
//

L->RightChild = P;
P->Parent = L;

}

} else { // RtlIsRightChild(L)

if (RtlIsRoot(P)) {

/*
we have the following case

P L
/ \ / \
a L P c
/ \ / \
b c ==> a b
*/

//
// Connect P & b
//

P->RightChild = L->LeftChild;
if (P->RightChild != NULL) {P->RightChild->Parent = P;}

//
// Connect P & L
//

L->LeftChild = P;
P->Parent = L;

//
// Make L the root
//

L->Parent = L;

} else if (RtlIsRightChild(P)) {

/*
we have the following case

| |
G L
/ \ / \
a P P d
/ \ / \
b L G c
/ \ / \
c d ==> a b
*/

//
// Connect G & b
//

G->RightChild = P->LeftChild;
if (G->RightChild != NULL) {G->RightChild->Parent = G;}

//
// Connect P & c
//

P->RightChild = L->LeftChild;
if (P->RightChild != NULL) {P->RightChild->Parent = P;}

//
// Connect L & Great GrandParent
//

if (RtlIsRoot(G)) {
L->Parent = L;
} else {
L->Parent = G->Parent;
*(ParentsChildPointerAddress(G)) = L;
}

//
// Connect L & P
//

L->LeftChild = P;
P->Parent = L;

//
// Connect P & G
//

P->LeftChild = G;
G->Parent = P;

} else { // RtlIsLeftChild(P)

/*
we have the following case

| |
G L
/ \ / \
P d P G
/ \ / \ / \
a L ==> a b c d
/ \
b c
*/

//
// Connect P & b
//

P->RightChild = L->LeftChild;
if (P->RightChild != NULL) {P->RightChild->Parent = P;}

//
// Connect G & c
//

G->LeftChild = L->RightChild;
if (G->LeftChild != NULL) {G->LeftChild->Parent = G;}

//
// Connect L & Great GrandParent
//

if (RtlIsRoot(G)) {
L->Parent = L;
} else {
L->Parent = G->Parent;
*(ParentsChildPointerAddress(G)) = L;
}

//
// Connect L & P
//

L->LeftChild = P;
P->Parent = L;

//
// Connect L & G
//

L->RightChild = G;
G->Parent = L;

}
}
}

return L;
}

发表评论