您當前位置：首頁 > php開源 > php教程 > 伸展樹 - 二叉搜索樹的擴展2

伸展樹 - 二叉搜索樹的擴展2

來源：程序員人生發布時間：2015-05-08 08:28:08 閱讀次數：3380次

- 舒展樹的介紹
- 舒展樹的C實現
  - 1 節點定義
  - 2 旋轉
  - 3 舒展樹的舒展
  - 4 搜索
  - 4 舒展樹的插入和刪除
- 全部代碼和參考資料

1. 舒展樹的介紹

舒展樹（splay tree）是1種搜索2叉樹，它能在 $O(log n)$ 內完成插入、查找和刪除操作。
（1）舒展樹滿足搜索2叉樹的性質，左子節點小于根節點，右子節點大于等于根節點。
（2）舒展樹獨有特點：當某個節點被訪問時，舒展樹會通過旋轉使該節點成為樹的根。

舒展樹的動身點是這樣的：斟酌到局部性原理（剛被訪問的內容下次更大的可能仍會被訪問）和28原則（80%的時間只會訪問20%的節點）,為了使全部查找時間更小，被查找頻率高的節點應當常常處于靠近根的位置。
因而提出以下方案：在每次查找以后對樹進行重構，把查找到的節點移到離樹根更近些。舒展樹應運而生，它是1種自調劑情勢的2叉搜索樹，它會沿著從某個節點到樹根的路徑，通過1系列的旋轉把這個節點搬到樹根上去。
因此相對“2叉搜索樹”和“AVL樹”，對舒展樹重點關注如何旋轉的

2. 舒展樹的C實現

以下舒展樹的實現思想來源于2叉搜索樹的根插法（先插入節點到葉子，然后遞歸旋轉到根），我們將查找到的節點旋轉到根，等價于將被查找節點插入到根部：

2.1 節點定義

typedef SplayTreeNode* SplayTree;
struct SplayTreeNode {
    Item key;
    SplayTree left;
    SplayTree right;
};

舒展樹不需要記錄額外甚么值（如AVL的高度）來保護樹的信息，節省了內存。

2.2 旋轉

引入兩種基本的旋轉：左旋和右旋
- 當被查找節點在根節點的左子樹上時，以根為軸，右旋，將該節點提升到根上

//右旋--k2是根，k1是k2的左子樹，將k1旋轉成根 -- 以k2為原點向右旋
SplayTree rotR(SplayTree k2) 
{
    SplayTree k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    return k1;
}

當被查找節點在根節點的右子樹上時，以根為軸，左旋，將該節點提升到根上

//左旋---k2是根，k1是k2的右子樹，(k1的右子樹非空)將k1旋轉成根 -- 以k2為原點向左旋
SplayTree rotL(SplayTree k2) 
{
    SplayTree k1 = k2->right;
    k2->right = k1->left;
    k1->left = k2;
    return k1;
}

2.3 舒展樹的舒展

<注>該算法實現沒有經過嚴格的驗證，自創；
如有疑問可參考經典算法：
舒展樹(1)之圖文解析和 C語言的實現：http://www.cnblogs.com/skywang12345/p/3604238.html

設被查找節點為 x , 當查找到 x 的先驅節點時：
（1） x 在當前根的左邊，那末右旋，將和 x 接近的節點向上提升1步；
（2） x 在當前根的右邊，那末左旋，將和 x 接近的節點向上提升1步；
（3） x 的值等于當前根的值，查找結束，在上述兩步遞歸進程中完成旋轉；
先驅節點不存在時，查找結束。

遞歸實現進程是自底向上的，當查找節點命中后，以它的父節點為軸旋轉，提升查找節點為根；向上遞歸，在根與查找節點的路徑上每步都旋轉1次，直至原樹根。

//舒展進程：將key對應的節點舒展到根上，并返回根節點
SplayTree Splay(SplayTree tree, Item key)
{
    if (tree == NULL)
        return tree;
    if (key == tree->key) //命中
        return tree;
    if (key < tree->key) { //左邊
        if (tree->left == NULL)
            return tree;
        tree->left = Splay(tree->left, key);
        tree = rotR(tree);
    } else { //右邊
        if (tree->right == NULL)
            return tree;
        tree->right = Splay(tree->right, key);
        tree = rotL(tree);
    }
    return tree;
}

2.4 搜索

SplayTree SplayTreeSearch(SplayTree tree, Item key)
{

    if (tree == NULL || tree->key == key)
        return tree;
    if (key < tree->key)
        return SplayTreeSearch(tree->left, key);
    else
        return SplayTreeSearch(tree->right, key);
}

2.4 舒展樹的插入和刪除

（1）插入：和搜索2叉樹的插入相同，省略

（2）刪除: 刪除舒展樹中鍵值為key的節點。
先在舒展樹中查找鍵值為key的節點：如果沒找到，則直接返回；如果找到的話則將該節點旋轉成根節點，然后在刪除該節點，然后將該節點的兩個子樹連接到1起（根節點選用和key鄰近的節點）；

