Java數據結構與算法解析——伸展樹

GreOConnor 7年前發布 | 36K 次閱讀伸展樹算法 Java Java開發

伸展樹簡介

伸展樹(Splay Tree)是特殊的二叉查找樹。

它的特殊是指，它除了本身是棵二叉查找樹之外，它還具備一個特點: 當某個節點被訪問時，伸展樹會通過旋轉使該節點成為樹根。這樣做的好處是，下次要訪問該節點時，能夠迅速的訪問到該節點。

特性

1.和普通的二叉查找樹相比，具有任何情況下、任何操作的平攤O(log2n)的復雜度，時間性能上更好

2.和一般的平衡二叉樹比如紅黑樹、AVL樹相比，維護更少的節點額外信息，空間性能更優，同時編程復雜度更低

3.在很多情況下，對于查找操作，后面的查詢和之前的查詢有很大的相關性。這樣每次查詢操作將被查到的節點旋轉到樹的根節點位置，這樣下次查詢操作可以很快的完成

4.可以完成對區間的查詢、修改、刪除等操作，可以實現線段樹和樹狀數組的所有功能

旋轉

伸展樹實現O(log2n)量級的平攤復雜度依靠每次對伸展樹進行查詢、修改、刪除操作之后，都進行旋轉操作 Splay(x, root)，該操作將節點x旋轉到樹的根部。

伸展樹的旋轉有六種類型，如果去掉鏡像的重復，則為三種：zig(zag)、zig-zig(zag-zag)、zig-zag(zag-zig)。

1 自底向上的方式進行旋轉

1.1 zig旋轉

如圖所示，x節點的父節點為y，x為y的左子節點，且y節點為根。則只需要對x節點進行一次右旋(zig操作)，使之成為y的父節點，就可以使x成為伸展樹的根節點。

1.2 zig-zig旋轉

如上圖所示，x節點的父節點y，y的父節點z，三者在一字型鏈上。此時，先對y節點和z節點進行zig旋轉，然后再對x節點和y節點進行zig旋轉，最后變為右圖所示，x成為y和z的祖先節點。

1.3 zig-zag旋轉

如上圖所示，x節點的父節點y，y的父節點z，三者在之字型鏈上。此時，先對x節點和y節點進行zig旋轉，然后再對x節點和y節點進行zag旋轉，最后變為右圖所示，x成為y和z的祖先節點。

2 自頂向下的方式進行旋轉這種方式不需要節點存儲其父節點的引用。當我們沿著樹向下搜索某個節點x時，將搜索路徑上的節點及其子樹移走。構建兩棵臨時的樹——左樹和右樹。沒有被移走的節點構成的樹稱為中樹。

(1) 當前節點x是中樹的根

(2) 左樹L保存小于x的節點

(3) 右樹R保存大于x的節點

開始時候，x是樹T的根，左樹L和右樹R都為空。三種旋轉操作：

2.1 zig旋轉

如圖所示，x節點的子節點y就是我們要找的節點，則只需要對y節點進行一次右旋(zig操作)，使之成為x的父節點，就可以使y成為伸展樹的根節點。將y作為中樹的根，同時，x節點移動到右樹R中，顯然右樹上的節點都大于所要查找的節點。

2.2 zig-zig旋轉如上圖所示，x節點的左子節點y，y的左子節點z，三者在一字型鏈上，且要查找的節點位于z節點為根的子樹中。此時，對x節點和y節點進行zig，然后對z和y進行zig，使z成為中樹的根，同時將y及其子樹掛載到右樹R上。

2.3 zig-zag旋轉

如上圖所示，x節點的左子節點y，y的右子節點z，三者在之字型鏈上，且需要查找的元素位于以z為根的子樹上。此時，先對x節點和y節點進行zig旋轉，將x及其右子樹掛載到右樹R上，此時y成為中樹的根節點；然后再對z節點和y節點進行zag旋轉，使得z成為中樹的根節點。

2.4 合并

最后，找到節點或者遇到空節點之后，需要對左、中、右樹進行合并。如圖所示，將左樹掛載到中樹的最左下方（滿足遍歷順序要求），將右樹掛載到中樹的最右下方（滿足遍歷順序要求）。

伸展樹的實現

1.節點

public class SplayTree<T extends Comparable<T>> {
    private SplayTreeNode<T> mRoot;    // 根結點

public class SplayTreeNode<T extends Comparable<T>> {
    T key;                // 關鍵字(鍵值)
    SplayTreeNode<T> left;    // 左孩子
    SplayTreeNode<T> right;    // 右孩子

    public SplayTreeNode() {
        this.left = null;
        this.right = null;
    }

