ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論 » 2分探索木への追加

2017年10月
« 9月   11月 »
1234567
891011121314
15161718192021
22232425262728
293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

2分探索木への追加

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木がある。