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