伸展树简介
伸展树是二叉查找树，满足左子树的key<=根节点的<=右子树的key的特点。不保证树是平衡的，但各种操作的平摊的复杂度是logn。从效率上上和平衡树的效率差不多。从编码复杂度上伸展树比红黑树和AVL简单了很多。
伸展树的思想：二八原则 ，也就是把那些访问频率高的的字段尽可能移到离根节点近的位置，所以每次访问节点都会通过各种旋转的方法将访问节点旋转到根节点。
伸展树的旋转
要将访问节点旋转到根节点，主要通过zig、zag、zag-zag、zig-zig、zag-zig和zig-zag这几种方式的针对不同情况的旋转到根节点。zig和zag通常称为单层旋转，zag-zag、zig-zig、zag-zig和zig-zag称为双层旋转，双层旋转都是由单层旋转组合成的。
zig和zag
zig和zag明明是右旋和左旋为啥重新起个名字，大家还都这么叫。没找到这么找到这么叫的原因，但搜到一个单词 zigzagging，意思是“之字形运动”，也许与这单词有关系吧。
网上也有直接利用zig和zag将访问节点旋转到根节点，称之为单层旋转，这也符合伸展树的定义。操作流程是这样的：如果访问节点在父节点左支上，则进行zig操作，在父节点右支上，则进行zag操作，但是效率有时候不太好。如下图，这种旋转结果令人不太满意为了避免这种状况，经常只有当父节点是根节点时，我们用这种单层旋转，其他情况我们都用双层旋转
zag-zag和zig-zig
RR型：孩子节点在父节点右支，父节点在祖父节点右支
LL型：孩子节点在父节点左支，父节点在祖父节点左支
伸展树中，再将节点旋转到根节点的时候，遇到RR型时，进行zag-zag操作
zig-zig.png
伸展树中，再将节点旋转到根节点的时候，遇到LL型时，进行zig-zig操作
zag-zig和zig-zag
LR型：孩子节点在父节点右支，父节点在祖父节点左支
RL型：孩子节点在父节点左支，父节点在祖父节点右支
伸展树中，再将节点旋转到根节点的时候，遇到LR型时,进行zag-zig操作
zig-zag.png
伸展树中，再将节点旋转到根节点的时候，遇到RL型时，进行zig-zag操作
代码实现
zag、zig、zag-zag、zig-zag、zag-zig、zig-zig
这些都是上面各种旋转的代码化,需要注意的是，zig-zag zag-zig 旋转不是一个节点。
/**
* 左旋转
*
* @param node
*/
public void zag(SplayNode node) {
if (node == null) {
return;
}
SplayNode pNode = node.getParent();
if (pNode == null) {
return;
}
SplayNode lChild = node.getLeft();
node.setParent(pNode.getParent());
if (pNode.getParent() != null) {
if (pNode.getParent().getLeft() == pNode) {
pNode.getParent().setLeft(node);
} else {
pNode.getParent().setRight(node);
}
}
pNode.setParent(node);
node.setLeft(pNode);
pNode.setRight(lChild);
if (lChild != null)
lChild.setParent(pNode);
}
/**
* 右旋转
*
* @param node
*/
public void zig(SplayNode node) {
if (node == null) {
return;
}
SplayNode pNode = node.getParent();
if (pNode == null) {
return;
}
SplayNode rChild = node.getRight();
node.setParent(pNode.getParent());
if (pNode.getParent() != null) {
if (pNode.getParent().getLeft() == pNode) {
pNode.getParent().setLeft(node);
} else {
pNode.getParent().setRight(node);
}
}
pNode.setParent(node);
node.setRight(pNode);
pNode.setLeft(rChild);
if (rChild != null)
rChild.setParent(pNode);
}
// 分为左旋(zag),右旋(zig),
private void zigZag(SplayNode node) {
zig(node);
zag(node);
}
private void zigZig(SplayNode node) {
zig(node.getParent());
zig(node);;
}
private void zagZag(SplayNode node) {
zag(node.getParent());
zag(node);
}
private void zagZig(SplayNode node) {
zag(node);
zig(node);
}
伸展操作
伸展操作其实就是针对伸展中遇到的LL,LR,RR,RL以及父节点是根节点的各种情况处理，处理方式就是伸展树的各种旋转。
public void splay(SplayNode node){
if(node.getParent() ==null){
return;
}
SplayNode parent = node.getParent();
if(parent.getParent() ==null){//父节点是根节点
if(node == parent.getLeft()){
zig(node);
}else {
zag(node);
}
return;
}
if(parent == parent.getParent().getLeft()){
if(node == parent.getLeft()){//LL型
zigZig(node);
}else {
zigZag(node);//LR型
}
}else {
if(node == parent.getParent()){
zagZag(node);//RR型
}else {
zagZig(node);//RL型
}
}
}
基础操作
插入
伸展树也是二叉树，所以插入操作的和二叉树一样，增加的只是插入完成后，对插入节点一次伸展操作
public void insert(int value){
SplayNode node = new SplayNode();
node.setValue(value);
if (root == null) {//如果树为空
root = node;
return;
}
SplayNode insertNode = insertNode(node, getRoot());
if(insertNode ==null){
return;
}
splay(insertNode);
}
//将节点插入树中
public SplayNode insertNode(SplayNode node,SplayNode root){
if(root.getValue()>node.getValue()){//插入左子树
if(root.getLeft()!=null){
return insertNode(node,root.getLeft());
}else {
root.setLeft(node);
node.setParent(root);
return node;
}
}else if (root.getValue() <node.getValue()){//插入右子树
if(root.getRight() !=null){
return insertNode(node,root.getRight());
}else {
root.setRight(node);
node.setParent(root);
return node;
}
}else{//这个节点废弃掉
return null;
}
}
查找
查找操作和二叉树的查找一样，只是在查找到结果之后将，查找节点通过伸展操作旋转到根节点
public SplayNode search(int key){
SplayNode node = searchNode(getRoot(),key);
if(node ==null){
return;
}
splay(node);
}
public SplayNode searchNode(SplayNode root ,int key){
if(root.getValue()>key){//去左子树查找
if(root.getLeft()!=null){
return searchNode(root.getLeft(),key);
}else {
return null;//未查找到
}
}else if (root.getValue() <key){//去右子树查找
if(root.getRight() !=null){
return searchNode(root,key);
}else {
return null;//未查找到
}
}else{//等于key
return root;
}
}
删除
删除操作就是，查找到删除节点后，然后通过伸展操作旋转到根节点，然后再删除。
删除操作
- 找到该节点后继节点（中序遍历它后面的那个节点）
- 没有后继节点，将根节点左孩子当做根节点
- 有后继节点，将后继节点key赋值给根节点。1、后继节点是叶子节点，直接删除2、后继节点有右孩子，右孩子替换后继节点的位置
public void deleteKey(int key){
SplayNode node = searchNode(getRoot(),key);
if(node ==null){
return;
}
splay(node);
SplayNode succeedNode = getSucceedNode(node);
if(succeedNode == null){
root = node.getLeft();
if(root != null){
root.setParent(null);
}
}else {
if(succeedNode.getRight() == null){//后继节点是叶子节点
root.setValue(succeedNode.getValue());//将后继节点值赋给根节点
SplayNode parent = succeedNode.getParent();
if(parent.getLeft().getValue() == succeedNode.getValue()){
parent.setLeft(null);
}else {
parent.setRight(null);
}
succeedNode.setParent(null);
}else {
root.setValue(succeedNode.getValue());//将后继节点值赋给根节点
SplayNode parent = succeedNode.getParent();
SplayNode right = succeedNode.getRight();
right.setParent(null);
if(parent.getLeft().getValue() == succeedNode.getValue()){
parent.setLeft(right);
right.setParent(parent);
}else {
parent.setRight(right);
right.setParent(parent);
}
}
}
}
/**
* 获取后继节点
* @param node
* @return
*/
public SplayNode getSucceedNode(SplayNode node){
if(node ==null){
return null;
}
SplayNode rightTree = node.getRight();
if(rightTree == null){
return null;
}
SplayNode currentNode = rightTree;
SplayNode succeedNode =currentNode;
while (currentNode != null){
succeedNode =currentNode;
currentNode =currentNode.getLeft();
}
return succeedNode;
}
思考一个问题
现在访问一个节点就会将它旋转到根节点，是不是会存在访问一次之后就不再访问它了？这样的情况是不是就会浪费性能，在实际应用中，是不是增加个热度的字段，根据这个热度值来判断，它值不值得旋转到根节点。热度值的值设置，是不是可以让前N次数据访问 ，这个值不起作用，只用来改变数据热度，N次之后才起作用,这样的设计是否效率更高些?
总结
整篇文章核心就伸展树的伸展操作，伸展树的核心就是数据的二八原则。如果数据二八选择不明显，就看旋转操作能不能将树变得相对平衡了，双层旋转还是可以达到这个效果的。
