4 平衡木

4.1 計算量のオーダー

データの数が$N$ 個の場合，サーチの計算回数を考えよう．もっともバランス良く，ツリー 構造ができたとする．その深さを$m$ とすると，

$$\sum_{n=1}^{m-1} 2^{n-1}\leq N=1+2+4+8+\cdots\leq\sum_{n=1}^{m} 2^{n-1}$$ (1)

が成り立つ．これから，

$$2^{m-1}-1 \leq N \leq 2^{m}-1$$ (2)

となる．これから，深さ$m$ は

$$m-1 \leq \log_2(N+1) \leq m$$ (3)

を満たす整数となる．サーチの回数はツリーの深さと同程度であることが直感的に分かる だろう．従って，データ数$N$ が大きい場合，その計算回数(比較回数)は $O(\log_2 N)$ と なることが分かるだろう．

バランスが悪い木(教科書 Fig 6-19右図)の場合の，比較の回数は平均で$N/2$ 回である． 従って，計算量は$O(N)$ となる．

データ量が非常に多い場合，すなわち$N$ が非常に大きい場合，この計算量の差は顕著な 者となる．したがって，バランスの良いツリー構造を作らなくてはならないことが分かるだろう．

4.2 平衡木の作成

4.2.1 AVL木

教科書を使って，説明する．

4.2.2 B木

教科書を使って説明する．

ホームページ: Yamamoto's laboratory
著者: 山本昌志