counting sort

counting sort について書きます。

counting sort は、一次元配列の要素がすべてゼロ以上の整数である必要があります。

元の配列が、上記の条件を満たしていなくても、すべての要素の関係を崩さず、ゼロ以上の整数にできるならcounting sort を使えます。

計算量

O(n)

続きを読む

二分探索木/Binary-Search-Tree 削除/Delete c++

 ハトムギです。

前回に引き続き、二分探索木について書きます。

今回は、指定したkeyを持つnodeの削除について書きます。

  • 二分探索木とは
  • 二分探索木・削除
    • void del(node *u, int k)
      • 子を持たない場合 del0( node *u, int k, int rorl)
      • 子を一つ持つ場合 del1( node *u, int k, int rorl)
      • 子を二つ持つ場合 del2 ( node*u, int k, int rorl)

 

続きを読む

二分探索木/Binary-Search-Tree 探索/Search c++

 

こんにちは、ハトムギです。

今回も前回に引き続き、二分探索木について書きます。

  • 二分探索木とは
    • struct node {
    •       int key;
    •       node* parent, * left, * right;
    • };
  • 二分探索木・探索
    • bool find ( node *u , int k) 

  続きを読む

二分探索木/Binary-Search-Tree 挿入/Insert c++

 

ハトムギです。

アルゴリズムの基礎、二分探索木について勉強したので、今回は新しいnodeの挿入について書きます。

二分探索木とは

探索木の中でももっとも基本的なものが、二分探索木です

簡単に説明するとその名の通り、根から枝が二つに分かれ、また各節点から二つに分かれを繰り返します。

 

今回は、あるnodeのkeyより値の小さいnodeは左側に、大きいnodeは右側にくるように実装しました。

各nodeは、key, 親、左の子、右の子をメンバにもつ構造体により実装できます。

struct node {
      int key;
      node* parent, * left, * right;

};

二分探索木・挿入

void insert (node* u, int newkey) ;   

主な方針としては、malloc またはcalloc 関数でstruct node分の新しいnode を用意します。

node* z; //z=newnode 

z = (node*)malloc(sizeof(node));

z->key = k; z->p = NULL;

z->l = NULL;

z->r = NULL;

 

次に、key を比較して正しい位置に持って行きます。

 

ここで、keyと比較できないときがあるのに気がつきます。

まだ、二分探索木に一つもnodeが無いときは新しいnodeを根としておきます。

ここで、根を指しておくためのポインタがあれば便利だと気がつきます。

node * root; // root はグローバルに宣言しておくと便利です。

if (u == NULL) {

 root = z;

 return;

}

次に、二分探索木が一つ以上のnodeを持っているときです。

新しいnodeをあるnodeの下に付け加えるので、そのあるnodeを保存しておく struct node 型のポインタを確保します。

node * y = u ; 

あるnodeとは所謂、新しいnodeの親となるnodeです。

親がわかっても左の子なのか右の子なのかわかりません。そこで、右か左かの情報を保存しておく変数を宣言しておきます。

int rorl = 0: // le =0

準備が出来たので、二分探索木の端に到達するまで、keyの比較をしていきます。

端に到達したら、新しいnodeの親と子を設定して挿入完了です。

 while (1) {

   if (u->key > z->key) {

     u = u->l; 

     rorl = 0; 

   } else {

     u = u->r; 

     rorl = 1; 

   }

   if (u == NULL)break;

   y = u;

}

if (rorl)y->r = z;

else y->l = z;

z->p = y;