伸展樹的引入：
我們知道AVL樹為了保持嚴(yán)格的平衡缩举，所以在數(shù)據(jù)插入上會呈現(xiàn)過多的旋轉(zhuǎn)签财，影響了插入和刪除的性能间唉。從訪問量上，我們知道許多應(yīng)用場景都有一個(gè)“二八原則“施逾，也就是說80%的人只會用到20%的數(shù)據(jù)敷矫，比如說我們的用的輸入法，平常打的字也就那么多汉额，或許還沒有20%呢曹仗。右比如新聞消息，熱門消息的訪問量是遠(yuǎn)遠(yuǎn)大于普通消息的
伸展樹的定義：
一種較為特殊的二叉查找樹蠕搜，特殊之處在于：** 當(dāng)某個(gè)節(jié)點(diǎn)被訪問時(shí)怎茫，伸展樹輝通過旋轉(zhuǎn)使該節(jié)點(diǎn)成為樹根。這樣能夠使得下一次訪問該節(jié)點(diǎn)時(shí)，能夠迅速的訪問到該節(jié)點(diǎn)轨蛤。****
伸展樹的實(shí)現(xiàn)：伸展即將某個(gè)節(jié)點(diǎn)旋轉(zhuǎn)成為根節(jié)點(diǎn)蜜宪，而實(shí)現(xiàn)的方法分為“自底向上”和“自頂向下”的方法。
a. 自底向上：首先找到目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)祥山，如果目標(biāo)節(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子圃验，則進(jìn)行右旋，如果目標(biāo)節(jié)點(diǎn)為父節(jié)點(diǎn)的右孩子缝呕，則進(jìn)行左旋轉(zhuǎn)
Paste_Image.png
如上圖澳窑，紅色節(jié)點(diǎn)表示為我們目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)。
/** 比較--->查找目標(biāo)節(jié)點(diǎn)--->對目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)
* 使用自底向上的方法實(shí)現(xiàn)伸展
* @param tree 節(jié)點(diǎn)
* @param data 目標(biāo)值
* @return 返回目標(biāo)節(jié)點(diǎn)
*/
public SplayTreeNode<T> splay(SplayTreeNode<T> tree, T data){
//若樹為空供常，則返回
if (tree == null){
return null;
}
//進(jìn)行比較
int result = mCompare(data, tree.data);
//小于0照捡，說明目標(biāo)節(jié)點(diǎn)在左子樹
if (result < 0){
//在左子樹中進(jìn)行查找
tree.left = splay(tree.left, data);
//表示找到了目標(biāo)節(jié)點(diǎn)，tree為目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)话侧，進(jìn)行右旋
tree = rotationRight(tree);
}
// 大于0栗精，說明目標(biāo)節(jié)點(diǎn)在右子樹
else if (result > 0){
//在右子樹樹種進(jìn)行查找
tree.right = splay(tree.right, data);
//表示找到了目標(biāo)節(jié)點(diǎn)，tree為目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)瞻鹏，進(jìn)行左旋
tree = rotationLeft(tree);
} else {
//找到目標(biāo)節(jié)點(diǎn)悲立，返回
return tree;
}
return tree;
}
左旋：
left_rotation
A：表示找到目標(biāo)節(jié)點(diǎn)
B：使目標(biāo)節(jié)點(diǎn)的左孩子成為父節(jié)點(diǎn)的右孩子
C：使父節(jié)點(diǎn)成為目標(biāo)節(jié)點(diǎn)的左孩子
/**
* 進(jìn)行左旋轉(zhuǎn)
* @param root 傳入目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)
* @return 返回以目標(biāo)節(jié)點(diǎn)為根節(jié)點(diǎn)的部分樹
*/
private SplayTreeNode<T> rotationLeft(SplayTreeNode<T> root) {
SplayTreeNode<T> newRoot = root.right;//A
root.right = newRoot.left;//B
newRoot.left = root;//C
return newRoot;
}
右旋：
right_rotation
A：找到目標(biāo)節(jié)點(diǎn)
B：使目標(biāo)節(jié)點(diǎn)的右孩子成為父節(jié)點(diǎn)的左孩子
C：使父節(jié)點(diǎn)成為目標(biāo)節(jié)點(diǎn)的右孩子
/**
* 進(jìn)行右旋
* @param tree
* @return
*/
private SplayTreeNode<T> rotationRight(SplayTreeNode<T> tree) {
SplayTreeNode<T> newRoot = tree.left;//A
tree.left = newRoot.right;//B
newRoot.right = tree;//C
return newRoot;
}
實(shí)現(xiàn)具體的伸展：
(1)在查找時(shí)，進(jìn)行伸展：
private SplayTreeNode<T> search(SplayTreeNode<T> tree, T data){
if (tree == null){
return null;
}
int result = mCompare(data, tree.data);
if (result < 0){
return search(tree.left, data);
} else if (result > 0){
return search(tree.right, data);
} else {
//找到目標(biāo)節(jié)點(diǎn)新博，進(jìn)行伸展薪夕，使其成為根節(jié)點(diǎn)
root = splay(root, data);
return tree;
}
}
(2) 在插入的時(shí)候進(jìn)行伸展：
public SplayTreeNode<T> insert(T data){
root = insert(root, data);
//進(jìn)行伸展
root = splay(root, data);
return root;
}
(3) 在刪除的時(shí)候進(jìn)行伸展：
/**
* 刪除時(shí)，進(jìn)行伸展：
* a. 找到刪除的節(jié)點(diǎn)
* b. 對刪除的節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)赫悄，使其成為根節(jié)點(diǎn)
* c. 刪除該節(jié)點(diǎn)后原献，問題是如何將左右子樹進(jìn)行拼接？
* (1) 若左子樹不為空埂淮，則找到左子樹中的最大值姑隅，因?yàn)樽笞訕涞淖畲笾倒?jié)點(diǎn)沒有右子樹
* (1.1) 將選中的最大值節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)，使其成為根節(jié)點(diǎn)
* (1.2) 將原來的右子樹拼接過來
* (2) 若左子樹為空倔撞，則右子樹直接成為完整的樹
* @param data
* @return
*/
public SplayTreeNode<T> remove(T data){
SplayTreeNode<T> newRoot, removeRoot;
if (root == null){
return null;
}
//找到要刪除的節(jié)點(diǎn)
removeRoot = search(root, data);
//若沒找到讲仰，則返回空
if (removeRoot == null){
return null;
}
//對要刪除的節(jié)點(diǎn)旋轉(zhuǎn)成為根節(jié)點(diǎn)
root = splay(root, data);
//左邊不為空
if (root.left != null){
//找到左子樹的最大節(jié)點(diǎn)值作為根節(jié)點(diǎn)，因?yàn)槠錄]有右孩子存在
newRoot = splay(root.left, findMax(root.left).data);
//右子樹直接賦值
newRoot.right = root.right;
}
//否則直接賦值右子樹
else {
newRoot = root.right;
}
//更新樹
root = newRoot;
//返回刪除的節(jié)點(diǎn)
return removeRoot;
}
完整代碼：
public class SplayTree<T extends Comparable<T>> {
class SplayTreeNode<T extends Comparable<T>>{
SplayTreeNode<T> left;
SplayTreeNode<T> right;
T data;
SplayTreeNode(SplayTreeNode<T> left, SplayTreeNode<T> right, T data){
this.left = left;
this.right = right;
this.data = data;
}
SplayTreeNode(){
this(null, null, null);
}
SplayTreeNode(T data){
this(null, null, data);
}
}
private SplayTreeNode<T> root;
private Comparator<T> cmp;
public SplayTree(){
root = null;
}
public SplayTree(Comparator<T> cmp){
this.cmp = cmp;
}
private int mCompare(T a, T b){
if (cmp != null){
return cmp.compare(a,b);
}
return a.compareTo(b);
}
public SplayTreeNode<T> insert(T data){
root = insert(root, data);
//進(jìn)行伸展
root = splay(root, data);
return root;
}
private SplayTreeNode<T> insert(SplayTreeNode<T> tree, T data){
if (tree == null){
return new SplayTreeNode<T>(data);
}
int result = mCompare(data, tree.data);
if (result < 0){
tree.left = insert(tree.left, data);
} else if (result > 0){
tree.right = insert(tree.right, data);
} else {
System.out.println("已經(jīng)存在該值");
return null;
}
return tree;
}
private SplayTreeNode<T> insert(SplayTreeNode<T> rootTree, SplayTreeNode<T> tempNode){
if (rootTree == null){
return tempNode;
} else {
int result = mCompare(tempNode.data, rootTree.data);
if (result < 0){
rootTree.left = insert(rootTree.left, tempNode);
} else if (result > 0){
rootTree.right = insert(rootTree.right, tempNode);
}
}
return rootTree;
}
public SplayTreeNode<T> search(T data){
return search(root, data);
}
private SplayTreeNode<T> search(SplayTreeNode<T> tree, T data){
if (tree == null){
return null;
}
int result = mCompare(data, tree.data);
if (result < 0){
return search(tree.left, data);
} else if (result > 0){
return search(tree.right, data);
} else {
//找到目標(biāo)節(jié)點(diǎn)痪蝇，進(jìn)行伸展鄙陡，使其成為根節(jié)點(diǎn)
root = splay(root, data);
return tree;
}
}
public T getRoot(){
return root != null ? root.data : null;
}
public T findMax(){
return findMax(root).data;
}
private SplayTreeNode<T> findMax(SplayTreeNode<T> tree){
if (tree == null){
return null;
}
while (tree.right != null){
tree = tree.right;
}
return tree;
}
/**
* 刪除時(shí)，進(jìn)行伸展：
* a. 找到刪除的節(jié)點(diǎn)
* b. 對刪除的節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)躏啰，使其成為根節(jié)點(diǎn)
* c. 刪除該節(jié)點(diǎn)后趁矾，問題是如何將左右子樹進(jìn)行拼接？
* (1) 若左子樹不為空给僵，則找到左子樹中的最大值毫捣，因?yàn)樽笞訕涞淖畲笾倒?jié)點(diǎn)沒有右子樹
* (1.1) 將選中的最大值節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)，使其成為根節(jié)點(diǎn)
* (1.2) 將原來的右子樹拼接過來
* (2) 若左子樹為空，則右子樹直接成為完整的樹
* @param data
* @return
*/
public SplayTreeNode<T> remove(T data){
SplayTreeNode<T> newRoot, removeRoot;
if (root == null){
return null;
}
//找到要刪除的節(jié)點(diǎn)
removeRoot = search(root, data);
//若沒找到培漏，則返回空
if (removeRoot == null){
return null;
}
//對要刪除的節(jié)點(diǎn)旋轉(zhuǎn)成為根節(jié)點(diǎn)
root = splay(root, data);
//左邊不為空
if (root.left != null){
//找到左子樹的最大節(jié)點(diǎn)值作為根節(jié)點(diǎn)，因?yàn)槠錄]有右孩子存在
newRoot = splay(root.left, findMax(root.left).data);
//右子樹直接賦值
newRoot.right = root.right;
}
//否則直接賦值右子樹
else {
newRoot = root.right;
}
//更新樹
root = newRoot;
//返回刪除的節(jié)點(diǎn)
return removeRoot;
}
/**
* 使用自底向上的方法實(shí)現(xiàn)伸展
* @param tree 節(jié)點(diǎn)
* @param data 目標(biāo)值
* @return 返回目標(biāo)節(jié)點(diǎn)
*/
public SplayTreeNode<T> splay(SplayTreeNode<T> tree, T data){
//若樹為空胡本，則返回
if (tree == null){
return null;
}
//進(jìn)行比較
int result = mCompare(data, tree.data);
//小于0牌柄，說明目標(biāo)節(jié)點(diǎn)在左子樹
if (result < 0){
//在左子樹中進(jìn)行查找
tree.left = splay(tree.left, data);
//表示找到了目標(biāo)節(jié)點(diǎn)，tree為目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)侧甫，進(jìn)行右旋
tree = rotationRight(tree);
}
// 大于0珊佣，說明目標(biāo)節(jié)點(diǎn)在右子樹
else if (result > 0){
//在右子樹樹種進(jìn)行查找
tree.right = splay(tree.right, data);
//表示找到了目標(biāo)節(jié)點(diǎn)，tree為目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)披粟，進(jìn)行左旋
tree = rotationLeft(tree);
} else {
//找到目標(biāo)節(jié)點(diǎn)咒锻，返回
return tree;
}
return tree;
}
/**
* 進(jìn)行左旋轉(zhuǎn)
* @param root 傳入目標(biāo)節(jié)點(diǎn)的父節(jié)點(diǎn)
* @return 返回以目標(biāo)節(jié)點(diǎn)為根節(jié)點(diǎn)的部分樹
*/
private SplayTreeNode<T> rotationLeft(SplayTreeNode<T> root) {
SplayTreeNode<T> newRoot = root.right;//A
root.right = newRoot.left;//B
newRoot.left = root;//C
return newRoot;
}
/**
* 進(jìn)行右旋
* @param tree
* @return
*/
private SplayTreeNode<T> rotationRight(SplayTreeNode<T> tree) {
SplayTreeNode<T> newRoot = tree.left;//A
tree.left = newRoot.right;//B
newRoot.right = tree;//C
return newRoot;
}
public void inOrder(){
inOrder(root);
}
private void inOrder(SplayTreeNode<T> tree){
if (tree != null){
inOrder(tree.left);
System.out.print(tree.data + " ");
inOrder(tree.right);
}
}
}
測試代碼：
public class SplayTreeTest {
public static void main(String[] args){
int arr[] = {8,4,30,2,6,9,38,1,3,5,7,33,39,31,34};
SplayTree<Integer> splayTree = new SplayTree<Integer>();
//進(jìn)行插入
for (int anArr : arr) {
splayTree.insert(anArr);
}
//打印樹
System.out.println("root:" + splayTree.getRoot());
printArr(splayTree);
//進(jìn)行搜索節(jié)點(diǎn)33
splayTree.search(33);
System.out.println("root:" + splayTree.getRoot());
printArr(splayTree);
//進(jìn)行刪除節(jié)點(diǎn)8
splayTree.remove(8);
System.out.println("root:" + splayTree.getRoot());
printArr(splayTree);
}
private static void printArr(SplayTree<Integer> splayTree){
System.out.println("當(dāng)前樹的中序遍歷如下：");
splayTree.inOrder();
System.out.println();
}
}
實(shí)現(xiàn)結(jié)果：
root:34
當(dāng)前樹的中序遍歷如下：
1 2 3 4 5 6 7 8 9 30 31 33 34 38 39
root:33
當(dāng)前樹的中序遍歷如下：
1 2 3 4 5 6 7 8 9 30 31 33 34 38 39
root:7
當(dāng)前樹的中序遍歷如下：
1 2 3 4 5 6 7 9 30 31 33 34 38 39
