プログラミング原人の進化ログ

プログラミング原人の進化論

オレ　プログラミング　ベンキョウ　スル。マナンダ　コト　カク。

トップ > アルゴリズム > C++で実装する二分探索木

C++で実装する二分探索木

アルゴリズム アルゴリズム-データ構造

二分探索木とは何かを簡単に説明してから、実装します。この記事では二分探索木に対する基本的な操作である要素の挿入・探索・削除ができるようになることを目標としています。

二分探索木とは？

探索木というデータ構造があります。各ノードがキーと値を持ち、辞書や優先度付きキューとして使用することができます。
二分探索木とは、その二分木バージョンです。こういったものをイメージしてもらえればOKです。

f:id:programgenjin:20190224090520p:plain

とりあえず、各ノードにはキーを書いてあります。
二分探索木は、要素の挿入や探索といった操作を効率的に行うことができます。

二分探索木のルール

上の二分木を見てください。あるノードに注目すると、そのノードのキーよりも、左の子のキーは小さく、右の子のノードは大きいことがわかります。
実は、二分探索木は次のようなルールにしたがって作られています。

  • ノードxの左部分木に属するノードのキーは、xのキー以下である。ノードxの右部分木に属するノードのキーは、xのキー以上である。

f:id:programgenjin:20190224092026p:plain

じっと睨むと、確かにそうなっています。

二分探索木を実装してみる

では、二分探索木に対する要素の挿入・探索・削除を実装していきます。

要素の挿入

二分木に要素を追加し、キーの値に応じて適切な位置に配置します。まず、例を考えて感覚をつかみます。次のようなキーのような順で要素を追加するとします。なお、ここではキーのみを考え、値は考えません。要素の位置を決定するにはキーさえあれば良いからです。

{30, 88, 12, 1, 20, 17, 25}

何もない状態から、上のルールに従って二分木を構成していきます。

f:id:programgenjin:20190224094027p:plain f:id:programgenjin:20190224094059p:plain f:id:programgenjin:20190224094116p:plain f:id:programgenjin:20190224094137p:plain f:id:programgenjin:20190224094153p:plain f:id:programgenjin:20190224094209p:plain f:id:programgenjin:20190224090520p:plain

では、実装していきます。次の問題を解いてみます。
二分探索木 挿入| アルゴリズムとデータ構造 | Aizu Online Judge

解答の骨子はこんな感じになると思います。

#include<iostream>
#include<string>
using namespace std;

struct Node {
  int key;
  Node *parent, *left, *right;
};

void insert(int key) {
  // insert
}

void print() {
  // print
}

int main() {
  int i, m, key;
  string command;

  cin >> m;
  for (i = 0; i < m; i++) {
    cin >> command;
    if (command[0] == 'i') {
      cin >> key;
      // insert
    } else {
      // print
    }
  }

  return 0;
}

これに沿ってコードを書いていきます。
解答例です。

#include<iostream>
#include<string>
using namespace std;

struct Node {
  int key;
  Node *parent, *left, *right;
};

Node *NIL, *root;

void insert(int key) {
  Node *x, *y, *z;
  
  // initialize
  z = new Node;  // 新しい要素のメモリ確保
  z->key = key;
  z->left = NIL;
  z->right = NIL;
  y = NIL;
  x = root;

  // rootから適切な位置まで二分木をたどる
  while (x != NIL) {
    y = x;
    if (z->key < x->key) x = x->left;
    else x = x->right;
  }

  // 新しい要素を配置する場所を決定
  z->parent = y;  
  if (y == NIL) root = z;  // もともと木が存在しなかった場合
  else if (z->key < y->key) y->left = z;
  else y->right = z;    
}

// 先行順巡回
void preorder(Node* node) {
  if (node == NIL) return;
  cout << " " << node->key;
  if (node->left != NIL) preorder(node->left);
  if (node->right != NIL) preorder(node->right); 
}

// 中間順巡回
void inorder(Node* node) {
  if (node == NIL) return;
  if (node->left != NIL) inorder(node->left);
  cout << " " << node->key;
  if (node->right != NIL) inorder(node->right);
}

void print() {
  inorder(root);
  cout << endl;
  preorder(root);
  cout << endl;
}

int main() {
  int i, m, key;
  string command;

  cin >> m;
  for (i = 0; i < m; i++) {
    cin >> command;
    if (command[0] == 'i') {
      cin >> key;
      insert(key);
    } else {
      print();
    }
  }

  return 0;
}

ちょっと長いですね。簡単に解説入れていきます。
・それぞれのノードは、そのノードの親、左の子、右の子を指すポインタを持つとします。これによって木の親子関係を保持します。そこで、Node構造体を定義します。
・根をNode型ポインタroot、ノードが存在しないことを値を持たないNode型のポインタNILによって表現します。
・与えられたキーを持つ要素を適切な位置に挿入するinsert関数を定義します。新しい要素を保持するポインタzの位置を、xを使って根からノードをたどって探していきます。xがNILに到達すると探索を終了します。yはxの親となっており、探索終了の後zの親をさし示すことになります。
先行順巡回、中間順巡回がわからない方はこちら。
programgenjin.hatenablog.com

要素の探索

次の問題を解いてみます。
二分探索木 検索 | アルゴリズムとデータ構造 | Aizu Online Judge

解答の骨子はこんな感じです。

#include<iostream>
using namespace std;

struct Node {
  int key;
  Node *parent, *left, *right;
};

void insert() {
  // insert
}

Node* find() {
  // find
  // 該当するノードを指すポインタを返す
}

void print() {
  // print
}

int main() {
  int i, m, key;
  string command;

  cin >> m;
  for (i = 0; i < m; i++) {
    cin >> command;
    if (command[0] == 'i') {
      // insert
    } else if (command[0] == 'f') {
      // find
    } else {
      // print
    }
  }

  return 0;
}

insert, print関数については先ほどと同様にできるでしょう。問題はfind関数ですが、根を出発点として、現在のノードのキーが調べたいキーより小さい場合は左の子、同じまたは大きい場合は右の子に移動を繰り返すことで探索が可能となるはずです。

解答例：

#include<iostream>
using namespace std;

struct Node {
  int key;
  Node *parent, *left, *right;
};

Node *root, *NIL;

void insert(int key) {
  Node *x, *y, *z;

  // initialize
  z = new Node;
  z->left = NIL;
  z->right = NIL;
  z->key = key;
  y = NIL;
  x = root;

  while (x != NIL) {
    y = x;
    if (z->key < x->key) x = x->left;
    else x = x->right;
  }

  z->parent = y;
  if (y == NIL) root = z;
  else if (z->key < y->key) y->left = z;
  else y->right = z;  
}

Node* find(int key) {
  Node *x;

  x = root;
  while (x != NIL && x->key != key) {
    if (key < x->key) x = x->left;
    else x = x->right;
  }
  
  return x;        
}

void preorder(Node* node) {
  if (node == NIL) return;
  cout << " " << node->key;
  if (node->left != NIL) preorder(node->left);
  if (node->right != NIL) preorder(node->right);
}

void inorder(Node* node) {
  if (node == NIL) return;
  if (node->left != NIL) inorder(node->left);
  cout << " " << node->key;
  if (node->right != NIL) inorder(node->right);
}

void print() {
  inorder(root);
  cout << endl;
  preorder(root);
  cout << endl;  
}

int main() {
  int i, m, key;
  string command;

  cin >> m;
  for (i = 0; i < m; i++) {
    cin >> command;
    if (command[0] == 'i') {
      // insert
      cin >> key;
      insert(key);
    } else if (command[0] == 'f') {
      // find
      cin >> key;
      if (find(key) != NIL) cout << "yes" << endl;
      else cout << "no" << endl;
    } else {
      // print
      print();
    }
  }

  return 0;
}

要素の削除

最後に要素の削除をやります。次の問題を解いてみます。
二分探索木 削除 | アルゴリズムとデータ構造 | Aizu Online Judge

解答の骨子はこんな感じです。

#include<iostream>
#include<string>
using namespace std;

struct Node {
  int key;
  Node *parent, *left, *right;
};

void insert(int key) {
  // insert
}

void find(int key) {
  // find
}

void delete_node(int key) {
  // delete
}

int main() {
  int i, m, key;
  string command;

  cin >> m;
  for (i = 0; i < m; i++) {
    cin >> command;
    if (command[0] == 'i') {
      cin >> key;
      // insert
    } else if (command[0] == 'f') {
      cin >> key;
      // find
    } else if (command[0] == 'd') {
      cin >> key;
      // delete
    } else {
      // print
    }
  }
    
  return 0;
}

先ほどの問題にdelete_node関数を加えるだけほぼOKです。
ではdelete_node関数を実装していきます。
ノードの削除は、ポインタを繋ぎかえることによって行います。そのために、Node型のポインタx, y, zを用意します。zは削除したいキーを持つノードです。yは実際に削除するノード、xはyの子で、いずれもノードを削除するために用います。ノードの削除は次のzの持つこの数によって３通りに分けて行います。

  1. zが子を持たない

f:id:programgenjin:20190226114922j:plain

  1. zが一つの子を持つ

f:id:programgenjin:20190226114955j:plain

  1. zが２つの子を持つ

f:id:programgenjin:20190226115008j:plain


