二分木が平衡か判定する方法

引き続き世界で闘うプログラミング力を鍛える150問』の問題を解いていこう。プログラミング言語は Python を使う。

お題を引用しよう。

二分木が平衡かどうかを調べる関数を実装してください。平衡木とは、どのノードの2つの部分木も、その高さの差が1以下であるような木であると定義します。

順を追って考えていこう。

二分木のデータ構造

Wikipedia にある二分木の定義はこうだ。

計算機科学でいう二分木は、データ構造の1つである。根付き木構造の中で、あるノードが持つ子の数が高々2であるものをいう。典型的には2つの子はそれぞれ「左」「右」と呼ばれる。

この構造を素直にプログラムに直したのが次のコードだ。

@property デコレータを使って leftright という名前で左の子と右の子を表現している。インスタンス化されたタイミングでは、左も右も None になる。

二分木の高さを求める方法

二分木の高さは再帰関数で求めることができる。次の get_height()Node クラスのメソッドだ。

2~3行目の if で、左の子も右の子も存在しない場合は再帰を終了する。言い換えれば、get_height() をコールするインスタンスが節ではなく葉であれば、そこで終了する。

インスタンスが節であれば、その左の子と右の子の高さを取得し、高い方よりさらに1だけ大きい数が、その節の高さになる。

二分木が平衡であることを調べる方法

get_height() が実装されてしまえば、平衡かどうかを調べるメソッドは簡単に書ける。

左の子と右の子の高さを取得し、高さが等しければ平衡で、そうでなければ平衡でいない、ということだ。

ここまでで一つ気づくことがある。is_balanced() をコールすると子ノードの get_height() がコールされることになる。 get_height() はさらに子ノードに対しても get_height() をコールする。したがって、get_height() の計算結果をいちいち計算せず、保存しておくことで高速化できる。このような技術をメモ化と言う。

メモ化した get_height() は次のように書ける。

_height というプライベート変数を導入し、計算済みの高さを保存するようにしている。

全体のプログラム

プログラムの全体像をここに掲載する。

コメントを残す

コメントを投稿するには、以下のいずれかでログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中