百度做网站的费用/药品销售推广方案

序

承接上文，我们继续聊这个话题。

平衡二叉树:AVL Tree(1962)

上文我们只实现了单旋，但是实际中为了达到平衡很多是要做双旋操作的。

先来看一张双旋后的一张图，明显右边的图查询的时候会更便捷。

整个过程

下面我们就进行代码实践。

#include <stdio.h>
#include <stdlib.h>#define max(a,b)    (((a) > (b)) ? (a) : (b)) typedef struct AvlNode{int data;struct AvlNode *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;return child;
}AvlNode *rotate_RR(AvlNode *parent){AvlNode *child = parent->right_child;parent->right_child = child->left_child;child->left_child = parent;return child;
}AvlNode *rotate_RL(AvlNode *parent){AvlNode *child = parent->right_child;parent->right_child = rotate_LL(child);return rotate_RR(parent);
}AvlNode *rotate_LR(AvlNode *parent){AvlNode *child = parent->left_child;parent->left_child = rotate_RR(child);return rotate_LL(parent);
}
/*    旋转动作结束    */int get_height(AvlNode *node){int height = 0;if(node != NULL){height = 1 + max(get_height(node->left_child), get_height(node->right_child));}return height;
}int get_balance(AvlNode *node){if(node == NULL) return 0;return get_height(node->left_child) - get_height(node->right_child);
}/*    平衡二叉树    */
AvlNode *balance_tree(AvlNode **node){int height_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);}}else if(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, int key){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;}else if(key < (*root)->data){(*root)->left_child = avl_add(&((*root)->left_child), key);//balance_tree(root);}else if(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) return NULL;printf("%d->", node->data);avl_print(node->left_child);avl_print(node->right_child);return node;
}int main(){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");return 0;
}

                                    

                                    

让我们看看伸展树!     

伸展树（Splay Tree，1985）

伸展树的基本原理：

                                    

                                    举例

 我抽取一部分lighttpd-1.4.31.tar.gz中的代码，来讲解 

想看具体的代码实践的，可以到如下位置观看

 

我的代码结构:

 

 代码部分

 1> splaytree.h

/*~ splaytree.h~*/typedef struct tree_node{struct tree_node *left, *right;int key;    /*  关键字  */int size;   /*  结点数目    */void *data;
} splay_tree;/*我现在只写这两个方法*/
splay_tree * splaytree_insert(splay_tree *t, int key, void *data);
splay_tree * splaytree_splay(splay_tree *t, int key);#define node_size(x) (((x)==NULL) ? 0 : ((x)->size))

这个没有必要多讲，看注释和方法名称自然就知道干吗的了！

2> splaytree.c

/* splaytree.c */
#include "splaytree.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>#define compare(i,j) ((i) - (j))splay_tree * splaytree_insert(splay_tree *t, int key, void *data){splay_tree * new;if (t != NULL) {t = splaytree_splay(t, key);if(compare(key, t->key) == 0){ /*   该结点已存在    */return t;}}new = (splay_tree *) malloc (sizeof (splay_tree));assert(new);if (t == NULL) {new->left = new->right = NULL;} else if (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);return new;
}splay_tree * splaytree_splay(splay_tree *t, int key){splay_tree N, *l, *r, *child; /*    临时变量用于装配*t使用  */int cmp, l_size, r_size;if (t == NULL) return t;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);} else if (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->right;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 t;
}

看到上面一坨代码估计大家不知所云了？

我就针对性的讲解一下。

　　>> 重点讲讲讲核心算法splaytree_splay()方法吧!

############################################################################################

这个if讲通，那么另一个else if也好理解。

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->left

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

                                    最后:t = child

                         

 

这是一个右链的过程

                                    r->left = t;r=t;

                                    t = t->left

############################################################################################

3>main.c

#include <stdio.h>#include "splaytree.h"splay_tree * splaytree_print(splay_tree *t){if(t != NULL){printf("t->data:%d\t t->key:%d t->size:%d\n", *((int *)t->data), t->key, t->size);splaytree_print(t->left);splaytree_print(t->right);}
}int main(){splay_tree *root;root = NULL;int data1 = 1000;root = splaytree_insert(root, 20, &data1);int data2 = 200;root = splaytree_insert(root, 5, &data2);int data3 = 300;root = splaytree_insert(root, 3, &data3);int data4 = 100;root = splaytree_insert(root, 10, &data4);printf("打印结果*************\n");splaytree_print(root);//这里应该有个数据查询过程，但是我没有写。注意在调用的时候调用一下splay方法，//那么热数据自然就跑到顶端了。printf("查询方法中调用这个伸展函数之后，打印结果*************\n");root = splaytree_splay(root, 3);splaytree_print(root);return 0;
}

                                    

这里我没有把查询伸展树的过程写下来，只是强调一下，在查询的过程中，只要调用这个核心方法，那么自然热数据就跑到顶端了。

                                    看一下过程

 

                                   

                                   

推荐