counting sort
counting sort について書きます。
counting sort は、一次元配列の要素がすべてゼロ以上の整数である必要があります。
元の配列が、上記の条件を満たしていなくても、すべての要素の関係を崩さず、ゼロ以上の整数にできるならcounting sort を使えます。
計算量
O(n)
続きを読む二分探索木/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;