2分木へのデータの追記

前回の授業で、2分探索木のデータに対する処理を説明したので、今回は木にデータを追加する処理。

struct Tree {
    int data ;
    struct Tree* left ;
    struct Tree* right ;
} ;
struct Tree* tcons( int x, struct Tree*L, struct Tree*R )
{
    struct Tree* ans ;
    ans = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
    if ( ans != NULL ) {
        ans->data  = x ;
        ans->left  = L ;
        ans->right = R ;
    }
    return ans ;
}
struct Tree* top = NULL ;
void insert( int x )
{
    struct Tree** tail = &top ; // 書換えるべき末端ポインタへのポインタ
    while( (*tail) != NULL ) {
        if ( (*tail)->data == x )
            break ; // 同じデータは重複するので、追加処理は行わない
        else if ( (*tail)->data > x )
            tail = &( (*tail)->left ) ; // 左の枝を降りていく
        else
            tail = &( (*tail)->right ) ; // 右の枝を降りていく
    }
    if ( (*tail) == NULL )
        (*tail) = tcons( x , NULL , NULL ) ;
}

単純リストの時は、2重ポインタの混ざった式の部分的に、型を意識する説明をした。今回は、”tail = &( (*tail)->left )“の赤のカッコが省略されたら、青のカッコが省略されたら、どちらが文法エラーかを「演算子の優先順位」の話を交えながら説明する。

不均衡な木の成長

この insert() を使って、

• insert(50); insert(20); insert(70); insert(30); insert(60);を実行した場合と、
• insert(20); insert(30); insert(50); insert(60); insert(70);を実行した場合を考える。

後者は、下図の右の用に一方的に伸びる木構造ができて、高速な検索の恩恵がない。

       50　　　　　　20
　　／　　　＼　　　　　＼
　20　　　　　70　　　　　30
／　＼　　　／　＼　　　　　＼ O(N)
　　　30　60　　　　　　　　　50
　　　　　　　　　　　　　　　　＼
　　　O(log N)　　　　　　　　　　60
　　　　　　　　　　　　　　　　　　＼
　　　　　　　　　　　　　　　　　　　70

これらの問題を解決するため、枝の途中でデータの配置を動かして、左右均衡のとれた構造に書換える方法として、AVL木がある。