自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

淺談基礎(chǔ)算法之AVL tree和splay tree（三）

作者：川山甲
開發(fā) 架構(gòu) 算法
平衡二叉樹:上文我們只實(shí)現(xiàn)了單旋，但是實(shí)際中為了達(dá)到平衡很多是要做雙旋操作的。先來看一張雙旋后的一張圖，明顯右邊的圖查詢的時(shí)候會(huì)更便捷。

序

承接上文，我們繼續(xù)聊這個(gè)話題。

平衡二叉樹:AVL Tree(1962)

上文我們只實(shí)現(xiàn)了單旋，但是實(shí)際中為了達(dá)到平衡很多是要做雙旋操作的。

先來看一張雙旋后的一張圖，明顯右邊的圖查詢的時(shí)候會(huì)更便捷。

  整個(gè)過程

  下面我們就進(jìn)行代碼實(shí)踐。

  1. #include <stdio.h> 
  2. #include <stdlib.h> 
  3.  
  4. #define max(a,b)    (((a) > (b)) ? (a) : (b))  
  5.  
  6. typedef struct AvlNode{ 
  7.     int data; 
  8.     struct AvlNode *left_child, *right_child; 
  9. } AvlNode; 
  10.  
  11. AvlNode *root; 
  12.  
  13. /*    旋轉(zhuǎn)動(dòng)作開始        */ 
  14. AvlNode *rotate_LL(AvlNode *parent){ 
  15.     AvlNode *child = parent->left_child; 
  16.     parent->left_child = child->right_child; 
  17.     child->right_child = parent; 
  18.     return child; 
  19. } 
  20.  
  21. AvlNode *rotate_RR(AvlNode *parent){ 
  22.     AvlNode *child = parent->right_child; 
  23.     parent->right_child = child->left_child; 
  24.     child->left_child = parent; 
  25.     return child; 
  26. } 
  27.  
  28. AvlNode *rotate_RL(AvlNode *parent){ 
  29.     AvlNode *child = parent->right_child; 
  30.     parent->right_child = rotate_LL(child); 
  31.     return rotate_RR(parent); 
  32. } 
  33.  
  34. AvlNode *rotate_LR(AvlNode *parent){ 
  35.     AvlNode *child = parent->left_child; 
  36.     parent->left_child = rotate_RR(child); 
  37.     return rotate_LL(parent); 
  38. } 
  39. /*    旋轉(zhuǎn)動(dòng)作結(jié)束    */ 
  40.  
  41. int get_height(AvlNode *node){ 
  42.     int height = 0; 
  43.     if(node != NULL){ 
  44.         height = 1 + max(get_height(node->left_child), get_height(node->right_child)); 
  45.     } 
  46.     return height; 
  47. } 
  48.  
  49. int get_balance(AvlNode *node){ 
  50.     if(node == NULL) return 0; 
  51.     return get_height(node->left_child) - get_height(node->right_child); 
  52. } 
  53.  
  54. /*    平衡二叉樹    */ 
  55. AvlNode *balance_tree(AvlNode **node){ 
  56.     int height_diff = get_balance(*node); /* 平衡因子在-1到1之間*/ 
  57.  
  58.     if(height_diff > 1){ 
  59.         if(get_balance((*node)->left_child) > 0){ 
  60.             *node = rotate_LL(*node); 
  61.         }else{ 
  62.             *node = rotate_LR(*node); 
  63.         } 
  64.     }else if(height_diff < -1){ 
  65.         if(get_balance((*node)->right_child) < 0){ 
  66.             *node = rotate_RR(*node); 
  67.         }else{ 
  68.             *node = rotate_RL(*node); 
  69.         } 
  70.     } 
  71.     return *node; 
  72. } 
  73.  
  74. AvlNode *avl_add(AvlNode **root, int key){ 
  75.     if(*root == NULL){ 
  76.         *root = (AvlNode *)malloc(sizeof(AvlNode)); 
  77.         if(*root == NULL){ 
  78.             printf("內(nèi)存分配失敗!\n"); 
  79.             exit(-1); 
  80.         } 
  81.  
  82.         (*root)->data = key; 
  83.         (*root)->left_child = (*root)->right_child = NULL; 
  84.     }else if(key < (*root)->data){ 
  85.         (*root)->left_child = avl_add(&((*root)->left_child), key); 
  86.         //balance_tree(root); 
  87.     }else if(key > (*root)->data){ 
  88.         (*root)->right_child = avl_add(&((*root)->right_child), key); 
  89.         //balance_tree(root); 
  90.     }else{ 
  91.         printf("復(fù)制%d失敗!\n", key); 
  92.         exit(-1); 
  93.     } 
  94.  
  95.     return *root; 
  96. } 
  97.  
  98. AvlNode *avl_print(AvlNode *node){ 
  99.     if(node == NULL) return NULL; 
  100.  
  101.     printf("%d->", node->data); 
  102.  
  103.     avl_print(node->left_child); 
  104.     avl_print(node->right_child); 
  105.     return node; 
  106. } 
  107.  
  108. int main(){ 
  109.     avl_add(&root, 24); 
  110.     avl_add(&root, 17); 
  111.     avl_add(&root, 40); 
  112.     avl_add(&root, 8); 
  113.     avl_add(&root, 22); 
  114.     avl_add(&root, 18); 
  115.     avl_add(&root, 23); 
  116.  
  117.     printf("打印二叉樹\n"); 
  118.     avl_print(root); 
  119.     printf("\n"); 
  120.  
  121.     balance_tree(&root); 
  122.     printf("打印二叉樹\n"); 
  123.     avl_print(root); 
  124.     printf("\n"); 
  125.     return 0; 
  126. } 

 

                   

