二分探索木での値の検索《グラフ理論・二分木》

木のメニュー【子の頂点・完全二分木の管理・二分探索木の判定・値の追加・値の検索 】

問題【STEP: 1】子の頂点 (二分木)
Task
二分木の情報と K 個の頂点と左右の組が与えられるので 子の頂点番号を出力してね。

【子の頂点 (二分木)】コード 1/3

reader.on('close', () => { 
   const [N, K, R] = lines.shift().split(' ').map(Number);
   const binary_tree = [];  // 二分木の情報
   for (let i = 0; i < N; i++) {  // N 個の各頂点について…
      binary_tree.push(new Map([['L', ''], ['R', '']]));  // {'L', ''},{'R', ''}の各ペアを保存
    }
   for (let i = 0; i < N - 1; i++) {  // N - 1 個の…
      const [a, b, LR] = lines.shift().split(' ');  // 枝の情報
      const [A, B] = [a, b].map(Number);  // A が親 B が子
      binary_tree[A - 1].set(LR, B);  // binary_tree[A-1].LR の要素を上書き
   }
   for (let i = 0; i < K; i++) {  // K 個の…
      const [v, l] = lines.shift().split(' ');  // 頂点と 子の左か右の情報
      console.log(binary_tree[v - 1].get(l));  // 子の頂点番号を出力
   }
});
hogeちゃんの画像

配列binary_tree[親 – 1] に{キーが’L’, 値が左の子の頂点番号},{キーが’R’, 値が右の子の頂点番号}がペアとなったマップを保存して二分木の情報を管理しました。

top

【子の頂点 (二分木)】コード 2/3

reader.on('close', () => {
   const adjacency_Matrix_binary = (a, b, lr) => {
      switch (lr) {  // lr が…
      case 'L':  // 'L' なら…
         Matrix[a][b] = 'L';  // Matrix[a][b] は 'L'
         break;
      case 'R':  // 'R' なら…
         Matrix[a][b] = 'R';  // Matrix[a][b] は 'R'
         break;
      }
   };
   const Matrix = [];  // 隣接行列(値は '' または 'L' または 'R')
   const [N, K, R] = lines.splice(0, 1)[0].split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      Matrix[i] = new Array(N).fill('');  // 隣接行列の各値を '' で初期化
   }
   for (let i = 0; i < N - 1; i++) {
      const [a, b, LR] = lines.splice(0, 1)[0].split(' ');
      const [A, B] = [a, b].map(e => e - 1);
      adjacency_Matrix_binary(A, B, LR);
   }
   for (let i = 0; i < K; i++) {
      const [v, lr] = lines.splice(0, 1)[0].split(' ');
      console.log(Matrix[v - 1].includes(lr) ? Matrix[v - 1].indexOf(lr) + 1 : '');
   }
   // console.log(Matrix);
});
hogeちゃんの画像

N × N の二次元配列 Matrix (値は ” または ‘L’ または ‘R’) で二分木の情報を管理しました。

top

【子の頂点 (二分木)】コード 3/3

reader.on('close', () => {
   const adjacency_List_binary = (a, b, lr) => {
      switch (lr) {  // lr が…
      case 'L':  // 'L'なら…
         List[a][0] = b + 1;  // List[a][0] は b + 1
         break;
      case 'R':  // 'R'なら…
         List[a][1] = b + 1;  // List[a][1] は b + 1
         break;
      }
   };
   const List = [];  // 隣接リスト (有向グラフ)
   const [N, K, R] = lines.shift().split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List[i] = ['', ''];  // List[i] の要素の初期値は ['', '']
   }
   for (let i = 0; i < N - 1; i++) {
   const [a, b, LR] = lines.shift().split(' ');
   const [A, B] = [a, b].map(e => e - 1);
      adjacency_List_binary(A, B, LR);
   }
   for (let i = 0; i < K; i++) {
      const [v, LR] = lines.shift().split(' ');
      switch (LR) {  // LR が…
      case 'L':  // 'L'なら…
         console.log(List[v - 1][0]);  // v の左の子(List[v - 1][0])を出力
         break;
      case 'R':  // 'R'なら…
         console.log(List[v - 1][1]);  // v の右の子(List[v - 1][１])を出力
         break;
      }
   }
   // console.table(List);
});
hogeちゃんの画像