    public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) {
        this.key = key;
        this.left = left;
        this.right = right;
    }
}

}</code></pre> 
  
SplayTree是伸展樹，而SplayTreeNode是伸展樹節點。在此，我將SplayTreeNode定義為SplayTree的內部類。在伸展樹SplayTree中包含了伸展樹的根節點mRoot。SplayTreeNode包括的幾個組成元素: 
  (1) key – 是關鍵字，是用來對伸展樹的節點進行排序的。 
  (2) left – 是左孩子。 
  (3) right – 是右孩子。 
  2.旋轉 
  /*

旋轉key對應的節點為根節點，并返回根節點。
*
注意：
(a)：伸展樹中存在"鍵值為key的節點"。
將"鍵值為key的節點"旋轉為根節點。
(b)：伸展樹中不存在"鍵值為key的節點"，并且key < tree.key。
b-1 "鍵值為key的節點"的前驅節點存在的話，將"鍵值為key的節點"的前驅節點旋轉為根節點。
b-2 "鍵值為key的節點"的前驅節點存在的話，則意味著，key比樹中任何鍵值都小，那么此時，將最小節點旋轉為根節點。
(c)：伸展樹中不存在"鍵值為key的節點"，并且key > tree.key。
c-1 "鍵值為key的節點"的后繼節點存在的話，將"鍵值為key的節點"的后繼節點旋轉為根節點。
c-2 "鍵值為key的節點"的后繼節點不存在的話，則意味著，key比樹中任何鍵值都大，那么此時，將最大節點旋轉為根節點。
*/
private SplayTreeNode<T> splay(SplayTreeNode<T> tree, T key) {
if (tree == null)

return tree;


SplayTreeNode<T> N = new SplayTreeNode<T>();
SplayTreeNode<T> l = N;
SplayTreeNode<T> r = N;
SplayTreeNode<T> c;
for (; ; ) {

int cmp = key.compareTo(tree.key);
if (cmp < 0) {
    if (key.compareTo(tree.left.key) < 0) {
        c = tree.left;                           /* rotate right */
        tree.left = c.right;
        c.right = tree;
        tree = c;
        if (tree.left == null)
            break;
    }
    r.left = tree;                               /* link right */
    r = tree;
    tree = tree.left;
} else if (cmp > 0) {

    if (tree.right == null)
        break;

    if (key.compareTo(tree.right.key) > 0) {
        c = tree.right;                          /* rotate left */
        tree.right = c.left;
        c.left = tree;
        tree = c;
        if (tree.right == null)
            break;
    }

    l.right = tree;                              /* link left */
    l = tree;
    tree = tree.right;
} else {
    break;
}

}
l.right = tree.left;                                / assemble /
r.left = tree.right;
tree.left = N.right;
tree.right = N.left;
return tree;
}
public void splay(T key) {
mRoot = splay(mRoot, key);
}
}</code></pre> 
上面的代碼的作用：將”鍵值為key的節點”旋轉為根節點，并返回根節點。它的處理情況共包括： 
(a)：伸展樹中存在”鍵值為key的節點”。 
將”鍵值為key的節點”旋轉為根節點。 
(b)：伸展樹中不存在”鍵值為key的節點”，并且key < tree->key。 
b-1) “鍵值為key的節點”的前驅節點存在的話，將”鍵值為key的節點”的前驅節點旋轉為根節點。 
b-2) “鍵值為key的節點”的前驅節點存在的話，則意味著，key比樹中任何鍵值都小，那么此時，將最小節點旋轉為根節點。 
(c)：伸展樹中不存在”鍵值為key的節點”，并且key > tree->key。 
c-1) “鍵值為key的節點”的后繼節點存在的話，將”鍵值為key的節點”的后繼節點旋轉為根節點。 
c-2) “鍵值為key的節點”的后繼節點不存在的話，則意味著，key比樹中任何鍵值都大，那么此時，將最大節點旋轉為根節點。 
下面列舉個例子分別對a進行說明。 
在下面的伸展樹中查找10，，共包括”右旋” –> “右鏈接” –> “組合”這3步。 
 
01, 右旋 
對應代碼中的”rotate right”部分 
 
02, 右鏈接 
對應代碼中的”link right”部分 
 
03.組合 
對應代碼中的”assemble”部分 
 