讓我們看看伸展樹!     

伸展樹（Splay Tree，1985）

伸展樹的基本原理：

   

 舉例

我抽取一部分lighttpd-1.4.31.tar.gz中的代碼，來講解 

想看具體的代碼實(shí)踐的，可以到如下位置觀看

我的代碼結(jié)構(gòu):

代碼部分

  1. /*~ splaytree.h~*/ 
  2. typedef struct tree_node{ 
  3.     struct tree_node *left, *right; 
  4.     int key;    /*  關(guān)鍵字  */ 
  5.     int size;   /*  結(jié)點(diǎn)數(shù)目    */ 
  6.     void *data; 
  7. } splay_tree; 
  8. /*我現(xiàn)在只寫這兩個(gè)方法*/ 
  9. splay_tree * splaytree_insert(splay_tree *t, int key, void *data); 
  10. splay_tree * splaytree_splay(splay_tree *t, int key); 
  11. #define node_size(x) (((x)==NULL) ? 0 : ((x)->size)) 

這個(gè)沒有必要多講，看注釋和方法名稱自然就知道干嗎的了！

  1. /* splaytree.c */ 
  2. #include "splaytree.h" 
  3. #include <stdio.h> 
  4. #include <stdlib.h> 
  5. #include <assert.h> 
  6. #define compare(i,j) ((i) - (j)) 
  7. splay_tree * splaytree_insert(splay_tree *t, int key, void *data){ 
  8.     splay_tree * new; 
  9.  
  10.     if (t != NULL) { 
  11.         t = splaytree_splay(t, key); 
  12.         if(compare(key, t->key) == 0){ /*   該結(jié)點(diǎn)已存在    */ 
  13.             return t; 
  14.         } 
  15.     } 
  16.     new = (splay_tree *) malloc (sizeof (splay_tree)); 
  17.     assert(new); 
  18.     if (t == NULL) { 
  19.         new->left = new->right = NULL; 
  20.     } else if (compare(key, t->key) < 0) { 
  21.         new->left = t->left; 
  22.         new->right = t; 
  23.         t->left = NULL; 
  24.         t->size = 1 + node_size(t->right); 
  25.     } else { 
  26.         new->right = t->right; 
  27.         new->left = t; 
  28.         t->right = NULL; 
  29.         t->size = 1 + node_size(t->left); 
  30.     } 
  31.     new->key = key; 
  32.     new->data = data; 
  33. new->size = 1 + node_size(new->left) + node_size(new->right); 
  34.     return new; 
  35. } 
  36. splay_tree * splaytree_splay(splay_tree *t, int key){ 
  37.     splay_tree N, *l, *r, *child; /*    臨時(shí)變量用于裝配*t使用  */ 
  38.     int cmp, l_size, r_size; 
  39.     if (t == NULL) return t; 
  40.     N.left = N.right = NULL; 
  41.     l = r = &N; 
  42.     l_size = r_size = 0; 
  43.     for (;;) { 
  44.         cmp = compare(key, t->key); 
  45.  
  46.         if (cmp < 0) { 
  47.             if(t->left == NULL) break; 
  48.             if (compare(key, t->left->key) < 0) { 
  49.                 child = t->left;                        /*  右旋    */ 
  50.                 t->left = child->right; 
  51.                 child->right = t; 
  52.                 t->size = 1 + node_size(t->left) + node_size(t->right); 
  53.                 t = child; 
  54.                 if(t->left == NULL) break; 
  55.             } 
  56.             r->left = t;                                /*  右鏈    */ 
  57.             r = t; 
  58.             t = t->left; 
  59.             r_size += 1 + node_size(r->right); 
  60.         } else if (cmp > 0) { 
  61.             if(t->right == NULL) break; 
  62.  
  63.             if (compare(key, t->right->key) > 0) { 
  64.                 child =  t->right; 
  65.                 t->right = child->left; 
  66.                 child->left = t; 
  67.                 t->size = 1 + node_size(t->left) + node_size(t->right); 
  68.                 t = child; 
  69.                 if(t->right == NULL) break; 
  70.             } 
  71.             l->right = t; 
  72.             l = t; 
  73.             t = t->right; 
  74.             l_size += 1 + node_size(l->left); 
  75.         } else { 
  76.             break; 
  77.         } 
  78.     } 
  79.     l_size += node_size(t->left); 
  80.     r_size += node_size(t->right); 
  81.     t->size = 1 + l_size + r_size; 
  82.  
  83.     l->right = r->left = NULL; 
  84.  
  85.     /*  校驗(yàn)size數(shù)據(jù)    */ 
  86.     /*右孩子的左結(jié)點(diǎn)不計(jì)算在內(nèi)*/ 
  87.     for(child = N.right; child != NULL; child = child->right){ 
  88.         child->size = l_size; 
  89.         l_size -= 1 + node_size(child->left); 
  90.     } 
  91.     for(child = N.left; child != NULL; child = child->left){ 
  92.         child->size = r_size; 
  93.  r_size -= 1 +node_size(child->right); 
  94.     } 
  95.     /*  裝配數(shù)據(jù)    */ 
  96.     l->right = t->left; 
  97.     r->left = t->right; 
  98.     t->left = N.right; 
  99.     t->right = N.left; 
  100.     return t; 
  101. } 

