基本的なアルゴリズムについての簡単な説明: AVL ツリーとスプレイツリー (パート 3)

順序

上記に引き続き、このトピックについて話し続けましょう。

バランス二分木: AVL 木 (1962)

上記では、単一の回転のみを実装しましたが、実際にはバランスをとるために、多くの二重回転操作が必要になります。

まずは二重回転後の画像を見てみましょう。右側の画像の方がクエリしやすいのは明らかです。

全体のプロセス

それではコードを練習してみましょう。

 # <stdio.h>をインクルードする
# <stdlib.h>をインクルードする
 
 #define max(a,b) (((a) > (b)) ? (a) : (b)) 
 
 typedef 構造体 AvlNode{
    整数データ;
    構造体 AvlNode *left_child、*right_child;
 }AvlNode; 
 
 AvlNode *ルート; 
 
 /* 回転を開始します */  
 AvlNode *rotate_LL(AvlNode *親){
    AvlNode *child = parent->left_child;
    親->左の子 = 子->右の子;
    子->right_child = 親;
子を返します。
 } 
 
 AvlNode *rotate_RR(AvlNode *親){
    AvlNode *child = parent->right_child;
    親->右の子 = 子->左の子;
    子->left_child = 親;
子を返します。
 } 
 
 AvlNode *rotate_RL(AvlNode *親){
    AvlNode *child = parent->right_child;
    親->right_child = rotate_LL(child);
 rotate_RR(親)を返します。
 } 
 
 AvlNode *rotate_LR(AvlNode *親){
    AvlNode *child = parent->left_child;
    親->left_child = rotate_RR(child);
 rotate_LL(親)を返します。
 }
 /* 回転終了 */   
 
 int get_height(AvlNode *ノード){
    整数高さ = 0;
 if (ノード != NULL){
        高さ = 1 + max(get_height(node->left_child), get_height(node->right_child));
    }
高さを返します。
 } 
 
 int get_balance(AvlNode *ノード){
 if (node == NULL) 0を返します。
 get_height(node->left_child) - get_height(node->right_child) を返します。
 } 
 
 /* バランスのとれた二分木 */  
 AvlNode *balance_tree(AvlNode **node){
    int height_diff = get_balance(*node); /* バランス係数は -1 から 1 の間です*/   
 
高さの差が1より大きい場合
get_balance((*node)->left_child) > 0の場合{
            *ノード = rotate_LL(*ノード);
        }それ以外{
            *ノード = rotate_LR(*ノード);
        }
    }それ以外 高さの差が -1 未満の場合{
 get_balance((*node)->right_child) < 0)の場合{
            *ノード = rotate_RR(*ノード);
        }それ以外{
            *ノード = rotate_RL(*ノード);
        }
    }
 *ノードを返します。
 } 
 
 AvlNode *avl_add(AvlNode **ルート、intキー){
 (*root == NULL)の場合{
        *ルート = (AvlNode *)malloc(sizeof(AvlNode));
 (*root == NULL)の場合{
            printf( "メモリの割り当てに失敗しました!\n" );
終了（-1）;
        } 
 
        (*root)->データ = キー;
        (*root)->left_child = (*root)->right_child = NULL;
    }それ以外  if (キー < (*ルート)->データ){
        (*root)->left_child = avl_add(&((*root)->left_child), キー);
 //balance_tree(ルート);  
    }それ以外  if (キー > (*ルート)->データ){
        (*root)->right_child = avl_add(&((*root)->right_child), キー);
 //balance_tree(ルート);  
    }それ以外{
        printf( "%d のコピーに失敗しました!\n" , key);
終了（-1）;
    } 
 
 *rootを返します。
 } 
 
 AvlNode *avl_print(AvlNode *ノード){
 if (node == NULL)はNULLを返します。 
 
    printf( "%d->" , ノード->データ); 
 
    avl_print(ノード->left_child);
    avl_print(ノード->right_child);
ノードを返します。
 } 
 
 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(ルート);
    printf( "\n" ); 
 
    バランスツリー(&root);
    printf( "バイナリツリーを印刷\n" );
    avl_print(ルート);
    printf( "\n" );
 0を返します。
 }

ストレッチツリーを見てみましょう！

スプレイツリー（1985）

スプレーツリーの基本原理：

例

lighttpd-1.4.31.tar.gzからいくつかのコードを抽出して説明しました

具体的なコード練習を見たい方は、以下の場所で視聴できます。

私のコード構造:

コードセクション

/*~ splaytree.h~*/  
 typedef 構造体 tree_node{
    構造体 tree_node *左、*右;
    int key; /* キーワード */  
    int size; /* ノード数 */  
    void *データ;
 } splay_tree;
 /*今はこの2つのメソッドだけを書いています*/  
 splay_tree * splaytree_insert(splay_tree *t, int キー、void *データ);
 splay_tree * splaytree_splay(splay_tree *t, int キー);
 #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キー、 void *データ){
    splay_tree *新規; 
 
 t != NULLの場合{
        t = splaytree_splay(t, キー);
 if (compare(key, t->key) == 0){ /* ノードはすでに存在します */  
 tを返します。
        }
    }