提示：如果在上面的伸展樹中查找”70”，則正好與”示例1”對稱，而對應的操作則分別是”rotate left”, “link left”和”assemble”。 
其它的情況，例如”查找15是b-1的情況，查找5是b-2的情況”等等，這些都比較簡單，大家可以自己分析。 
3.插入 
/**

將結點插入到伸展樹中，并返回根節點
@param tree 伸展樹的根節點
@param z 插入的結點
@return
*/
private SplayTreeNode<T> insert(SplayTreeNode<T> tree, SplayTreeNode<T> z) {
int cmp;
SplayTreeNode<T> y = null;
SplayTreeNode<T> x = tree;

// 查找z的插入位置
while (x != null) {

y = x;
cmp = z.key.compareTo(x.key);
if (cmp < 0)
    x = x.left;
else if (cmp > 0)
    x = x.right;
else {
    System.out.printf("不允許插入相同節點(%d)!\n", z.key);
    z = null;
    return tree;
}

}
if (y == null)

tree = z;

else {

cmp = z.key.compareTo(y.key);
if (cmp < 0)
    y.left = z;
else
    y.right = z;

}
return tree;
}
public void insert(T key) {
SplayTreeNode<T> z = new SplayTreeNode<T>(key, null, null);
// 如果新建結點失敗，則返回。
if ((z = new SplayTreeNode<T>(key, null, null)) == null)

return;


// 插入節點
mRoot = insert(mRoot, z);
// 將節點(key)旋轉為根節點
mRoot = splay(mRoot, key);
}</code></pre> 
insert(key)是提供給外部的接口，它的作用是新建節點(節點的鍵值為key)，并將節點插入到伸展樹中；然后，將該節點旋轉為根節點。 
insert(tree, z)是內部接口，它的作用是將節點z插入到tree中。insert(tree, z)在將z插入到tree中時，僅僅只將tree當作是一棵二叉查找樹，而且不允許插入相同節點。 
4.刪除 
/**


@param tree 伸展樹
@param key 刪除的結點
@return
*/
private SplayTreeNode<T> remove(SplayTreeNode<T> tree, T key) {
SplayTreeNode<T> x;

if (tree == null)

return null;


// 查找鍵值為key的節點，找不到的話直接返回。
if (search(tree, key) == null)

return tree;


// 將key對應的節點旋轉為根節點。
tree = splay(tree, key);
if (tree.left != null) {

// 將"tree的前驅節點"旋轉為根節點
x = splay(tree.left, key);
// 移除tree節點
x.right = tree.right;

}
else

x = tree.right;


tree = null;
return x;
}
public void remove(T key) {
mRoot = remove(mRoot, key);
}</code></pre> 
remove(key)是外部接口，remove(tree, key)是內部接口。 
remove(tree, key)的作用是：刪除伸展樹中鍵值為key的節點。 
它會先在伸展樹中查找鍵值為key的節點。若沒有找到的話，則直接返回。若找到的話，則將該節點旋轉為根節點，然后再刪除該節點。 
伸展樹實現完整代碼 
public class SplayTree<T extends Comparable<T>> {
private SplayTreeNode<T> mRoot;    // 根結點
public class SplayTreeNode<T extends Comparable<T>> {
T key;                // 關鍵字(鍵值)
SplayTreeNode<T> left;    // 左孩子
SplayTreeNode<T> right;    // 右孩子
public SplayTreeNode() {

this.left = null;
this.right = null;

}
public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) {

this.key = key;
this.left = left;
this.right = right;

}
}
/*

旋轉key對應的節點為根節點，并返回根節點。
*
注意：
(a)：伸展樹中存在"鍵值為key的節點"。
將"鍵值為key的節點"旋轉為根節點。
(b)：伸展樹中不存在"鍵值為key的節點"，并且key < tree.key。
b-1 "鍵值為key的節點"的前驅節點存在的話，將"鍵值為key的節點"的前驅節點旋轉為根節點。
b-2 "鍵值為key的節點"的前驅節點存在的話，則意味著，key比樹中任何鍵值都小，那么此時，將最小節點旋轉為根節點。
(c)：伸展樹中不存在"鍵值為key的節點"，并且key > tree.key。
c-1 "鍵值為key的節點"的后繼節點存在的話，將"鍵值為key的節點"的后繼節點旋轉為根節點。
c-2 "鍵值為key的節點"的后繼節點不存在的話，則意味著，key比樹中任何鍵值都大，那么此時，將最大節點旋轉為根節點。
*/
private SplayTreeNode<T> splay(SplayTreeNode<T> tree, T key) {
if (tree == null)

return tree;


SplayTreeNode<T> N = new SplayTreeNode<T>();
SplayTreeNode<T> l = N;
SplayTreeNode<T> r = N;
SplayTreeNode<T> c;
for (; ; ) {

int cmp = key.compareTo(tree.key);
if (cmp < 0) {
    if (key.compareTo(tree.left.key) < 0) {
        c = tree.left;                           /* rotate right */
        tree.left = c.right;
        c.right = tree;
        tree = c;
        if (tree.left == null)
            break;
    }
    r.left = tree;                               /* link right */
    r = tree;
    tree = tree.left;
} else if (cmp > 0) {

    if (tree.right == null)
        break;

    if (key.compareTo(tree.right.key) > 0) {
        c = tree.right;                          /* rotate left */
        tree.right = c.left;
        c.left = tree;
        tree = c;
        if (tree.right == null)
            break;
    }

    l.right = tree;                              /* link left */
    l = tree;
    tree = tree.right;
} else {
    break;
}

}
l.right = tree.left;                                / assemble /
r.left = tree.right;
tree.left = N.right;
tree.right = N.left;
return tree;
}
public void splay(T key) {
mRoot = splay(mRoot, key);
}



