先週は2分木の操作のプログラミングであったが、今日は入力データを2分木に追加する処理を 説明する。追記すべき場所を末端まで移動しながら探し、追加する処理は、以下の通り。

int key ;
struct Tree* top = NULL ;
struct Tree** tail ;
for( tail = &top ; (*tail) != NULL ; /*none*/ ) {
if ( (*tail)->data == key )
break ;
else if ( (*tail->data > key )
tail = &( (*tail)->left ) ;
else
tail = &( (*tail)->right ) ;
}
if ( (*tail) == NULL )
(*tail) = tcons( key , NULL , NULL ) ;

この処理の動きを説明した後、データが昇順や降順に与えられると、枝が一方向にのみ 成長し、検索処理が O( N ) になってしまい、本来の O( log N ) にならないことを説明する。 このような場合、枝の途中で、繋ぎ換えを行えば枝の深さが減らせることを説明する。 これを全体に施し、最適化を行う方法として、AVL木を紹介する。

このような２分木の欠点としては、１データあたり２ポインタを必要とし、メモリの 利用効率としては悪いことを説明する。

この説明にあたり、32bit = int 、32bit = pointer で 説明をするが、最近のコンピュータであれば、Over 4GB になれば、32bit では不十分で あることを示し、64bit OS などが普及してきたことを関連情報として説明する。 2^64 = 16 * 1024 * 1024 * 1024 * 1024 * 1024 * 1024 = 16 EB( Exa Byte )

これらのメモリの使用効率を改善して、2分木と同様の左右の枝の概念を持つ方法として、 2分ヒープを紹介する。