プロが教えるわが家の防犯対策術!

二分木の高さについて

このカテゴリでいいのか迷ったのですが。。。


1)、葉を含めて節点の総数がNであるような二分木の高さの範囲、というのはどういったのものなのでしょうか?


また逆に2)、高さhの二分木のもつ要素の最大と最小はいくつなのでしょうか?

導き方も含めてお答えいただけると助かります。


ちなみに1)の自分の答えは完全二分木のときはlogn、最悪にバランスが取れていない時がnです。

このQ&Aに関連する最新のQ&A

A 回答 (2件)

完全2分木のときは


s = 1 + 2^1 + 2^2 + + 2^h =(2^(h+1)-1)/(2-1)= 2^(h+1)-1

h + 1 = log( s + 1 )
h = log( s + 1 ) - 1
log は 2 の対数

もっともアンバランスのときは

s = h + 1

h = s - 1

でどうでしょうかね
高さの定義にもよるでしょうね
    • good
    • 0

>1)の自分の答えは完全二分木のときはlogn、最悪にバランスが取れていない時がnです。



だとすると、ノードの数が2個(完全二分木の場合もバランスが最悪の場合も同じ形)のとき、
おかしなことになりませんか?
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q二分探索木のheight(高さ?)を見つけるアルゴリズム

Binary Search Tree(=二分探索木)のheight(高さ?)を見つけるメソッドを作りたいのですが、
そのアルゴリズムが頭にうまく浮かびません。