/* 
*刪除舒展樹中鍵值為key的節點
*參數說明：
*   tree: 根節點
*   key: 待刪除節點的鍵值
*返回：
*   根節點
*/
SplayTree SplayTreeDelete(SplayTree tree, Item key)
{
    SplayTree x = NULL;
    if (tree == NULL)
        return tree;
    tree = Splay(tree, key);
    if (tree == NULL) 
        return tree;
    if (tree->left != NULL) {
        //將根的左邊，鄰近key的節點旋轉成根
        x = Splay(tree->left, key);
        x->right = tree->right;
    } else {
        //tree->left == NULL
        x = tree->right;
    }
    delete tree;
    return x;
}

3. 全部代碼和參考資料

#include <stdio.h>
#include <stdlib.h>
#define MAX(A, B) ((A > B) ? A : B)
typedef int Item;
typedef struct SplayTreeNode SplayTreeNode;
typedef SplayTreeNode* SplayTree;
struct SplayTreeNode {
    Item key;
    SplayTree left;
    SplayTree right;
};
static int g_error = 0; //毛病代碼
SplayTree NewNode(Item key, SplayTree left, SplayTree right)
{
    SplayTree x = (SplayTree)malloc(sizeof(*x));
    if (x == NULL) {
        g_error = 1;
        exit(-1);
    }
    x->key = key;
    x->left = left;
    x->right = right;
    return x;
}

SplayTree SplayTreeInit()
{
    return NewNode(10, NULL, NULL);    
}



//左旋---k2是根，k1是k2的右子樹，(k1的右子樹非空)將k1旋轉成根 -- 以k2為原點向左旋
SplayTree rotL(SplayTree k2) 
{
    SplayTree k1 = k2->right;
    k2->right = k1->left;
    k1->left = k2;
    return k1;
}

//右旋--k2是根，k1是k2的左子樹，將k1旋轉成根 -- 以k2為原點向右旋
SplayTree rotR(SplayTree k2) 
{
    SplayTree k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    return k1;
}




SplayTree Splay(SplayTree tree, Item key)
{
    if (tree == NULL)
        return tree;
    if (key == tree->key)
        return tree;
    if (key < tree->key) { //左邊
        if (tree->left == NULL)
            return tree;
        tree->left = Splay(tree->left, key);
        tree = rotR(tree);
    } else { //右邊
        if (tree->right == NULL)
            return tree;
        tree->right = Splay(tree->right, key);
        tree = rotL(tree);
    }
    return tree;
}
SplayTree SplayTreeSearch(SplayTree tree, Item key)
{

    if (tree == NULL || tree->key == key)
        return tree;
    if (key < tree->key)
        return SplayTreeSearch(tree->left, key);
    else
        return SplayTreeSearch(tree->right, key);
}

SplayTree SplayTreeInsert(SplayTree tree, Item key)
{   
    if (tree == NULL)
        return NewNode(key, NULL, NULL);
    if(key < tree->key) 
        tree->left = SplayTreeInsert(tree->left, key);
    else
        tree->right = SplayTreeInsert(tree->right, key);
    return tree;
}

void traversal(SplayTree tree)
{
    if (tree == NULL) {
        printf("NIL	");
        return;
    }
    printf("%d	", tree->key);
    traversal(tree->left);
    traversal(tree->right);
    return;
}


SplayTree SplayTreeDelete(SplayTree tree, Item key)
{
    SplayTree x = NULL;
    if (tree == NULL)
        return tree;
    tree = Splay(tree, key);
    if (tree == NULL) 
        return tree;
    if (tree->left != NULL) {
        x = Splay(tree->left, key);
        x->right = tree->right;
    } else {
        //tree->left == NULL
        x = tree->right;
    }
    delete tree;
    return x;
}

int main()
{
    SplayTree splay_tree = NULL;
    //for (int i = 0; i < 10; i++) {
    //  int key = rand()%100;
    //  splay_tree = SplayTreeInsert(splay_tree, key);
    //  printf("%d	", key);
    //}
    splay_tree = SplayTreeInsert(splay_tree, 1);
    splay_tree = SplayTreeInsert(splay_tree, 5);
    splay_tree = SplayTreeInsert(splay_tree, 4);
    splay_tree = SplayTreeInsert(splay_tree, 2);
    splay_tree = SplayTreeInsert(splay_tree, 6);

    printf("
Traversal
");
    traversal(splay_tree);
    splay_tree = Splay(splay_tree, 6);
    splay_tree = SplayTreeDelete(splay_tree, 4);
    printf("
Deleted Traversal
");
    traversal(splay_tree);
    getchar();
}

參考資料：
舒展樹-維基百科：https://zh.wikipedia.org/wiki/%E4%BC%B8%E5%B1%95%E6%A0%91
舒展樹(1)之圖文解析和 C語言的實現：http://www.cnblogs.com/skywang12345/p/3604238.html
2叉搜索樹的實現：http://blog.csdn.net/quzhongxin/article/details/45038399

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生