淺談基礎算法之AVL tree和splay tree（三）

作者：川山甲 2012-10-17 14:20:57

開發架構算法

平衡二叉樹:上文我們只實現了單旋，但是實際中為了達到平衡很多是要做雙旋操作的。先來看一張雙旋后的一張圖，明顯右邊的圖查詢的時候會更便捷。

序

承接上文，我們繼續聊這個話題。

平衡二叉樹: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中的代碼，來講解

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

我的代碼結構:

代碼部分

/*~ 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))

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

/* 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; 
}