隣接リストをアレンジして二分木の情報を管理しました。

top
問題【STEP: 2】子の頂点 (多分木)
Task
二分木の情報と K 個の頂点と左右の組が与えられるので 各頂点の指定された子の頂点番号を出力してね。

【子の頂点 (多分木)】コード

reader.on('close', () => {
   const adjacency_Linear_List = (a, b) => {  // 隣接リスト (有向グラフ)
      List[a].push(b + 1);
   };
   const List = [];  // 隣接リスト (有向グラフ)
   const [N, K, R] = lines.shift().split(' ').map(Number);
   for (let i = 0; i < N; i++) {
      List[i] = [];
   }
   for (let i = 0; i < N - 1; i++) {
      const [A, B] = lines.shift().split(' ').map(e => e - 1);
      adjacency_Linear_List(A, B);
   }
   for (let i = 0; i < K; i++) {
      const [v, l] = lines.shift().split(' ').map(e => e - 1);
      console.log(List[v][l]);  // 頂点 v の l 番目の子の番号を出力
   }
   // console.table(List);
});
hogeちゃんの画像

隣接リストで多分木の情報を管理。

top
問題【STEP: 3】完全二分木の管理
Task
完全二分木の情報と頂点と左右の組が与えられるので頂点の指定された子の番号を出力してね。

【完全二分木の管理】コード 1/2

reader.on('close', () => {
   const [N, K, R] = lines.shift().split(' ').map(Number);
   const node = [R];  // 頂点番号
// 根→node[0], node[i]の左の子→node[2*i+1], node[i]の右の子→node[2*i+2]
   for (let i = 0; i < N - 1; i++) {
      const [a, b, LR] = lines.shift().split(' ');
      const [A, B] = [a, b].map(Number);  // A は B の親
      const pointer = node.indexOf(A);  // 親番号のポインタ
      switch (LR) {  // LR が…
      case 'L':  // 'L'なら…
         node[2 * pointer + 1] = B;  // node[2 * pointer + 1]に B を保存
         break;
      case 'R':  // 'R'なら…
         node[2 * pointer + 2] = B;  // node[2 * pointer + 2]に B を保存
         break;
      }
   }
   for (let i = 0; i < K; i++) {
      const [v, LR] = lines.shift().split(' ');
      const pointer = node.indexOf(Number(v));  // node に含まれる v (親の頂点)のポインタ
      // console.log(pointer);
      switch (LR) {  // LR が…
      case 'L':  // 'L'なら…
         console.log(node[2 * pointer + 1]);  // 左の子を出力
         break;
      case 'R':  // 'R'なら…
         console.log(node[2 * pointer + 2]);  // 右の子を出力
         break;
      }
   }
});
hogeちゃんの画像

完全二分木の条件

  1. 全ての葉以外のノードが2つの子ノードを持つ。
  2. 全ての葉が根から等しい距離にある。

node.indexOf(Number(v))で親番号の添字を調べて 子の番号の添字を計算(2 * pointer + 1)または(2 * pointer + 2)で求めています。

top

【完全二分木の管理】コード 2/2

reader.on('close', () => {
   const [N, K, R] = lines.shift().split(' ').map(Number);
   const node = [R];  // 頂点番号の値
// 根→node[0], node[i]の左の子→node[2*i+1], node[i]の右の子→node[2*i+2]
   const pointer = [];  // nodeのポインタ(pointer[i] = node.indexOf(i))  
   pointer[R] = 0;  // 根のポインタは 0
   for (let i = 0; i < N - 1; i++) {
      const [a, b, LR] = lines.shift().split(' ');
      const [A, B] = [a, b].map(Number);
      switch (LR) {  // LR が…
      case 'L':  // 'L'なら…
         pointer[B] = 2 * pointer[A] + 1;  // B のポインタは 2*pointer[A]+1
         break;
      case 'R':  // 'R'なら…
         pointer[B] = 2 * pointer[A] + 2;  // B のポインタは 2*pointer[A]+1
         break;
      }
      node[pointer[B]] = B;  // node[B のポインタ]に B を保存
   }
   for (let i = 0; i < K; i++) {
      const [v, LR] = lines.shift().split(' ');
      switch (LR) {  // LR が…
      case 'L':  // 'L'なら…
         console.log(node[pointer[v] * 2 + 1]);  // 左の子を出力
         break;
      case 'R':  // 'R'なら…
         console.log(node[pointer[v] * 2 + 2]);  // 右の子を出力
         break;
      }
   }
});
hogeちゃんの画像