/**
 * 將結點插入到伸展樹中，并返回根節點
 * @param tree 伸展樹的根節點
 * @param z 插入的結點
 * @return
 */
private SplayTreeNode<T> insert(SplayTreeNode<T> tree, SplayTreeNode<T> z) {
    int cmp;
    SplayTreeNode<T> y = null;
    SplayTreeNode<T> x = tree;

    // 查找z的插入位置
    while (x != null) {
        y = x;
        cmp = z.key.compareTo(x.key);
        if (cmp < 0)
            x = x.left;
        else if (cmp > 0)
            x = x.right;
        else {
            System.out.printf("不允許插入相同節點(%d)!\n", z.key);
            z = null;
            return tree;
        }
    }

    if (y == null)
        tree = z;
    else {
        cmp = z.key.compareTo(y.key);
        if (cmp < 0)
            y.left = z;
        else
            y.right = z;
    }

    return tree;
}

public void insert(T key) {
    SplayTreeNode<T> z = new SplayTreeNode<T>(key, null, null);

    // 如果新建結點失敗，則返回。
    if ((z = new SplayTreeNode<T>(key, null, null)) == null)
        return;

    // 插入節點
    mRoot = insert(mRoot, z);
    // 將節點(key)旋轉為根節點
    mRoot = splay(mRoot, key);
}

/*


刪除結點(z)，并返回被刪除的結點
*
參數說明：
bst 伸展樹
z 刪除的結點
*/
/*

@param tree 伸展樹
@param key 刪除的結點
@return
*/
private SplayTreeNode<T> remove(SplayTreeNode<T> tree, T key) {
SplayTreeNode<T> x;
if (tree == null)
   return null;
// 查找鍵值為key的節點，找不到的話直接返回。
if (search(tree, key) == null)
   return tree;
// 將key對應的節點旋轉為根節點。
tree = splay(tree, key);
if (tree.left != null) {
   // 將"tree的前驅節點"旋轉為根節點
   x = splay(tree.left, key);
   // 移除tree節點
   x.right = tree.right;
}
else
   x = tree.right;
tree = null;
return x;
}


public void remove(T key) {
 mRoot = remove(mRoot, key);
}
/*

(遞歸實現)查找"伸展樹x"中鍵值為key的節點
*/
private SplayTreeNode<T> search(SplayTreeNode<T> x, T key) {
if (x==null)
   return x;
int cmp = key.compareTo(x.key);
if (cmp < 0)
   return search(x.left, key);
else if (cmp > 0)
   return search(x.right, key);
else
   return x;
}


public SplayTreeNode<T> search(T key) {
 return search(mRoot, key);
}
/*

查找最小結點：返回tree為根結點的伸展樹的最小結點。
*/
private SplayTreeNode<T> minimum(SplayTreeNode<T> tree) {
if (tree == null)
   return null;
while(tree.left != null)
   tree = tree.left;
return tree;
}


public T minimum() {
 SplayTreeNode<T> p = minimum(mRoot);
 if (p != null)

 return p.key;


return null;
}
/*

查找最大結點：返回tree為根結點的伸展樹的最大結點。
*/
private SplayTreeNode<T> maximum(SplayTreeNode<T> tree) {
if (tree == null)
   return null;
while(tree.right != null)
   tree = tree.right;
return tree;
}


public T maximum() {
 SplayTreeNode<T> p = maximum(mRoot);
 if (p != null)

 return p.key;


return null;
}
}</code></pre>
  
來自：http://blog.csdn.net/u012124438/article/details/78067998


                    
                         本文由用戶 GreOConnor 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
                         轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
                         本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！
                         本文地址：http://www.baiduhome.net/lib/view/open1506734884043.html
                         伸展樹 算法 Java Java開發

Java數據結構與算法解析——伸展樹

伸展樹簡介

特性

旋轉

伸展樹的實現

1.節點

2.旋轉

3.插入

4.刪除

相關經驗

相關資訊

相關文檔

目錄