数据结构 - 伸展树 Splay Tree
目录
一、什么是伸展树？
80-20黄金法则显示，日常中我们80%的访问发生在20%的数据上。
如果我们能够把经常访问的节点推到靠近根节点的位置，那么就可以极大的提高访问速度。
这就是伸展树的出发点，并实现了以下方案：每次查找节点之后对树进行重构（旋转操作），把被查找的节点搬移到树根。
与二叉平衡树相比，伸展树不会保证树一直是平衡的，甚至可能是一个糟糕的单链表，但是它各种操作的平摊时间复杂度是O(log n)。
二、Splay操作的设计模式
伸展树的设计有两种设计模式，一种“自底向上”，一种“自顶向下”。
由于伸展树的操作需要访问其父结点和祖父结点，那么“自底向上”的设计就需要额外的指针指向结点的父结点，来为我们提供访问的方式，这就需要额外的空间了。
//自底向上
struct SplayNode{
int value;
SplayNode *parent; //额外指针指向父结点
SplayNode *left, *right;
SplayNode(int val):value(val), left(NULL), right(NULL){}
};
因此本文主要讨论“自顶向下”的模式，因此延展树的定义如下。
//自顶向下
struct SplayNode{
int value;
SplayNode *left, *right;
SplayNode(int val):value(val), left(NULL), right(NULL){}
};
class SplayTree{
public:
SplayTree(): root(NULL){}
SplayTree(vector<int> &arr);
void Splay(int val);
//....
private:
//....
SplayNode* root;
};
三、伸展树的旋转操作
假设X是一个非根点的被访问结点：
- 如果X的父结点是root，那我们可以直接旋转X和root。
- 如果X除了有父结点P，还有一个祖父结点G，那么就有两种情景（实际是四种，但是镜像），分别为Zig-Zag和Zig-Zig。
3.1 父结点是root
3.1.1 左旋
访问结点X在父结点的左边，旋转操作：P的左子树挂载X的右子树，然后P成为X的右子树。
SplayNode* SplayTree::LeftRotation(SplayNode* G){
SplayNode* X = G->left;
G->left = X->right;
X->right = G;
return X;
}
3.1.2 右旋
访问结点X在父结点P的右边，旋转操作：P的右子树挂载X的左子树，然后P成为X的左子树。
SplayNode* SplayTree::RightRotation(SplayNode* G){
SplayNode* X = G->right;
G->right = X->left;
X->left = G;
return X;
}
3.2 父结点不是root
如果父结点P不是root，那么X除了有父结点P，还有一个祖父结点G，那么就有两种情景（实际是四种，但是镜像），分别为Zig-Zag和Zig-Zig。
3.2.1 Zig-Zig
下图是Zig-Zig中左-左的情形（右-右类似），可以看出需要做两次旋转。
- 第一次，把P和X看成一个整体，对G和(P, X)做一次左旋操作。
- 第二次，把P和G看出一个整体，对X和(P, G)做一次左旋操作。
3.2.2 Zig-Zag
下图是Zig-Zag中左-右的情形（右-左类似），也需要两次旋转，不过方式不一样。
- 第一次，以P为root结点，对P和X做一次右旋操作。
- 第二次，把P和X看成一个整体，对G和(P, X)做一次左旋操作。
实现
因为，本文主要讨论“自顶向下”的模式。结合前面关于旋转的讨论，Splay操作的实现如下。
void SplayTree::SpecificSplay(int val, SplayNode* &T){
if(!T) return;
if(val == T->value) return;
SplayNode* G = T;
for(;;){
if(val < G->value){
if(!G->left) break;
if(val < G->left->value){ //left zig-zig
G = LeftRotation(G);
}
else if(val > G->left->value){ //left zig-zag
G->left = RightRotation(G->left);
}
G = LeftRotation(G);
}
else if(val > G->value){
if(!G->right) break;
if(val < G->right->value){ //right zig-zag
G = LeftRotation(G);
}
else if(val > G->right->value){ //right zig-zig
G = RightRotation(G);
}
G = RightRotation(G);
}
else break;
}
T = G;
}
四、删除操作
相较于其他操作，伸展树的删除操作比较特殊，它主要包括以下步骤：
- 将待删除元素结点splay到root，然后delete。
- 将左子树leftTree中最大值结点splay到左子树的root
- 将右子树rightTree挂载到leftTree->right上。
实现如下：
SplayNode* SplayTree::getMax(SplayNode* T){
if(!T) return NULL;
if(!T->right) return T;
else return getMax(T->right);
}
void SplayTree::Delete(int val){
if(!root) return;
SpecificSplay(val, root);
SplayNode *leftTree = root->left, *rightTree = root->right;
SplayNode *leftTreeMax = getMax(root->left);//左子树最大值
delete root;
if(!leftTreeMax)
root = rightTree;
else{
SpecificSplay(leftTreeMax->value, leftTree);
leftTree->right = rightTree;
root = leftTree;
}
}
五、完整程序
SplayTree.h
#pragma once
#include <vector>
using namespace std;
/* 伸展树 Splay Tree
* ADT和AVL都不能保证分摊时间(amortized time)始终保持在O(logN)，而伸展树可以。
*/
struct SplayNode{
int value;
SplayNode *left, *right;
SplayNode(int val):value(val), left(NULL), right(NULL){}
};
class SplayTree{
public:
SplayTree(): root(NULL){}
SplayTree(vector<int> &arr);
void Insert(int val);
void Delete(int val);
void PostOrder();
void Splay(int val);
void Clear();
private:
SplayNode* LeftRotation(SplayNode* G); //X从右子树旋到根结点
SplayNode* RightRotation(SplayNode* G); //X从左子树旋转到根结点
SplayNode* RecursiveInsert(int val, SplayNode* T);
SplayNode* RecursiveClear(SplayNode* T);
SplayNode* getMax(SplayNode* T);
void SpecificSplay(int val, SplayNode* &T);
void RecursivePostOrder(SplayNode* T);
SplayNode* root;
};
SplayTree.cpp
#include "SplayTree.h"
#include <algorithm>
#include <iostream>
using namespace std;
SplayTree::SplayTree(vector<int> &arr){
for(auto &i: arr)
Insert(i);
}
void SplayTree::Insert(int val){
root = RecursiveInsert(val, root);
}
SplayNode* SplayTree::RecursiveInsert(int val, SplayNode* T){
if(!T) return new SplayNode(val);
if(val > T->value)
T->right = RecursiveInsert(val, T->right);
else if(val < T->value)
T->left = RecursiveInsert(val, T->left);
else {cout << "This node already exits." << endl;}
return T;
}
SplayNode* SplayTree::getMax(SplayNode* T){
if(!T) return NULL;
if(!T->right) return T;
else return getMax(T->right);
}
void SplayTree::Delete(int val){
if(!root) return;
SpecificSplay(val, root);
SplayNode *leftTree = root->left, *rightTree = root->right;
SplayNode *leftTreeMax = getMax(root->left);//左子树最大值
delete root;
if(!leftTreeMax)
root = rightTree;
else{
SpecificSplay(leftTreeMax->value, leftTree);
leftTree->right = rightTree;
root = leftTree;
}
}
void SplayTree::PostOrder(){
RecursivePostOrder(root);
}
void SplayTree::RecursivePostOrder(SplayNode* T){
if(!T) {return;}
RecursivePostOrder(T->left);
RecursivePostOrder(T->right);
cout << T->value << " ";
}
/*
* X一开始处于左子树
* G X
* / / \
* X ==> left G
* / \ /
* left right right
*/
SplayNode* SplayTree::LeftRotation(SplayNode* G){
SplayNode* X = G->left;
G->left = X->right;
X->right = G;
return X;
}
/*
* X一开始处于右子树:
*
* G X
* / \ / \
* left1 X ==> G right
* / \ / \
* left2 right left1 left2
*/
SplayNode* SplayTree::RightRotation(SplayNode* G){
SplayNode* X = G->right;
G->right = X->left;
X->left = G;
return X;
}
void SplayTree::Splay(int val){
SpecificSplay(val, root);
}
void SplayTree::SpecificSplay(int val, SplayNode* &T){
if(!T) return;
if(val == T->value) return;
SplayNode* G = T;
for(;;){
if(val < G->value){
if(!G->left) break;
if(val < G->left->value){
G = LeftRotation(G);
}
else if(val > G->left->value){
G->left = RightRotation(G->left);
}
G = LeftRotation(G);
}
else if(val > G->value){
if(!G->right) break;
if(val < G->right->value){
G = LeftRotation(G);
}
else if(val > G->right->value){
G = RightRotation(G);
}
G = RightRotation(G);
}
else break;
}
T = G;
}
void SplayTree::Clear(){
root = RecursiveClear(root);
}
SplayNode* SplayTree::RecursiveClear(SplayNode* T){
if(!T) return NULL;
T->left = RecursiveClear(T->left);
T->right = RecursiveClear(T->right);
delete T; T = NULL;
return T;
}
main.cpp
#include "SplayTree.h"
#include <iostream>
using namespace std;
int main(){
vector<int> arr = {10, 6, 8, 4, 5, 3, 11};
SplayTree test(arr);
//Insertion Test
cout << "After Insertion: ";
test.PostOrder(); cout << endl;
cout << endl;
//Splay Test 1: Left Zig-Zag
test.Splay(8);
cout << "First Splaying: ";
test.PostOrder(); cout << endl;
//Splay Test 2: Left Zig
test.Splay(6);
cout << "Second Splaying: ";
test.PostOrder(); cout << endl;
//Splay Test 3: Left Zig-Zig
test.Splay(3);
cout << "Third Splaying: ";
test.PostOrder(); cout << endl;
//Splay Test 4: Right Zig-Zig + Left Zig-Zag
test.Splay(5);
cout << "Fourth Splaying: ";
test.PostOrder(); cout << endl;
//Splay Test 5: Right Zig
test.Splay(6);
cout << "Fifth Splaying: ";
test.PostOrder(); cout << endl;
//Insert 9 for Test 5
cout << endl;
test.Insert(9);
cout << "Insert 9: ";
test.PostOrder(); cout << endl;
cout << endl;
//Splay Test 5: Right Zig-Zig + Right Zig-Zag
test.Splay(9);
cout << "Sixth Splaying: ";
test.PostOrder(); cout << endl;
//Deletion Test
cout << "After Deletion: ";
test.Delete(6);
test.PostOrder(); cout << endl;
//Clearing Test
cout << "After Clearing: ";
test.Clear();
test.PostOrder(); cout << endl;
}
Output
After Insertion: 3 5 4 8 6 11 10
First Splaying: 3 5 4 6 11 10 8
Second Splaying: 3 5 4 11 10 8 6
Third Splaying: 5 11 10 8 6 4 3
Fourth Splaying: 3 4 11 10 8 6 5
Fifth Splaying: 3 4 5 11 10 8 6
Insert 9: 3 4 5 9 11 10 8 6
Sixth Splaying: 3 4 5 6 8 11 10 9
After Deletion: 3 4 11 10 9 8 5
After Clearing:
六、更多思考
虽然伸展树在性能上超过了二叉平衡树，但是由于“二叉”这个局限，其对于大块数据的读写仍显得心有余而力不足。
自然而然，我们就可以想到“多叉”，B树就是一个类似于“多叉”的树结构，它减少了定位记录时所经历的中间过程，从而加快存取速度。