配列 node は頂点の番号を保存。

配列 pointer[i] は node の中に含まれる i の位置(ポインタ)を保存。

top
問題【STEP: 4】二分探索木の判定
Task
与えられた根付き木は二分探索木？  “YES” または “NO” を 出力してね。

【二分探索木の判定】コード 1/3

reader.on('close', () => {
   const [N, R] = lines.shift().split(' ').map(Number);
   const node = [R];  // 頂点番号の値
   const pointer = [];  // pointer[i] = node.indexOf(node[i])
   pointer[R] = 0;  // pointer[R] = node.indexOf(node[R])
   const parent_set = new Set();  // 親の頂点(セット)
   let binary_search_tree = true;  // 二分探索木であるかどうかの真偽値
   for (let i = 0; i < N - 1; i++) {
      const [a, b, LR] = lines.shift().split(' ');
      const [A, B] = [a, b].map(Number);
      switch (LR) {  // LR が…
      case 'L':  // 'L'なら…
         pointer[B] = 2 * pointer[A] + 1;  // B のポインタは 2*pointer[A]+1
         break;
      case 'R':  // 'R'なら…
         pointer[B] = 2 * pointer[A] + 2;  // B のポインタは 2*pointer[A]+2
         break;
      }
      node[pointer[B]] = B;
      parent_set.add(A);  // A(親の頂点) を parent_set に加える
   }
   const parent = [...parent_set];  // parent_set の要素を配列の要素として保存
   for (let i = 0; i < parent.length; i++) {
      const point = pointer[parent[i]];  // 親のポインタ
      const L = node[point * 2 + 1];  // 左の子
      const R = node[point * 2 + 2];  // 右の子
      const P = node[point];  // 親
      if ((L && L >= P) ||(R && R <= P)) {  // 左の子が親以上 または 右の子が親以下なら…
         binary_search_tree = false;  // 二分探索木に該当しない
         break;
      } 
   }
   console.log(binary_search_tree ? 'YES' :'NO');
});
hogeちゃんの画像

二分探索木の条件

  1. 各頂点が持つ子の数が高々 2。
  2. 「左の子 < 頂点 < 右の子」が全ての頂点について成り立つ。
top

【二分探索木の判定】コード 2/3

reader.on('close', () => {
   const adjacency_list_map = (a, b, lr) => {
      if (!llist_map.has(a)) {
         llist_map.set(a, [0, 1000000]);
      }
      switch (lr) {
      case 'L':
         llist_map.get(a)[0] = b;
         break;
      case 'R':
         llist_map.get(a)[1] = b;
         break;
      }
   };
   const [N, R] = lines[0].split(' ').map(Number);
   const llist_map = new Map();
   let binary_search_tree = true;
   for (let i = 1; i < N; i++) {
      const [a, b, LR] = lines[i].split(' ');
      const [A, B] = [a, b].map(Number);
      adjacency_list_map(A, B, LR);
   }
   for (var [key, value] of llist_map) {
      if (value[0] > key || value[1] < key) {
         binary_search_tree = false;
         break;
      }
   }
   console.log(binary_search_tree ? 'YES' : 'NO');
});
hogeちゃんの画像

llist_map の初期値は {a(親), [0(左の子), 1000000(右の子)]}

top

【二分探索木の判定】コード 3/3

reader.on('close', () => {
   const [N, R] = lines[0].split(' ').map(Number);
   let binary_search_tree = true;
   for (let i = 1; i < N; i++) {
      if (!binary_search_tree) {
         break;
      }
      const [a, b, LR] = lines[i].split(' ');
      const [A, B] = [a, b].map(Number);
      switch (LR) {
         case 'L':
         if (B >= A) {
            binary_search_tree = false;
         }
         break;
         case 'R':
         if (B <= A) {
            binary_search_tree = false;
         }
         break;
      }
   }
   console.log(binary_search_tree ? 'YES' : 'NO');
});
hogeちゃんの画像

