- ベストアンサー
二分木の高さについて
- みんなの回答 （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 でどうでしょうかね 高さの定義にもよるでしょうね
その他の回答 (1)
- asuncion
- ベストアンサー率33% (2126/6286)
＞１）の自分の答えは完全二分木のときはlogn、最悪にバランスが取れていない時がnです。 だとすると、ノードの数が２個（完全二分木の場合もバランスが最悪の場合も同じ形）のとき、 おかしなことになりませんか？
関連するQ&A
- 二分木探索でN番目の要素を探索するには
二分木探索で特定の要素の有無を調べる関数は作れたのですが、Ｎ番目に小さい要素を見つける方法が思い浮かびません。 二分木探索でN番目に小さい(昇順でＮ番目)の要素を探索するにはどのような手法があるのか教えて頂けないでしょうか？ よろしくお願い致します。
- ベストアンサー
- C・C++・C#
- アルゴリズム:2分探索の時間計算量
アルゴリズムの参考書を読んでいて疑問に思ったんですが、教えてください。 /* ２分探索 */ #include <stdio.h> /*--- 要素数nの配列aからkeyと一致する要素を２分探索 ---*/ int bin_search(const int a[], int n, int key) { int pl = 0;/* 探索範囲先頭の添字【1】 */ int pr = n-1;/* 〃 末尾の添字 【2】*/ int pc; /* 〃 中央の添字 */ do { pc = (pl + pr) / 2;/*【3】*/ if (a[pc] == key) /* 探索成功【4】 */ return (pc);/*【5】*/ else if (a[pc] < key)/*【6】*/ pl = pc + 1;/*【7】*/ else /*【8】*/ pr = pc - 1;/*【9】*/ } while (pl <= pr);/*【10】*/ return (-1);/* 探索失敗【11】 */ } のプログラムがありますが、【1】から【11】までの 実行回数と計算量は次のようになるそうですが、 実行回数 計算量 【1】 1 O(1) 【2】 1 O(1) 【3】 logn O(logn) 【4】 logn O(logn) 【5】 1 O(1) 【6】 logn O(logn) 【7】 logn O(logn) 【8】 logn O(logn) 【9】 logn O(logn) 【10】 logn O(logn) 【11】 1 O(1) なぜ【3】や【4】がlognになるんでしょうか？ 詳しく教えてください。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- コスモ
1)天体をばらまく領域を決める 2)ばらまく天体の最大の明るさと最小の明るさを決める 3)ある明るさの範囲に入る天体の個数をlogN-logSを関係から求める 4) logN-logS関係は平均値を与えるため、この値を平均値とするＰoisson統計に従う乱数から実際にばらまく天体の個数を決める 5)この天体を領域内に一様にばらまく（一様乱数を用いる。） 6)３～５の操作を最大の明るさから最小の明るさまで繰り返し行う。 という手順でＣ言語のプログラムを使って宇宙を表現したいのですが、どのようにプログラムすればよいでしょか？手がかりでいいので教えてください。できれば、参考URLがあるとありがたいです。お願いします。
- ベストアンサー
- C・C++・C#
- アルゴリズム(2分探索木)の問題について
２分探索木のアルゴリズムに関する問題について質問させていただきます。 [問題] 集合Sに対する2文探索木とは、ラベルつきの2分木で、 その頂点vにはSのある要素l(v)がラベルとしてつけられている。 l(v)は次の性質を満たす。 １．vの左部分木の頂点uに対して l(u) < l(v) 2．vの右部分木の頂点uに対して l(u) > l(v) 3．Sの任意の要素aに対して l(v) = a となる頂点vはちょうどひとつある。 図はキーワード集合{begin,else,end,if,then}をあらわす2分探索木の例である。 いま、集合Sを表す2分探索木と要素aが与えられているときa∈Sならば"はい"、 そうでなければ"いいえ"を出力するアルゴリズムを考える。 このアルゴリズムは、木の根rについて一回だけ再帰手続きSEARCH(a,r)を呼び出せばよい。 ただし、SEARCH(a,v)はvを根とする部分木中に要素aが含まれているかを判定する。 含まれているときに値"はい"を、そうでなければ値"いいえ"を返す。 ・アルゴリズム procedure SEARCH(a,v): if a = l(v) then return "はい" else if a < l(v) then if vが左の子wを持つ then return SEARCH( ア ) else return "いいえ" else イ 以下の問題に答えよ。 (1) 上のアルゴリズムのア,イを埋めよ。 (2) 上のアルゴリズムを参考にして、集合Sからのデータの削除DELETE(a,S)を考える。 削除すべき要素aが頂点vのラベルであったとする。そのとき次の3つの場合について、行うべき操作を記述せよ。 (i) 頂点vが葉である (ii) 頂点vの子が1個ある (iii) 頂点vの子が2個ある 以上です。 設問(1)は解けました。 答えは ア: a,w イ: a > l(v) then if vが右の子wを持つ then return SEARCH(a,w) else return "いいえ" になるのではないかと思います。 設問(2)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、 参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。 長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。
- ベストアンサー
- その他（プログラミング・開発）
- 探索木の問題について
探索木について。 探索木において、探索効率を高めるため（探索経路を短くするため）、子の数を最大ｍ個までとするｍ分探索木を考える。この木の探索についての計算量は、どのように考えれば良いですか。 説明してください。 という問題なのですが 画像のA,Bのタイプのどちらで考えればいいのかわかりません そこで、どちらのタイプで考えればいいのか あわよくば、問題についても答えを教えてください よろしくおねがいします
- 締切済み
- 情報工学
- c言語で2分探索木のを2分木に変えたい
2分木のプログラムを書いているのですが、ある数列を2分木にしたいのです。 2分探索木のプログラムを参考に書いていて、その一部が typedef int BSTREE_K_TYPE; typedef int BSTREE_V_TYPE; struct bsnode { BSTREE_K_TYPE key; BSTREE_V_TYPE value; struct bsnode *left; struct bsnode *right; }; typedef struct bsnode BSTREE_NODE; int gShortFormat = 1; void error(char *msg){ fflush(stdout); fprintf(stderr, "%s\n", msg); exit(1); } BSTREE_NODE *createNode(BSTREE_K_TYPE x){ BSTREE_NODE *new; new = malloc(sizeof(BSTREE_NODE)); if(new == NULL) error("createNode: メモがありません"); new->key = x; new->value = 0; new->left = NULL; new->right = NULL; return new; } BSTREE_NODE *insertNode(BSTREE_NODE *p, BSTREE_K_TYPE x){ if (p == NULL){ } else if (p->key == x){ error("insertNode: 指定キーのノードが含まれています"); } else if (p->key > x){ p->left = insertNode(p->left, x); } else { p->right = insertNode(p->right, x); } return p; } BSTREE_NODE *inputBSTree(BSTREE_NODE *btree, char *str[], int len, int *end){ BSTREE_K_TYPE x; int i, n = 0; for(i = 0; i < len; i++){ if(!strcmp(str[i], "--")) break; x = atoi(str[i]); if(btree == NULL) btree = createNode(x); else btree = insertNode(btree, x); n++; } *end = n; return btree; } このinsertNodeのifの条件を変えればいいのかと思い、いろいろ試してみたのですが、 左部分木には左側にしか葉がなく、右部分木には右にしか葉がないようなものしかできませんでした もう何時間も悩んだのですが自分の知識では手づまりです どうかよろしくお願いします。
- ベストアンサー
- C・C++・C#
- 重積分について
Dが()内の領域の時、以下の重積分を求めよ。 ∬(y-x)^2√(x+y)dxdy (x≧0、ｙ≧0、x+y≦1) 以下が私が解いた結果です。 y-x=s,x+y=t と置き換える。 (y=s+t/2,x=t-s/2) これにより、下記のように書き換えが可能である。 ∬(y-x)^2√(x+y)dxdy＝∬s^2√(ｔ)dsdt 範囲条件より、0≦x+y≦1より、0≦ｔ≦1 ｓの範囲について考えると ・ｙが最大且つｘが最小の時→ｓは最大 ・ｙが最小且つｘが最大の時→ｓは最小 これにより、ｓについての範囲は -1≦ｓ≦1 次に変形後のJacobianについて考える。 JΦ(ｓ、ｔ)＝1/2 よって∬(y-x)^2√(x+y)dxdy＝∬s^2√(ｔ)dsdt＝1/2 このような結果になったのですが、間違いや訂正する箇所はありますでしょうか？ あるようでしたら教えてください。
- ベストアンサー
- 数学・算数
- 三角関数の最大最小についての問題
関数の最大値と最小値、およびそのときのθの値を求めよ。ただし0≦θ＜2πとする。 y＝2tan^2θ＋4tanθ＋5 自分の解答) ｔａｎθ＝xとおくと、範囲は-1≦x≦1。 y＝2x^2＋4x＋5 y＝2(x＋1)^2＋3 頂点(-1、3) 軸x＝-1 よって x＝1のとき最大値11 x＝-1のとき最小値3 ここでグラフと範囲から最大値・最小値を出したのですが、 答えでは最大値はなしになっていました。 範囲が間違っているのでしょうか、ご指摘宜しくお願いします。
- ベストアンサー
- 数学・算数