看到上面一坨代碼估計(jì)大家不知所云了？

我就針對(duì)性的講解一下。

>> 重點(diǎn)講講講核心算法splaytree_splay()方法吧!

這個(gè)if講通，那么另一個(gè)else if也好理解。

  1. if (cmp < 0) { 
  2.             if(t->left == NULL) break; 
  3.  
  4.             if (compare(key, t->left->key) < 0) { 
  5.                 child = t->left;                        /*  右旋    */ 
  6.                 t->left = child->right; 
  7.                 child->right = t; 
  8.                 t->size = 1 + node_size(t->left) + node_size(t->right); 
  9.                 t = child; 
  10.  
  11.                 if(t->left == NULL) break; 
  12.             } 
  13.             r->left = t;                                /*  右鏈    */ 
  14.             r = t; 
  15.             t = t->left; 
  16.             r_size += 1 + node_size(r->right); 
  17.         } 

這是一個(gè)右旋的過程。

  child = t->left

t->left = child->right; child->right = t;

 最后:t = child

這是一個(gè)右鏈的過程

 r->left = t;r=t;

 t = t->left

3>main.c

  1. #include <stdio.h> 
  2. #include "splaytree.h" 
  3. splay_tree * splaytree_print(splay_tree *t){ 
  4.     if(t != NULL){ 
  5.         printf("t->data:%d\t t->key:%d t->size:%d\n", *((int *)t->data), t->key, t->size); 
  6.         splaytree_print(t->left); 
  7.         splaytree_print(t->right); 
  8.     } 
  9. } 
  10. int main(){ 
  11.     splay_tree *root; 
  12.     root = NULL; 
  13.     int data1 = 1000; 
  14.     root = splaytree_insert(root, 20, &data1); 
  15.     int data2 = 200; 
  16.     root = splaytree_insert(root, 5, &data2); 
  17.     int data3 = 300; 
  18.     root = splaytree_insert(root, 3, &data3); 
  19.     int data4 = 100; 
  20.     root = splaytree_insert(root, 10, &data4); 
  21.     printf("打印結(jié)果*************\n"); 
  22.     splaytree_print(root); 
  23.  
  24.  
  25.     //這里應(yīng)該有個(gè)數(shù)據(jù)查詢過程，但是我沒有寫。注意在調(diào)用的時(shí)候調(diào)用一下splay方法， 
  26.     //那么熱數(shù)據(jù)自然就跑到頂端了。 
  27.     printf("查詢方法中調(diào)用這個(gè)伸展函數(shù)之后，打印結(jié)果*************\n"); 
  28.     root = splaytree_splay(root, 3); 
  29.     splaytree_print(root); 
  30.     return 0; 
  31. } 

