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

Splay Tree
Splay Tree(伸展树)是Binary Search Tree(二叉搜索树)， Daniel Sleator和Robert E.Tarjan发明。但此操作可能会花费O(n)时间，但m次操作的最坏情况为O(m*log2(n))。
Splay Tree是在节点访问后，此节点将成为该树的根。如此节点位置深，则根到该节点路径上会有很多较深节点。旋转后，这些节点的深度会减少。

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

{
// while links is not the root we need to keep rotating it toward
// the root

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;
}

// 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;
}

//
// 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;
}

//
// 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;
}

//
// Connect L & P
//

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

//
// Connect L & G
//

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

}
}
}

return L;
}