前言接上文，我们继续聊这个话题。Balancedbinarytree:AVLTree(1962)上面我们只实现了单轮旋转，但在实践中需要很多双轮转操作才能达到平衡。先来看一张双旋转后的图。显然，右边的图片查询起来会更方便。下面我们将全程进行代码实践。#include#include#definemax(a,b)(((a)>(b))?(a):(b))typedefstructAvlNode{intdata;structAvlNode*left_child,*right_child;}AvlNode;AvlNode*root;/*旋转动作开始*/AvlNode*rotate_LL(AvlNode*parent){AvlNode*child=parent->left_child;parent->left_child=child->right_child;child->right_child=parent;returnchild;}AvlNode*rotate_RR(AvlNode*parent){AvlNode*child=parent->right_child;parent->right_child=child->left_child;child->left_child=parent;returnchild;}AvlNode*rotate_RL(AvlNode*parent){AvlNode*child=parent->right_child;parent->right_child=rotate_LL(child);returnrotate_RR(parent);}AvlNode*rotate_LR(AvlNode*parent){AvlNode*child=parent->left_child;parent->left_child=rotate_RR(child);returnrotate_LL(parent);}/*旋转动作绑定*/intget_height(AvlNode*node){intheight=0;if(node!=NULL){height=1+max(get_height(node->left_child),get_height(node->right_child));}returnheight;}intget_balance(AvlNode*node){if(node==NULL)return0;returnget_height(node->left_child)-get_height(node->right_child);}/*平衡二叉树*/AvlNode*balance_tree(AvlNode**node){intheight_diff=get_balance(*node);/*平衡因子在-1到1之间*/if(height_diff>1){if(get_balance((*node)->left_child)>0){*node=rotate_LL(*node);}else{*node=rotate_LR(*node);}}elseif(height_diff<-1){if(get_balance((*node)->right_child)<0){*node=rotate_RR(*node);}else{*node=rotate_RL(*node);}}return*node;}AvlNode*avl_add(AvlNode**root,intkey){if(*root==NULL){*root=(AvlNode*)malloc(sizeof(AvlNode));if(*root==NULL){printf("内存分配失败!\n");exit(-1);}(*root)->data=key;(*root)->left_child=(*root)->right_child=NULL;}elseif(key<(*root)->data){(*root)->left_child=avl_add(&((*root)->left_child),key);//balance_tree(root);}elseif(key>(*root)->data){(*root)->right_child=avl_add(&((*root)->right_child),key);//balance_tree(root);}else{printf("复制%d失败!\n",key);exit(-1);}return*root;}AvlNode*avl_print(AvlNode*node){if(node==NULL)返回NULL;printf("%d->",node->data);avl_print(node->left_child);avl_print(node->right_child);returnnode;}intmain(){avl_add(&root,24);avl_add(&root,17);avl_add(&root,40);avl_add(&root,8);avl_add(&root,22);avl_add(&root,18);avl_add(&root,23);printf("打印二叉树\n");avl_print(root);printf("\n");balance_tree(&root);printf("打印二叉树\n");avl_print(root);printf("\n");return0;}让我们看看伸展树！SplayTree(SplayTree,1985)splaytree的基本原理：比如我提取了一部分lighttpd-1.4.31.tar.gz的代码，讲解具体的代码实践，大家可以到以下位置去看我的代码结构：代码部分/*~splaytree.h~*/typedefstructtree_node{structtree_node*left,*right;intkey;/*keyword*/intsize;/*Numberofnodes*/void*data;}splay_tree;/*我现在只写这两个方法*/splay_tree*splaytree_insert(splay_tree*t,intkey,void*data);splay_tree*splaytree_splay(splay_tree*t,intkey);#definenode_size(x)(((x)==NULL)?0:((x)->size))这个不用多说，看注释和方法名就知道是做什么用的！/*splaytree.c*/#include"splaytree.h"#include#include#include#definecompare(i,j)((i)-(j))splay_tree*splaytree_insert(splay_tree*t,intkey,void*data){splay_tree*new;if(t!=NULL){t=splaytree_splay(t,key);if(compare(key,t->key)==0){/*该结点已经存在于*/returnt;}}new=(splay_tree*)malloc(sizeof(splay_tree));assert(new);if(t==NULL){new->left=new->right=NULL;}elseif(compare(key,t->key)<0){new->left=t->left;new->right=t;t->left=NULL;t->size=1+node_size(t->right);}else{new->right=t->right;new->left=t;t->right=NULL;t->size=1+node_size(t->left);}new->key=key;new->data=data;new->size=1+node_size(new->left)+node_size(new->right);returnnew;}splay_tree*splaytree_splay(splay_tree*t,intkey){splay_treeN,*l,*r,*child;/*临时变量用于安装*t使用*/intcmp,l_size,r_size;if(t==NULL)returnt;N.left=N.right=NULL;l=r=&N;l_size=r_size=0;for(;;){cmp=compare(key,t->key);if(cmp<0){if(t->left==NULL)break;if(compare(key,t->left->key)<0){child=t->left;/*右旋*/t->left=child->right;child->right=t;t->size=1+node_size(t->left)+node_size(t->right);t=child;if(t->left==NULL)break;}r->left=t;/*右链*/r=t;t=t->left;r_size+=1+node_size(r->right);}elseif(cmp>0){if(t->right==NULL)break;if(compare(key,t->right->key)>0){child=t->right;t->right=child->left;child->left=t;t->size=1+node_size(t->left)+node_size(t->right);t=child;if(t->right==NULL)break;}l->right=t;l=t;t=t->右;l_size+=1+node_size(l->left);}else{break;}}l_size+=node_size(t->left);r_size+=node_size(t->right);t->size=1+l_size+r_size;l->right=r->left=NULL;/*校试size数据*//*右孩子的左结点不计算在里面*/for(child=N.right;child!=NULL;child=child->right){child->size=l_size;l_size-=1+node_size(child->left);}for(child=N.left;child!=NULL;child=child->left){child->size=r_size;r_size-=1+node_size(child->right);}/*组装数据*/l->right=t->left;r->left=t->right;t->left=N.right;t->right=N.left;return;}看到上面一堆代码，估计大家都不知道该说什么了吧？我有针对性的讲解一下>>重点说一下核心算法splaytree_splay()方法！这个if有道理，另外一个elseif也很好理解。if(cmp<0){if(t->left==NULL)break;if(compare(key,t->left->key)<0){child=t->left;/*右旋转*/t->left=child->right;child->right=t;t->size=1+node_size(t->left)+node_size(t->right);t=child;if(t->left==NULL)break;}r->left=t;/*右链*/r=t;t=t->left;r_size+=1+node_size(r->right);}这是右手链过程。child=t->leftt->left=child->right;孩子->权利=t；最后：t=child这是一个右链过程r->left=t;r=t;t=t->left3>main.c#include#include"splaytree.h"splay_tree*splaytree_print(splay_tree*t){if(t!=NULL){printf("t->data:%d\tt->key:%dt->size:%d\n",*((int*)t->data),t->key,t->size);splaytree_print(t->left);splaytree_print(t->right);}}intmain(){splay_tree*root;root=NULL;intdata1=1000;root=splaytree_insert(root,20,&data1);intdata2=200;root=splaytree_insert(root,5,&data2);intdata3=300;root=splaytree_insert(root,3,&data3);intdata4=100;root=splaytree_insert(root,10,&data4);printf("打印结果***************\n");splaytree_print(root);//这里应该有查询数据的过程，我没写调用的时候注意调用splay方法，//那么热点数据自然会跑到最前面。printf("在查询方法中调用该扩展函数后，打印结果***************\n");root=splaytree_splay(root,3);splaytree_print(root);return0;}这里我没有写下查询展开树的过程，只是想强调一下，在查询过程中，只要调用这个核心方法，自然热点数据就会往上跑。看看过程原文链接：http://www.cnblogs.com/baochuan/archive/2012/10/16/2716641.html【小编推荐】大型网站后台搭建实践图片存储架构学习：缓存，架构师的美女情妇浅谈大型网站的算法与架构（二）浅谈大型网站的算法与架构企业应用架构模型之工作单元模型