まず思いついたのは一つ一つのNode(=ノード)をそれぞれのLeaf(=リーフ、葉?)まで辿っていって
それらのheightを全部記憶させておいて後で比較するという…最も原始的な方法です。
しかし、Treeの大きさも未知なので用意する変数の数も未知になって
どう考えても不適当でしょう(当たり前か(^^ゞ)。
Recursion(=再帰)を使えばいいのでしょうか?
そうだとしてもどうすればいいのか…。
アルゴリズムがパッと浮かぶ方、どうか教えて下さい。

Aベストアンサー

再帰を使うとすれば、二分木ですから、直下の二つだけ比較すれば良いです。
大きい方を採って、自分自身の分1をプラスして上に返したら、上は上で判断してくれます。

Qマージソートの計算量について-O(n*logn)

マージソートの計算量はO(n*logn)ですが、なぜそうなのかが理解出来ません。要素数が2, 4, 8, 16, 32, 64...と増加すると二分割するのにかかる時間は1, 2, 3, 4, 5, 6..となり、n=2^x, x=lognとなるところまでは理解出来ました。しかし更にnをかける必要があるのはどうしてでしょうか。要素数が1になるまで分割した後に、小さい順番に比較しながら統合して行く作業があり、これにも当然ランニングタイムがかかるのはわかりますがなぜこの要素の比較コスト?が*nなのでしょうか。
またウェブで調べると、他にもT(n)=2T(2/n)+O(n)という別の説明もあり、こちらも理解出来ません。この説明は上の説明とはまた別の角度から説明しているものなのでしょうか。わかる人がいたら教えて下さい。

Aベストアンサー

ソートの計算量を議論するときは、通常「比較回数」を考えます。

(正確には、全ての計算の手間を数えあげる必要がありますが、通常
・計算処理の中で「比較回数」が最も多くなる
・計算量(オーダー)では次数の低い項は無視できる
ので、比較回数以外は考える必要がなくなります)

ですので、マージソートの計算量を考える場合、「分割にかかる時間」ではなく、「(比較しながら行う)分割した部分列を統合していくのにかかる時間」だけを考えます。


で、マージソートにおいて分割した部分列を統合するのにかかる時間ですが、
たとえば、16の要素をマージソートする場合を例にあげると、

・要素数が1の部分列を要素数が2の部分列に統合する時の比較回数は1回です。要素数が2の部分列は全部で8個あるので、比較回数は8回。

・要素数が2の部分列を要素数が4の部分列に統合する時の比較回数は3回です。要素数が4の部分列は全部で4個あるので、比較回数は12回。

・要素数が4の部分列を要素数が8の部分列に統合する時の比較回数は7回です。要素数が8の部分列は全部で2個あるので、比較回数は14回。

・要素数が8の部分列を要素数が16の列に統合する時の比較回数は15回です。要素数が16の列は全部で1個あるので、比較回数は15回。

以上合計すると、比較回数8+12+14+15=49回で64要素のマージソートができるわけです。

この「比較回数」を「要素数n」の式で表現するわけですが、
個々の部分列の統合時の比較回数は、要素数n、分割数kとすると、n-k回になりますから、n=2^x (x = log n) とすると、
総比較回数=Σ(k=0~x-1) (n-2^k) = n x - n + 1 = n log n - n + 1
になります。

計算量(オーダー)の議論では、次数の低い項は無視しますから、
O(n log n - n + 1) = O(n log n) になります。

ソートの計算量を議論するときは、通常「比較回数」を考えます。

(正確には、全ての計算の手間を数えあげる必要がありますが、通常
・計算処理の中で「比較回数」が最も多くなる
・計算量(オーダー)では次数の低い項は無視できる
ので、比較回数以外は考える必要がなくなります)

ですので、マージソートの計算量を考える場合、「分割にかかる時間」ではなく、「(比較しながら行う)分割した部分列を統合していくのにかかる時間」だけを考えます。


で、マージソートにおいて分割した部分列を統合する...続きを読む

Q構造体とクラスの違い

お世話になります。

先日、C(C++もかな?)のベテランのプログラマの方が「構造体とクラスはまったく違うものだ」ときっぱり言い切っていらっしゃいました。私は、構造体にメソッドが加わったものがクラスだ、くらいな認識で、まったく違うものというよりはかなり近しい概念だと思っていたので少々驚いた次第です。

疑問が残りましたので、インターネットでいろいろ検索してみたのですが、おしなべて「構造体とクラスには共通点が多い」と説明されており、どうしても「まったく違うもの」と解釈できる文献を見つけることができませんでした。

果たして「構造体とクラスはまったく違うもの」なのでしょうか?

Aベストアンサー

> オブジェクト指向で大切なのは、プログラム(システム)全体での、各個のクラス
> の役割(機能)と相互機能関係を堅牢に設計すること
> というように解釈してよいでしょうか。また、そういう意味でUMLによる開発が有効
>なのでしょうか。
よく勉強なさっていらっしゃいますね。基本的には、ユーザをよく理解し、正しい文章を起草することが大切ということではないでしょうか。意味不明の文章(仕様書)を書く人が多いと思います。ただし、C++を設計したBjarne Stroustrup氏は、自分はプログラマである、とはっきり立場を表明されているようです(分析と設計、あるいは、度重なる打ち合わせだけではプログラムは完成しません)。

> 自分はJavaからプログラムに入った人間なのですが、
この意味がよく分かりません。

> 逆にJavaはオブジェクト指向を強制する言語ということになるでしょうか。
Stroustrup氏は、SmallTalkやJavaをこのように見ている節があります。
なお、同氏は、Javaは開発者だけではなく、マネージャなどの支持を取り付けようとした、という認識を示しているようです。

> ここでいう「型」の安全性とは、「その型のメンバへの不正アクセス発生の可
> 能性の有無」みたいなことでしょうか。
「型」の安全性を保障するには、ある時点で「型」、および、「型」と「型」の間の関係をチェックする必要があります。このチェックは実行時ではなく、コンパイル時に行うのが理想です。Stroustrup氏は、このような方針を打ち出しました。ちなみに、Cも先行するBなどより「型」を重視する言語です。どのような型がどのようにチェックされるのかを知りたい場合、恐れ入りますが、OSSなどの、たとえば、SQLiteなどを無料のVC++ Express Edition(VCEE)などでビルドしてみてください。VCEEはC++標準仕様を忠実に実装しようとしています。あるソースコードをビルドすると200を越える警告が出されます(そのように型チェックが行われる)。

> これもC++においてということでよろしいでしょうか
> (Javaで設計されたクラスはすべてObjectクラスの子クラスだと思うので)
テンプレートやジェネリック、という概念を後日調査してください。C++の考え方は、JavaやC#などに浸透しています(Stroustrup氏はこの自体をすでに予言していました)。

参考になれば幸いです。

> オブジェクト指向で大切なのは、プログラム(システム)全体での、各個のクラス
> の役割(機能)と相互機能関係を堅牢に設計すること
> というように解釈してよいでしょうか。また、そういう意味でUMLによる開発が有効
>なのでしょうか。
よく勉強なさっていらっしゃいますね。基本的には、ユーザをよく理解し、正しい文章を起草することが大切ということではないでしょうか。意味不明の文章(仕様書)を書く人が多いと思います。ただし、C++を設計したBjarne Stroustrup氏は、自分はプログラマである、と...続きを読む

Qシンボルが見つかりませんというエラーが理解できません。

以下のようなじゃんけんゲームのプログラムを書いたのですが、「シンボルが見つかりません。」というエラーが表示されるのですが、エラーの意味が理解できず、解決できません。どこが間違っているのか教えていただけませんか。

import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import java.io.File;

public class janken extends Applet
implements Runnable, ActionListener {
private static final int EXTERNAL_BUFFER_SIZE = 128000;

Image image[] = new Image[3];
Thread t;
int index1 = 0;
int index2 = 0;
String msg = "";
String msg1 = "";

boolean state = false;
Button b1 = new Button("ぐー");
Button b2 = new Button("ちょき");
Button b3 = new Button("ぱー");

public void init(){
for(int i = 0; i<=2; i++){
img[i] = getImage(getDocumentBase(),"hanabi" + (i+1) + ".JPG");
}
add(b1);
add(b2);
add(b3);
b1.addActionListener(this);
b2.addActionListener(this);
b3.addActionListener(this);
msg1 = "結果は・・";

}

public void paint(Graphics g){
g.drawImage(img[index1],350,30,this);
g.drawImage(img[index2],695,30,this);
g.drawString("コンピューター",420,300);
g.drawString("あなた",800,300);
g.drawString(msg,630,320);
g.drawString(msg1,550,320);
}

public void start(){
state = true;
t = new Thread(this);
t.start();

}

public void run(){
while(state){
index1++;
if(index1 == 3){
index1 = 0;
}
index2++;
if(index2 == 3){
index2 = 0;
}
repaint();
try {
Thread.sleep(60);
}catch(InterruptedException e) { }
}
}

public void actionPerformed(ActionEvent e){
if(state == false) {
start();
return;

}
state = false;
if(e.getSource() == b1) {
msg = "ぐー";
index2 = 0;
}

else if(e.getSource() == b2){
msg = "ちょき";
index2 = 1;
}

else if(e.getSource() == b3){
msg = "ぱー";
index2 = 2;
}
check();
repaint();
}

public void check() {
if(index1 == index2) msg ="あいこ";


else if (index1 == 0) {
if(index2 == 2) msg="あなたの勝ち";
else msg ="あなたの負け";
}

else if(index1 == 1) {
if(index2 == 0) msg="あなたの勝ち";
else msg="あなたの負け";
}

else if(index1 == 2) {
if(index2 == 1) msg="あなたの勝ち";
else msg="あなたの負け";
}

}
}

以下のようなじゃんけんゲームのプログラムを書いたのですが、「シンボルが見つかりません。」というエラーが表示されるのですが、エラーの意味が理解できず、解決できません。どこが間違っているのか教えていただけませんか。

import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
import java.io.File;

public class janken extends Applet
implements Runnable, ActionListener {
private static final int EXTERNAL_BUFFER_SIZE = 128000;

Image image[] = new Imag...続きを読む

Aベストアンサー

「シンボルを見つけられません。」というエラーの下に何か表示がありませんでしたか?そこにヒントがあると考えられます。
シンボルを見つけられませんといエラーが表示される主な理由は4つあります。
(1)クラス、メソッド、変数などの綴りミスや定義していない変数を使用している可能性がある。
(2)コンストラクタを呼び出すときに、newを忘れている可能性がある。(3)公開されていないメンバーを呼び出している可能性がある。
(4)必要なimport文を記述し忘れている可能性がある。
ここでのあなたのエラーは(1)番ではないでしょうか?上記ではimageとなっている変数がimgになっていますね。
これはエラー表示をよく見ることで意外と簡単に解決できるのです。
ゆっくり丁寧にエラー表示を見るように心がけることが大事ですよ。

QO(n log n)について2

n log nはつまり10の(nのn乗)乗という事ですね?
なにやらこちらの参考文献にはNの2乗よりn log nの方が効率が良いとあるのですが計算するとn log nのほうが数値が高くなるのですが、これはどういうことでしょう?

Aベストアンサー

> n log nはつまり10の(nのn乗)乗という事ですね?
違う。logは対数だから、何乗かしたらnになる数を求める。
すなわち
 2^x=n
となるとき
 x=log n
だ。
なお、演算量の話をするときはlogの底は2を使うことが多い。
# オーダーの話では底が何でも結局は同じだが

具体的な数字で話をすると、n=1024のとき、log n = 10で、
 n log n = 10240
だ。
 n^2 = 1048576
なので、100倍以上小さいことが分かるだろう。

Q大学院合格後の挨拶メール

現在大学4年生で大学院は他大学に行くことに決まったものです。
今年の8月の終わりに他大学の大学院(理系)の合格通知を受け取けとったのですがその後家に帰る暇もないほど研究が忙しくなり他大学の大学院の教授に挨拶のメールを送ることを忘れていました・・・・
書いてみたのですが自信がないので添削お願いします。

『YY大学YY研究室
教授 CC先生

秋冷の候、ますますご清栄のこととお喜び申し上げます。
M大学のMと申します。

先日の大学院入試では大変お世話になりました。おかげさまで、無事合格通知を頂くことが出来ました。お礼かたがたご報告申し上げます。
すぐに報告すべきでしたが研究が忙しくこのような時期となってしまいました。
大変遅くなり誠に申し訳ありません。
改めてご挨拶に伺いたいと存じますが、ご都合はいかがでしょうか?
お知らせいただければ幸いです。お忙しいところ申し訳ありませんがよろしくお願いします。』

Aベストアンサー

回答者1さんと同様に受け取られた教授はあまり良い感じはしないと思います。

まず、添削ですが。

教授 CC先生
→ CC教授
   教授は所属ではなく肩書きです。

M大学のMと申します。
→ M大学のMです。
   入試前の挨拶や面接ですでに面識があるのだから「申します」はおかしい。

改めてご挨拶に伺いたいと存じますが、ご都合はいかがでしょうか?
 → 改めてご挨拶に伺いたいと存じます。○月×旬ころのご都合はいかがでしょうか?
    いつの都合を聞かれているのかわからない。


他は回答者1さんと同じです。


ですが!!
メールではなく電話すべきです。
メールは事務的な内容のやりとりにはとても便利なコミュニケーション手段ですが
お礼を述べるなどの格はかなり低いです。

直接会う>手紙>電話>メール でしょう

ですが、手紙は現代では一方向的な挨拶だと思います。
今回は直接伺う相談もしたいわけですから、電話が良いと思います。

Qパイプライン方式での処理時間の求め方

応用情報の問題で、わからない所があります。

パイプラインの深さをD 、パイプラインのピッチをP 秒とすると、I 個の命令をパイプラインで実行するのに要する時間を表す式はどれか。
ここで、パイプラインの各ステージは1ピッチで処理されるものとし、パイプラインハザードについては、考慮しなくてよい。

 ア  (I +D )×P  イ  (I +D -1)×P
 ウ  (I ×D )+P  エ  (I ×D -1)+P

正解は「イ」なのですが、お恥ずかしながら全く腑に落ちません。

私の理解とそれによって導き出される式は以下のようになっています。
どこでまちがっているのか、教えていただけませんでしょうか。

◆私の理解
 パイプラインの深さをD:命令の中のステージ数はD個
 パイプラインのピッチをP 秒:1ピッチP秒かかる
 パイプラインの各ステージは1ピッチで処理:各ステージの処理はP秒かかる
 I 個の命令:命令がI個ある

◆式
 所用時間= I × (D × P)

D×Pで命令内全ステージにかかる時間を求めたつもりです。
それに命令数をかけています。

すみません、よろしくお願いいたします。

応用情報の問題で、わからない所があります。

パイプラインの深さをD 、パイプラインのピッチをP 秒とすると、I 個の命令をパイプラインで実行するのに要する時間を表す式はどれか。
ここで、パイプラインの各ステージは1ピッチで処理されるものとし、パイプラインハザードについては、考慮しなくてよい。

 ア  (I +D )×P  イ  (I +D -1)×P
 ウ  (I ×D )+P  エ  (I ×D -1)+P

正解は「イ」なのですが、お恥ずかしながら全く腑に落ちません。

私の理解とそれによって導き出される式は以下のようになって...続きを読む

Aベストアンサー

命令の個数を7、パイプラインの深さを4、パイプラインのピッチを1秒とする。

この場合、1つの命令がパイプラインを通り抜けるには4秒かかる。

そして、それぞれの命令は、1秒づつズレながら順にパイプラインに入っていく。

図にすると、以下のようになる。

 深さ4
←──→
□□□□______ 1番目のパイプに入った命令は抜けるまで4秒かかる
_□□□□_____ 2番目の命令が入るのは1ピッチ経過後。つまり1秒後
__□□□□____ 3番目の命令が入るのは2ピッチ経過後。つまり2秒後
___□□□□___ 4番目の命令が入るのは3ピッチ経過後。つまり3秒後
____□□□□__ 5番目の命令が入るのは4ピッチ経過後。つまり4秒後
_____□□□□_ 6番目の命令が入るのは5ピッチ経過後。つまり5秒後
______□□□□ 7番目の命令が入るのは6ピッチ経過後。つまり6秒後
1 2 3 4 5 67 89 10 ←(7+4-1)×1=10

最後の命令がパイプラインに入るのは「命令の個数-1ピッチ後」であり、その命令がパイプラインを通過し終わるのは、パイプラインの深さだけかかる。

つまり、最後の命令がパイプラインを通り抜け終わるのは「命令の個数-1+パイプラインの深さ」に、1ピッチの秒数を掛けた秒数が経過した時である。

「最後の命令がパイプラインを通り抜け終わる秒数」と言うのは「全部の命令を実行するのに要する時間」そのものである。

「(命令の個数-1+パイプラインの深さ)×1ピッチの秒数」を意味する式は「イ  (I +D -1)×P」である。

命令の個数を7、パイプラインの深さを4、パイプラインのピッチを1秒とする。

この場合、1つの命令がパイプラインを通り抜けるには4秒かかる。

そして、それぞれの命令は、1秒づつズレながら順にパイプラインに入っていく。

図にすると、以下のようになる。

 深さ4
←──→
□□□□______ 1番目のパイプに入った命令は抜けるまで4秒かかる
_□□□□_____ 2番目の命令が入るのは1ピッチ経過後。つまり1秒後
__□□□□____ 3番目の命令が入るのは2ピッチ経過後。つまり2秒後
___□□□□...続きを読む

QJavaで改行などが出来ないのです。

 Java の事で質問です。 
 

 System.out.println("このようにしても\n");

 改行できません。
 
 このようにしても\n   

 と表示されてしまいます。どうしてでしょう。ちなみにOSはMacOS9.1です。なにか関係があるのでしょうか?

Aベストアンサー

> class amigo{
> public static void main(String args[]) {
> System.out.print("aaaaaaaa");
> System.getProperty("line.separator");
> System.out.print("bbbbbbbb");
> }
> }
> のような使い方でしょうか?

String line_sep = System.getProperty("line.separator");
System.out.println("あいうえお" + line_sep + "かきくけこ");

こうです。

QJSP + ラジオボタン

JSP+Servlet+Beanで作ってます。
JBuilder5を使ってます。

JSPはラジオボタン、テキスト、ボタン等があります。
<INPUT TYPE = "radio" NAME = "r1" VALUE = "ins">A
<INPUT TYPE = "radio" NAME = "r1" VALUE = "upd">B
<INPUT TYPE = "radio" NAME = "r1" VALUE = "del">C

としています。
たとえば、Bを選択時、ボタンクリックで
Servletにリクエストを送信しますが、
Servletから再びJSPを呼び出し、画面を
表示するとき、ラジオボタンはBを選択
させたいのですが、どうしたらいいですか?
FormタグのCHECKEDというオプションを
どのように使えばいいのか教えていただきたいのですが。


テキストには、Beanでsetメソッド、
JSPでは、<jsp:getProperty・・・>を使って
セットできているんですが、ラジオボタンも
同様ですか?
@@@・・・JSPのタグを勉強しないといけないです。
@@@勉強不足です。

JSP+Servlet+Beanで作ってます。
JBuilder5を使ってます。

JSPはラジオボタン、テキスト、ボタン等があります。
<INPUT TYPE = "radio" NAME = "r1" VALUE = "ins">A
<INPUT TYPE = "radio" NAME = "r1" VALUE = "upd">B
<INPUT TYPE = "radio" NAME = "r1" VALUE = "del">C

としています。
たとえば、Bを選択時、ボタンクリックで
Servletにリクエストを送信しますが、
Servletから再びJSPを呼び出し、画面を
表示するとき、ラジオボタンはBを選択
させたいの...続きを読む

Aベストアンサー

<% %>のなかに
<jsp:getProperty name="wk" property="aaa" />
のようなJSPタグを使用することはできません。
これはエラーになります。

wkがBeanのインスタンス名、aaaがプロパティ名なので
<% if(wk.getAaa()==1){ out.print("checked");} %>

でよいと思いますが・・・

Qe^(-x^2)の積分

e^(-x^2)の積分はどうやったらよいのでしょうか?
どなたか分かる方、よろしくお願いします。

eは自然対数の底でe^(-x^2)=exp{-x^2}

Aベストアンサー

ガウス分布に使いますね。
やりかたですね。一般的なものを参考程度までに、

xy座標の第一象限で原点を通る一辺aの正方形
と正方形に接する半径aの(1/4)円とr半径√2aを考えるんですね。
正方形の領域□でe^-x^2 をx方向に積分すると、
∫[0→a]e^-x^2dx
正方形の領域だからe^-y^2 をy方向に積分しても
同じ値になりますね。だから
∫[0→a]e^-x^2dx=∫[0→a]e^-y^2dy
ということは、x,yは独立に考えられるので、
∫[0→a]e^-(x^2+y^2)dxdy
={∫[0→a]e^-x^2dx}^2
という関係が出ますね。
だから、e^-(x^2)を積分する代わりにe^-(x^2+y^2)を積分してその√を取れば解が得られるという論法を利用するんですね。
四角形の領域で
I=∫[x,y:0→a]e^-(x^2+y^2)dxdy
を積分するにはちょっとなんで、四角形に接する大小の円で挟み撃ちを考えるんですね。
半径aの(1/4)円では、
極座標変換して、(x^2+y^2)=r^2, dxdy=rdrdθ
=∫[0→a]e^-(r^2)dr∫[0→π/2]dθ
=(1/2)(1-e^-a^2)(π/2)=(π/4)(1-e^-a^2)
同様に、半径√2aの(1/4)円では、
=(π/4){1-e^-(2a^2)}
だから、
x:0→a
√{(π/4)(1-e^-a^2)}<∫[0→a]e^-(x^2)dx
<√{(π/4){1-e^-(2a^2)}}
が回答ですね。これ以上は数値表を参照ですね。
a→∞ であれば、
∫[0→∞]e^-(x^2)dx=(√π)/2
が回答になりますね。
広域積分でも検索すれば参考になるかも。

ガウス分布に使いますね。
やりかたですね。一般的なものを参考程度までに、

xy座標の第一象限で原点を通る一辺aの正方形
と正方形に接する半径aの(1/4)円とr半径√2aを考えるんですね。
正方形の領域□でe^-x^2 をx方向に積分すると、
∫[0→a]e^-x^2dx
正方形の領域だからe^-y^2 をy方向に積分しても
同じ値になりますね。だから
∫[0→a]e^-x^2dx=∫[0→a]e^-y^2dy
ということは、x,yは独立に考えられるので、
∫[0→a]e^-(x^2+y^2)dxdy
={∫[0→a]e^-x^2dx}^2
という関係が出ますね。
...続きを読む


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング