C++で二分木の隣接ノードのうちXORが奇数になるペアを数える方法

このチュートリアルでは、二分木においてXOR(排他的論理和)が奇数になる隣接ノードのペアの数を求めるプログラムについて解説します。

隣接ノードとは、親ノードとその直接の子ノードの組み合わせを指します。与えられた二分木に対して、隣接する2つの要素のXOR値が奇数になるペアがいくつあるかを数えるのが今回のタスクです。

XORが奇数になる条件

まず押さえておきたい重要な性質として、XORの結果が奇数になるのは、2つの値のうち片方が奇数でもう片方が偶数の場合だけです。同じ偶奇(パリティ)を持つ2つの値のXORは必ず偶数になります。

• 奇数 XOR 偶数 → 奇数
• 奇数 XOR 奇数 → 偶数
• 偶数 XOR 偶数 → 偶数

この性質を利用すれば、各ノードについて「親の値と自分の値の偶奇が異なるか」を調べるだけで答えを導き出せます。

アルゴリズムの考え方

木を再帰的に巡回しながら、各ノードとその親ノードの値のXORを計算し、結果が奇数であればカウントを1つ増やします。すべてのノードを訪問し終えた時点での合計が答えとなります。

実装の手順

1. 木のノードを表す構造体Nodeを定義する(値、左の子・右の子へのポインタ)
2. 親ノードと現在のノードを受け取る再帰関数count_pairを作成する
3. 親が存在し、親と現在のノードのXORが奇数ならカウントを増やす
4. 左右の子に対して再帰的に同じ処理を行い、結果を合計して返す

C++による実装例

#include <iostream>
using namespace std;
// 木のノード構造体
struct Node {
   int data;
   struct Node *left, *right;
};
// XORが奇数になるペアを数える関数
int count_pair(Node* root, Node *parent=NULL){
   if (root == NULL)
      return 0;
   // 親とのXORが奇数かどうかを判定
   int res = 0;
   if (parent != NULL && (parent->data ^ root->data) % 2)
      res++;
   return res + count_pair(root->left, root) + count_pair(root->right, root);
}
// 新しいノードを作成する関数
Node* newNode(int data){
   Node* temp = new Node;
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
int main(){
   struct Node* root = NULL;
   root = newNode(15);
   root->left = newNode(13);
   root->left->left = newNode(12);
   root->left->right = newNode(14);
   root->right = newNode(18);
   root->right->left = newNode(17);
   root->right->right = newNode(21);
   printf("%d ", count_pair(root));
   return 0;
}

出力

5

コードの解説

このプログラムでは、次のような二分木を構築しています。

        15
        /  \
      13    18
      /\   /\
    12 14 17 21

各隣接ペアのXORを実際に確認してみましょう。

このように、XORが奇数になる隣接ペアは全部で5つ存在するため、プログラムの出力は「5」となります。

計算量

このアルゴリズムは木の各ノードを一度ずつ訪問するため、時間計算量はO(N)(Nはノードの総数)です。空間計算量は再帰呼び出しのスタック深さに依存し、木が線形に偏っている最悪の場合にはO(N)となります。