新しい= (splay_tree *) malloc ( sizeof (splay_tree));
    assert(新しい);
 t == NULLの場合{
 new- >left = new- >right = NULL;
    }それ以外  （キー、t->キー）<0を比較する場合
new- >left = t->left;
新しい->right = t;
        t->左 = NULL;
        t->size = 1 + node_size(t->right);
    }それ以外{
 new- >right = t->right;
新しい- >left = t;
        t->右 = NULL;
        t->size = 1 + node_size(t->left);
    }
新しい->key = key;
新しい- >data = データ;
 new- >size = 1 + node_size( new- >left) + node_size( new- >right);
戻る 新しい;
 }
 splay_tree * splaytree_splay(splay_tree *t, intキー){
    splay_tree N, *l, *r, *child; /* 一時変数は *t を組み立てるために使用されます */  
 int cmp、l_size、r_size;
 t == NULL の場合はtを返します。
    N.左 = N.右 = NULL;
    l = r = &N;
    l_size = r_size = 0;
のために（;;） {
        cmp = compare(キー、t->キー); 
 
 (cmp < 0)の場合{
 if (t->left == NULL) break ;
比較(キー、t->left->key) < 0) {
                child = t->left; /* 右に回転 */  
                t->左 = 子->右;
                子->右 = t;
                t->size = 1 + node_size(t->left) + node_size(t->right);
                t = 子供;
 if (t->left == NULL) break ;
            }
            r->left = t; /* 右チェーン */  
            r = t;
            t = t->左;
            r_size += 1 + node_size(r->right);
        }それ以外  (cmp > 0)の場合{
 if (t->right == NULL) break ; 
 
比較(キー、t->right->key) > 0) {
                子 = t->right;
                t->右 = 子->左;
                子->左 = t;
                t->size = 1 + node_size(t->left) + node_size(t->right);
                t = 子供;
 if (t->right == NULL) break ;
            }
            l->右 = t;
            t = 0;
            t = t->右;
            l_size += 1 + node_size(l->left);
        }それ以外{
壊す;
        }
    }
    l_size += node_size(t->left);
    r_size += node_size(t->right);
    t->サイズ = 1 + l_size + r_size; 
 
    l->右 = r->左 = NULL; 
 
 /* サイズデータをチェック */  
 /*右の子の左のノードはカウントされません*/  
 ( child = N.right; child != NULL; child = child->right){
        子->サイズ = l_size;
        l_size -= 1 + node_size(child->left);
    }
 ( child = N.left; child != NULL; child = child->left){
        子->サイズ = r_size;
 r_size -= 1 +node_size(child->right);
    }
 /* アセンブリデータ */  
    l->右 = t->左;
    r->左 = t->右;
    t->左 = 北右;
    t->右 = N.左;
 tを返します。
 }

上記のコードを見ると、誰もが混乱するのではないでしょうか?

詳しく説明しましょう。

>> コアアルゴリズム splaytree_splay() メソッドに注目しましょう。

この if が意味を成すのであれば、他の else if も理解しやすくなります。

 (cmp < 0)の場合{
 if (t->left == NULL) break ; 
 
 （キー、t->left->key）<0を比較する場合
                child = t->left; /* 右に回転 */  
                t->左 = 子->右;
                子->右 = t;
                t->size = 1 + node_size(t->left) + node_size(t->right);
                t = 子供; 
 
 if (t->left == NULL) break ;
            }
            r->left = t; /* 右チェーン */  
            r = t;
            t = t->左;
            r_size += 1 + node_size(r->right);
        }

これは右利きのプロセスです。

子 = t->左

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

最後に: t = 子

これは右連鎖プロセスです。

r->左 = t;r=t;

t = t->左

3>メイン.c

 # <stdio.h>をインクルードする
＃含む  「splaytree.h」  
 splay_tree * splaytree_print(splay_tree *t){
 （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 *ルート;
    ルート = NULL;
    整数データ1 = 1000;
    ルート = splaytree_insert(ルート、20、&data1);
    整数データ2 = 200;
    ルート = splaytree_insert(ルート、5、&data2);
    整数データ3 = 300;
    ルート = splaytree_insert(ルート、3、&data3);
    整数データ4 = 100;
    ルート = splaytree_insert(ルート、10、&data4);
    printf( "結果を印刷*************\n" );
    splaytree_print(ルート); 
 
 
 //ここにはデータクエリプロセスがあるはずですが、記述しませんでした。呼び出すときは、splay メソッドを呼び出すことに注意してください。  
 //すると、ホット データが自然に最上位に表示されます。  
    printf( "クエリメソッドでこのストレッチ関数を呼び出した後、結果を出力します **************\n" );
    ルート = splaytree_splay(ルート、3);
    splaytree_print(ルート);
 0を返します。
 }