多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

國內最全IT社區平臺 聯系我們 | 收藏本站
阿里云優惠2
您當前位置：首頁 > php開源 > php教程 > 伸展樹 - 二叉搜索樹的擴展2

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

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

目錄

    • 舒展樹的介紹
    • 舒展樹的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

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
為碼而活
積分：4237
15粉絲
7關注
欄目熱點
關閉
程序員人生
主站蜘蛛池模板： 国产片性视频免费播放 | 亚洲韩国日本一级二级r级 亚洲韩精品欧美一区二区三区 | 欧美日本在线播放 | 亚洲欧美日韩在线观看看另类 | 亚洲综合天堂 | 免费网站看v片在线观看 | 日韩欧美亚洲综合一区二区 | 国产成人精品日本亚洲直接 | 中文字幕第2页 | 国产精品v欧美精品v日韩精品 | 在线观看的免费视频网站 | 另类专区另类专区亚洲 | 网友自拍网站 | 免费一级毛片在线视频观看 | 国产精品视频一区二区三区不卡 | 久久亚洲国产精品一区二区 | 中文字幕乱码系列免费 | 国产日韩高清一区二区三区 | 日本无卡码免费一区二区三区 | 自拍欧美亚洲 | 久久久久久免费一区二区三区 | 久久99国产精品久久99 | 视频二区 调教中字 知名国产 | 亚洲一区二区中文 | 午夜视频啪啪 | 一区二区在线欧美日韩中文 | 国产在线精品福利一区二区三区 | 亚洲综合精品一区二区三区中文 | 精品国产免费福利片 | 欧美人与动性xxxxx杂性 | 欧美成人高清性色生活 | 国产一区二区福利久久 | 波多野氏免费一区 | 最近免费中文字幕大全视频 | 成人精品国产亚洲欧洲 | 欧美日韩精品国产一区二区 | 在线观看欧美精品 | 最近高清中文字幕大全1 | 亚洲精品免费在线视频 | 一区二区三区四区日韩 | 久久久毛片免费全部播放 |