約 89,171 件
https://w.atwiki.jp/kanda_0608/pages/27.html
このwikiの二分探索木に関する練習問題に取り組みました。 二分探索木の構造、各関数の仕様はwikipediaを参考にしました。 課題 整数を保持するノードからなる二分探索木を生成するプログラム作って下さい。指定の値をもつノードを追加するadd, 探索するsearch, 削除するdeleteの3つの関数(メソッド)を作りましょう。 【ソースコード】
https://w.atwiki.jp/nkym_memo/pages/125.html
二分探索木 任意の節xについて、左部分木に含まれる要素は節xよりも小さく、右部分木に含まれる要素は節xよりも大きい attachref 二分探索木の節 typedef struct node{ int data; struct node *left; struct node *right; }NODE; NODE *root = NULL; 二分探索木の探索 NODE *search(int key) 二分探索木を探索する 節へのポインタを返す 見つからない場合、NULLを返す 再帰呼び出しの場合 NODE *search(int key,NODE *p) { if(p == NULL){ return NULL; }else if(key == p- key){ return p; }else if(key p- key){ return (search(key,p- left)); }else{ return (search(key,p- right)); } } ループの場合 NODE *search(int key,NODE *p) { p = root; while(p != NULL){ if(key == p- data)){ return p; }else if(key p- data)){ p = p- left; }else{ p = p- right; } return NULL; } } 二分探索木への挿入 NODE *insert(int key) 二分探索木に要素を挿入する すでに要素が登録されているのなら、何もしないでNULLを返す NODE *insert(int key) { NODE **p,*new; while(*p != NULL){ if(key == (*p)- data){ return NULL; }else if(key (*p)- data)){ p = (*p)- left; }else{ p = (*p)- right; } } if((new = malloc(sizeof(NODE))) == NULL){ fprintf(stderr,"out of memory!\n"); } new- left = NULL; new- right = NULL; new- data = key; *p = new; return new; } サンプルプログラム [[二分探索木サンプルプログラム ./二分探索木サンプルプログラム]] 参考文献 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤 嘉雪,ソフトバンククリエイティブ,1998) Cをさらに理解しながら学ぶデータ構造とアルゴリズム(森本 逞,共立出版,2007) コメント
https://w.atwiki.jp/nkym_memo/pages/126.html
二分探索木サンプルプログラム 初期化としてキー値を連番で10個挿入 オプションで探索キー値をとる すんごい適当 #include stdio.h #include stdlib.h #include unistd.h typedef struct node{ int key; int data; struct node *left; struct node *right; }NODE; NODE *root = NULL; enum{ RAND_min = 0, RAND_max = 1000 }; int Rand(int min,int max) { static int flag; if(!flag){ srand((unsigned int)time(NULL)); flag = 1; } return (max - min + 1) * (float)rand()/RAND_MAX + min; } NODE *insert(int key) { NODE **p,*new; p = root; while(*p != NULL){ if(key == (*p)- key){ return NULL; }else if(key (*p)- key){ p = (*p)- left; }else{ p = (*p)- right; } } if((new = malloc(sizeof(NODE))) == NULL){ fprintf(stderr,"Error Cannot allocate memory"); exit(1); } new- left = NULL; new- right = NULL; new- key = key; new- data = Rand(RAND_min,RAND_max); *p = new; return new; } void init() { int i; NODE *p; for(i = 0;i 10; i++){ if((p = insert(i)) == NULL){ fprintf(stderr,"Error insert"); exit(1); } printf("Node key %d data %d\n",p- key,p- data); } } NODE *search(int key) { NODE *p; p = root; while(p != NULL){ if(key == p- key){ return p; }else if(key p- key){ p = p- left; }else{ p = p- right; } } return NULL; } int main(int argc,char *argv[]) { init(); int key = atoi(argv[1]); fprintf(stdout,"check key %d\n",key); NODE *p; p = search(key); if(p != NULL){ printf("Data found key %d data %d \n",p- key,p- data); }else{ printf("Not found\n"); } return 0; } 参考文献 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤 嘉雪,ソフトバンククリエイティブ,1998) コメント
https://w.atwiki.jp/sevenlives/pages/2511.html
完全二分木? 二分探索木? データ構造 アルゴリズム
https://w.atwiki.jp/nkym_memo/pages/123.html
二分探索法(binary search) 順に整列された配列に対して探索を行う 探索範囲の中央で2分し、中央値に対して大小で探索範囲を縮める struct{ int key; int data; }table[100]; int ndata; int binary_search(int key) { int low = 0; int high = n-1; int middle; while(low = high){ middle = (low + high)/2; if(key == table[middle].key){ return (table[middle].data); }else if(key table[middle].key){ high = middle -1; }else{ low = middle +1; } } return -1; } サンプルプログラム [[二分探索法サンプル ./二分探索法サンプル]] 参考文献 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤嘉雪,ソフトバンククリエイティブ,1998)
https://w.atwiki.jp/vivid_turtle/pages/25.html
中央値という概念は二分探索と相性がすこぶるいい。ここでその性質を応用した例題を記す。 中央値の二分探索 中央値というのは次の条件を満たす数列の 1.floor(N/2)番目(0-index) これは「次の二つの条件を満たす」ことと同値である。 1.ある値Xがあり、floor(N/2)個以上の値がX以上 2.そのXになりうる候補の中での最大のものが中央値となる。 この言い換えによって、Xを二分探索することができるようになる。(○○の最大、最小で判断関数があるものは二分探索に応用可能) 典型な問題を紹介する。最も上記のことそのままであるけど。 ARC101-D Medians of Medians(700)-中央値と二分探索 虐殺700の回。しかし問題自体は良問である。この問題は二つの知見にまとめられ、これはそのうちの一つである。 中央値の中央値ということになるが、セオリー通り二分探索で考えてみる。つまり、Xを二分探索条件として、 中央値列のうちXより大きいのがfloor(N/2)個以上あるか。 を使えばよい。これを満たすときはXの下限を引き上げ満たさねば上限を引き下げる。 中央値列の部分をさらに言いかえすると、 [i, j](ここでは閉区間を使用する)の列の中で、Xより大きいのがfloor((j-i+1)/2)個以上あるものの数が、全体でfloor(N/2)個あるかどうか と同値である。 これを愚直にやると、二分探索でO(log max_n)、Xあたりの判定関数がO(n^2)となり、間に合わない。 しかし、ここでさらにテクニックを駆使して、オーダーを落とせる。詳しくは転倒数への帰着のARC101Dに続きがある。
https://w.atwiki.jp/nkym_memo/pages/119.html
探索(searching) 表の中から、ある特定の値をもつデータを探し出す操作 レコード構造(record structure) 表に格納する1つ1つのデータ フィールド(field) レコード内のデータ キー(key) 探索の対象となるフィールド 辞書(dictionary) 以下の3つの機能をもつ抽象データ型 挿入―データを表に登録する 探索―与えられて値をキーに持つデータを探し出す 削除―与えられた値をキーにもつデータを削除する 探索法の種類 線形探索法(linear search) 二分探索法(binary search) ハッシュ法? チェイン法? オープンアドレス法? 二分探索木(binary search tree) AVL木? B木 参考文献 定本 Cプログラマのためのアルゴリズムとデータ構造(近藤嘉雪,ソフトバンククリエイティブ,1998)
https://w.atwiki.jp/nkym_memo/pages/124.html
二分探索法サンプル Node[]を二分探索して、見つかれば表示するプログラム #include stdio.h #include stdlib.h #define NELEM(array) (sizeof(array)/sizeof(array[0])) struct{ int key; int data; }Node[20000]; enum{ RAND_min = 0, RAND_max = 1000 }; int Rand(int min,int max) { static int flag; if(!flag){ srand((unsigned int)time(NULL)); flag = 1; } return (max - min + 1) * (float)rand()/RAND_MAX + min; } void init() { int i; for(i = 0;i NELEM(Node); i++){ Node[i].key = i; Node[i].data = Rand(RAND_min,RAND_max); printf("%d %d \n",Node[i].key,Node[i].data); } } int search(int key) { int low = 0; int middle; int high = NELEM(Node) - 1; while(low = high){ middle = (low + high) * 0.5; printf("middle %d\n",middle); if(key == Node[middle].key){ return (Node[middle].data); }else if(key Node[middle].key){ high = middle - 1; }else{ low = middle + 1; } } return -1; } int main(int argc,char *argv[]) { int key = atoi(argv[1]); int data; init(); if((data = search(key)) 0){ printf("Data found key %d data %d \n",key,data); }else{ printf("Not found\n"); } return 0; }
https://w.atwiki.jp/kanda_0608/pages/26.html
C#の学習など 二分探索木
https://w.atwiki.jp/abwiki/pages/178.html
探索に用いる2分木 各ノードにデータと2個のポインタを持ち、ポインタleftでつながる子孫のデータは自分より小さく、ポインタrightでつながる子孫のデータは自分より大きい。 データの検索は根(ルート)より始め、そのデータより小さいないし大きい場合にポインタleftないしrightをたどる。左右の釣り合いの取れた2分木の場合、N個のデータから検索する時間は O(log2(N)) 程度であるが、最悪の場合は O(N) 程度まで低下する。 原著ではノードの削除関数はdelete()関数ですが、予約語のためremove()としました #N88BASICTypeDef keytype = Byte' 探索のキーの型Type node' 木のノードleft As *node' 左側へのポインタright As *node' 右側へのポインタkey[20] As keytype' 探索キー(20文字)End TypeDim nil As node' 末端用ノードnilの作成Dim root As *node' ルートノードの作成root = VarPtr(nil)' 初期値は当然nilFunction insert(key As *keytype) As *node' 挿入(登録)Dim cmp As IntegerDim p As *node, pp As DWord, q As *node' 検索lstrcpy(nil.key, key)' 番人pp = VarPtr(root)' rootから検索p = rootcmp = lstrcmp(key, p- key)While cmp 0If cmp 0 Thenpp = VarPtr(p- left)p = p- leftElsepp = VarPtr(p- right)p = p- rightEnd Ifcmp = lstrcmp(key, p- key)Wend' nilでなければ登録済みIf p VarPtr(nil) Theninsert = NULLExit FunctionEnd If' 新しいノードの作成q = malloc(SizeOf(node))If q = NULL ThenPrint "メモリ不足"insert = NULLExit FunctionEnd Iflstrcpy(q- key, key)q- left = VarPtr(nil)q- right = p' 登録SetDWord(pp, q)insert = qEnd FunctionFunction remove(key As *keytype) As Integer' 削除できれば 0, 失敗なら 1 を返すDim cmp As IntegerDim p As *node, pp As DWord, q As *node, qq As DWord, r As *node, s As *node' 検索lstrcpy(nil.key, key)' 番人pp = VarPtr(root)' rootから検索p = rootcmp = lstrcmp(key, p- key)While cmp 0If cmp 0 Thenpp = VarPtr(p- left)p = p- leftElsepp = VarPtr(p- right)p = p- rightEnd Ifcmp = lstrcmp(key, p- key)Wend' 見つからないIf p = VarPtr(nil) Thenremove = 1Exit FunctionEnd If' 見つかったr = pIf r- right = VarPtr(nil) Then' 子が左のみの場合SetDWord(pp, r- left)ElseIf r- left = VarPtr(nil) Then' 子が右のみの場合SetDWord(pp, r- right)Else' 両方に子がある場合' 削除する節より小さくかつ最大の葉を捜す(削除する節の変わりに入れる節を探す)qq = VarPtr(r- left)q = r- leftWhile q- right VarPtr(nil)qq = VarPtr(q- right)q = q- rightWends = q' 新しい節SetDWord(qq, s- left)' 新しい節の元あった場所にs- leftを詰めるs- left = r- left' 新しい節に左の木を付けるs- right = r- right' 新しい節に右の木を付けるSetDWord(pp, s)' 新しい節を付けるEnd Iffree(r)remove = 0' 削除成功End FunctionFunction search(key As *keytype) As *nodeDim cmp As IntegerDim p As *node'検索lstrcpy(nil.key, key)' 番人p = root' rootから検索cmp = lstrcmp(key, VarPtr(p- key))While cmp 0If cmp 0 Thenp = p- leftElsep = p- rightEnd Ifcmp = lstrcmp(key, VarPtr(p- key))WendIf p VarPtr(nil) Then' 見つかったsearch = pElse' 見つからないsearch = NULLEnd IfEnd FunctionDim depth As Integer' 木構造の深さSub printtree(p As *node)If p = VarPtr(root) Then depth = 0If p- left VarPtr(nil) Thendepth = depth + 1printtree(p- left)depth = depth - 1End IfPrint Space$(5 * depth) + MakeStr(p- key)If p- right VarPtr(nil) Thendepth = depth + 1printtree(p- right)depth = depth - 1End IfEnd Sub'Dim s As String, buf[20] As Byte, str As StringWhile 1Input "Comand(挿入 I, 削除 R, 検索 S), 文字列 "; s, strZeroMemory(buf, 21)lstrcpy(buf, Left$(str, 20))Select Case sCase "i" Or "I"If insert(buf) ThenPrint "登録しました"ElsePrint "登録ずみです"End IfCase "r" Or "R"If remove(buf) ThenPrint "登録されていません"ElsePrint "削除しました"End IfCase "s" Or "S"If search(buf) ThenPrint "登録されています"ElsePrint "登録されていません"End IfCase ElsePrint "使えるのは I, R, S です"End SelectIf root VarPtr(nil) Then printtree(root)PrintWend