まず、yを決めます。この数が０または１の場合は、zとyが一致します。この数が２の場合は、zの次節点をyとします。次節点とは中間順巡回でzの次にくるノードのことです。zの次節点がyになるのは、二分探索木においてzの次に小さいキーを持つノードがzの次節点だからです。
次節点の求め方ですが、zが右部分木を持つ場合は、中間順巡回の性質からその右部分木の最小のキーのノードが次節点となります。右部分木を持たない場合は、zの祖先をたどっていって、左の子を持っている最初のノードが次節点です。なぜなら、中間順巡回は左部分木、根、右部分木の順にノードにアクセスするからです。
yを決めたら、xをyの親の子とします。次に、xがNILでない場合はxの親をyの親とします。
最後に、zのこの数が２である場合は、yのキーをzのキーとします。

以上を踏まえてノードを削除する関数を実装すると、次のようになります。

// 次節点を求める
Node* next_node(Node *node) {
  Node *x;
  
  if (node->right != NIL) {
    x = node->right;
    while (x->left != NIL) {
      x = x->left;
    }    
  } else {    
    x = node;    
    while (x->parent != NIL && x == x->parent->right) {
      x = x->parent;
    }
    x = x->parent;
  }

  return x;
}

void delete_node(int key) {
  Node *x, *y, *z;

  z = find(key);  // 削除されるべきキーを持ったノード

  // yを決める
  if (z->left == NIL || z->right == NIL) {  // zが子を持たないor１個
    y = z;
    } else {  // zが子を２つ持つ
    y = next_node(z);  // 次節点
  }
  // xを決める
  if (y->left != NIL) x = y->left;
  else x = y->right;

  // ポインタつなぎ替え
  if (x != NIL) x->parent = y->parent;
  if (y->parent == NIL) root = x;
  else if (y == y->parent->left) y->parent->left = x;
  else y->parent->right = x;
  // zの子が２つの場合 yのキーをzに移す
  if (z != y) z->key = y->key;

  delete y;  // yのメモリを解放
}

解答例こちら。

#include<iostream>
#include<string>
using namespace std;

struct Node {
  int key;
  Node *parent, *left, *right;
};

Node *root, *NIL;

void insert(int key) {
  Node *x, *y, *z;

  // initialize
  z = new Node;
  z->left = NIL;
  z->right = NIL;
  z->key = key;
  y = NIL;
  x = root;

  while (x != NIL) {
    y = x;
    if (z->key < x->key) x = x->left;
    else x = x->right;
  }

  z->parent = y;
  if (y == NIL) root = z;
  else if (z->key < y->key) y->left = z;
  else y->right = z;
}

Node* find(int key) {
  Node *x;

  x = root;
  while (x != NIL && x->key != key) {
    if (key < x->key) x = x->left;
    else x = x->right;
  }

  return x;
}

// 次節点を求める
Node* next_node(Node *node) {
  Node *x;
  
  if (node->right != NIL) {
    x = node->right;
    while (x->left != NIL) {
      x = x->left;
    }    
  } else {    
    x = node;    
    while (x->parent != NIL && x == x->parent->right) {
      x = x->parent;
    }
    x = x->parent;
  }

  return x;
}

void delete_node(int key) {
  Node *x, *y, *z;

  z = find(key);  // 削除されるべきキーを持ったノード

  // yを決める
  if (z->left == NIL || z->right == NIL) {  // zが子を持たないor１個
    y = z;
    } else {  // zが子を２つ持つ
    y = next_node(z);  // 次節点
  }
  // xを決める
  if (y->left != NIL) x = y->left;
  else x = y->right;

  // ポインタつなぎ替え
  if (x != NIL) x->parent = y->parent;
  if (y->parent == NIL) root = x;
  else if (y == y->parent->left) y->parent->left = x;
  else y->parent->right = x;
  // zの子が２つの場合 yのキーをzに移す
  if (z != y) z->key = y->key;

  delete y;  // yのメモリを解放
}

void preorder(Node* node) {
  if (node == NIL) return;
  cout << " " << node->key;
  if (node->left != NIL) preorder(node->left);
  if (node->right != NIL) preorder(node->right);
}

void inorder(Node* node) {
  if (node == NIL) return;
  if (node->left != NIL) inorder(node->left);
  cout << " " << node->key;
  if (node->right != NIL) inorder(node->right);
}

void print() {
  inorder(root);
  cout << endl;
  preorder(root);
  cout << endl;
}

int main() {
  int i, m, key;
  string command;

  cin >> m;
  for (i = 0; i < m; i++) {
    cin >> command;
    if (command[0] == 'i') {
      cin >> key;
      insert(key);
    } else if (command[0] == 'f') {
      cin >> key;
      if (find(key) != NIL) cout << "yes" << endl;
      else cout << "no" << endl;
    } else if (command[0] == 'd') {
      cin >> key;
      delete_node(key);
    } else {
      print();
    }
  }
    
  return 0;
}

まとめ

だいぶ長くなりましたが、問題を３題解いて、二分探索木の機能を実装しました。自信のある方は最初から３題目を解いてもいいかもしれませんね。

参考

渡部有隆. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. Ozy, 秋葉拓哉協力. 株式会社マイナビ. 2015.