二分探索木の 条件は『「左の子 < 頂点 < 右の子」が全ての頂点について成り立つ』なので 全探索で 一箇所でも条件に当てはまらない場合は  binary_search_tree = false;になるように条件分岐しました。

top
問題【STEP: 5】二分探索木への値の追加
Task
二分探索木に 値 V を適切な位置に追加した場合の親子情報を出力してね。

【二分探索木への値の追加】コード

reader.on('close', () => {
   const [N, R] = lines.shift().split(' ').map(Number);
   const node = [R];
   const pointer = [];
   pointer[R] = 0;
   for (let i = 0; i < N - 1; i++) {
      const [a, b, LR] = lines.shift().split(' ');
      const [A, B] = [a, b].map(Number);
      switch (LR) {  // LR が…
      case 'L':  // 'L'なら…
         pointer[B] = 2 * pointer[A] + 1;  // B のポインタは 2*pointer[A]+1
         break;
      case 'R':  // 'R'なら…
         pointer[B] = 2 * pointer[A] + 2;  // B のポインタは 2*pointer[A]+2
         break;
      }
      node[pointer[B]] = B;
   }
   const v = Number(lines.shift());
   let point = 0;  // 根からスタート
   while (node[point]) {  // point 番目の要素に値がある間
      v < node[point] ? point = 2 * point + 1 : point = 2 * point + 2;
  // v が point 番目の要素より大きければ 左の子 違っていれば 右の子
   }
   console.log(node[Math.floor((now - 1) / 2)]);  // 親要素を出力
   console.log(now % 2 ? 'L' : 'R');
});
hogeちゃんの画像

二分探索木への値の追加

  1. ルート(node[0])から手順を開始。
  2. node[0]とvを比較。
  3. 「v < node[point]」→左の子node[2 * point + 1]へ移動
    「v > node[point]」→右の子node[2 * point + 2]へ移動。
  4. node[point] に値がなければれば node[point] に v を挿入。
    値があれば 次のnode[point]に移って繰り返し。
top
問題【FINAL】二分探索木での値の検索
Task
二分探索木の情報と K 個の数が与えられるので二分探索木に含まれているか判定してね。

【二分探索木での値の検索】コード 1/2

reader.on('close', () => {
   const [N, K, R] = lines.shift().split(' ').map(Number);
   const node = [R];
   const pointer = [];
   pointer[R] = 0;
   for (let i = 0; i < N - 1; i++) {
      const [A, B] = lines.shift().split(' ').map(Number);
      const A_pointer = node.indexOf[A];
      switch (A > B) {
      case true:
         pointer[B] = 2 * pointer[A] + 1;
         break;
      case false:
         pointer[B] = 2 * pointer[A] + 2;
         break;
      }
      node[pointer[B]] = B;
   }
   for (let i = 0; i < K; i++) {
      let included = false;
      const q = Number(lines.shift());
      let point = 0;
      while (q !== node[point] && node[point]) {
         switch (q < node[point]) {
         case true:
            point = 2 * pointer[node[point]] + 1;
            break;
         case false:
            point = 2 * pointer[node[point]] + 2;
            break;
         }
      }
      if (node[point] === q) {
         included = true;
      }
      console.log(included ? 'Yes' : 'No');
   }
});
hogeちゃんの画像

二分探索木での探索手順

  1. ルートから手順を開始。
  2. point とqを比較して 等しいか 値が存在しなければ終了。
  3. 「q < point」→左の子へ移動「q > point」→右の子へ移動。
top

【二分探索木での値の検索】コード 2/2

reader.on('close', () => {
   const [N, K, R] = lines.shift().split(' ').map(Number);
   const node_set = new Set();
   for (let i = 0; i < N - 1; i++) {
    const [A, B] = lines.shift().split(' ').map(Number);
      node_set.add(A);
      node_set.add(B);
   }
   const node = [...node_set];
   for (let i = 0; i < K; i++) {
      const q = Number(lines.shift());
      console.log(node.includes(q) ? 'Yes' : 'No');
   }
});
hogeちゃんの画像

全探索しても OK でした。

top

コメント