這里我沒有把查詢伸展樹的過程寫下來，只是強(qiáng)調(diào)一下，在查詢的過程中，只要調(diào)用這個(gè)核心方法，那么自然熱數(shù)據(jù)就跑到頂端了。

看一下過程

 

 

原文鏈接：http://www.cnblogs.com/baochuan/archive/2012/10/16/2716641.html 

【編輯推薦】

  1. 大型網(wǎng)站后臺(tái)構(gòu)建實(shí)踐
  2. 圖片存儲(chǔ)架構(gòu)學(xué)習(xí)：緩存，架構(gòu)師的美麗小三
  3. 淺談大型網(wǎng)站的算法和架構(gòu)（二）
  4. 淺談大型網(wǎng)站的算法和架構(gòu)
  5. 企業(yè)應(yīng)用架構(gòu)模式之工作單元模式
責(zé)任編輯：張偉 來源： 川山甲的博客
架構(gòu)算法PHP
相關(guān)推薦

2022-10-30 10:03:20

B+數(shù)據(jù)庫數(shù)據(jù)

2024-02-27 07:35:55

B-TreeB+TreeMySQL

2019-11-26 15:12:08

數(shù)據(jù)存儲(chǔ)B+樹

2022-06-01 12:04:02

項(xiàng)目Webpack

2017-07-18 16:25:31

機(jī)器學(xué)習(xí)算法決策樹

2022-09-26 07:56:53

AVL算法二叉樹

2009-09-09 17:08:27

LINQ Expres

2011-08-16 09:13:45

tree中文man

2023-10-10 11:02:00

LSM Tree數(shù)據(jù)庫

2009-09-09 17:02:05

LINQ Expres

2023-01-04 08:33:31

Linuxtree命令

2022-10-29 08:44:39

分布式數(shù)據(jù)庫存儲(chǔ)

2010-10-12 16:50:14

MySQL Hash索

2011-11-24 21:12:35

ibmdw

2020-02-13 17:27:31

CAPPaxos 共識(shí)算法

2021-06-28 07:01:50

Webpack 前端Tree shakin

2017-07-20 15:59:45

LinuxDevice Tree

2022-02-10 14:23:16

WebpackJavaScript

2023-01-26 00:59:39

B-Treegolang度量衡

2020-06-28 09:03:26

Linuxtree命令目錄
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)