C++ を使用してファイルを二分探索木に読み込む
このチュートリアルでは、ファイルを C++ のバイナリ検索ツリーに読み込む方法について説明します。 まず、二分探索木とその操作について簡単に説明します。
後で、ファイルを二分探索木に読み込む方法について説明します。
C++ の二分探索木
二分探索木は、ノードの特別な配置を持つ二分木であり、後で検索に役立ちます。 ここで言及する価値があるのは、統計によると操作の 90% 以上が検索操作であるということです。 insert、update、delete などの操作は 10% 未満です。
二分探索ツリーでは、各ノードは常に左の子よりも大きく、(重複の場合) 右の子よりも小さくなるように配置されます。
この定義は、ツリーのすべてのノードに再帰的に適用されます。 したがって、常に、左側のサブツリーのすべてのノードよりも大きく、右側のサブツリーのすべてのノードよりも小さいルートがあります。
5 / 3 8 / \ / 1 2 6 9
ここでは、自明な二分探索木の例を見ることができます。 前述のように、二分探索木は検索操作に役立ちます。
たとえば、上記のツリーで 7 (キーと言います) を検索したい場合。 キーをルート ノード 5 と比較します。
キーがルート要素よりも大きい。 したがって、左側のサブツリーのすべての値がルート ノードより小さいため、右側のサブツリーでのみキーを検索する必要があります。
次に、キーを 8 と比較し、キーが 8 よりも小さいため、8 の左側のサブツリーに向かって移動します。 次に、6 をキーと比較し、6 の右側のサブツリーに向かって移動します。
6 の右側には NULL があります。 したがって、要素が見つかりませんを停止します。 6 の代わりに 3 の比較を行いました。
ツリー内の要素が多いほど、ツリー内の全要素との比較の比率はさらに減少します。 検索は簡単に思えます。 ただし、後で完全なコードを提供します。
完全なコードを提示する前に、BST での挿入操作と削除操作について説明しましょう。 ただし、最初にクラス Node の定義を確認することをお勧めします。
template <class T>
class Node {
public:
T data;
Node* left;
Node* right;
Node(T data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
ここでは、テンプレートを使用して、任意のデータ型に同じツリーを使用しました。 BSTを使用する際に、その利点をお見せします。
Node クラスの定義には、オブジェクトの作成時に選択できる template タイプのデータがあります。 ツリーにリンクされた実装を実装するため、左右のポインターがあります。
コンストラクターでは、データに加えて、左側と右側のポインターに NULL を割り当てます。これは、最初のすべての新しいノードに左右の子ノードがないためです。
C++ での二分探索木への挿入
BST に新しい要素を挿入することを検討してください。 ツリーが空であるか、1つ以上のノードがあるかの 2つのケースが考えられます。
最初のケースは、ツリーが空です。 この挿入後、新しい要素がツリーのルート ノードになります。 2 番目のケースでは、新しいノードは既存のノードの左または右の子になります。
したがって、ルート ノードから開始し、ノードの値を新しい値と比較します。 現在のノードの左側または現在のノードの右側に移動します。
最後に、NULL (ノードなし) になるポイントに到達します。 新しいノードを作成し、ノードと新しいノードの値に従って、左または右の子にします。
たとえば、ノード 7 を BST に挿入すると、新しい BST は次のようになります。
5 / 2 8 / \ /
1 3 6 9
7
ルートノードから始めて、5 は 7 より小さいので、右に移動します。 8 の方が大きいので、左側に移動します。 6 は小さいです。 したがって、右に移動します。
右側にはノードがないので、新しいノードを作成し、ノード 6 の右の子にします。 挿入関数の実装を見ていきますが、その前に、クラス BST の定義を見てください。
template <class T>
class BST {
Node<T> *root;
public:
BST() { root = NULL; }
...
ここでも、データ メンバ Node<T> のデータ メンバー root のみを使用して、BST のテンプレート クラスを作成しました。 コンストラクターで、root ノードに NULL を割り当てました。これは、ツリーが空であることを意味します。
したがって、削除の場合、最後のノードを削除するたびに、ルート ノードに NULL を割り当てます。 insert 関数を見てみましょう。
Node<T>* insert(T key) { root = insert(root, key); }
Node<T>* insert(Node<T>* temp, T key) {
if (temp == NULL) return new Node<T>(key);
if (temp->data > key)
temp->left = insert(temp->left, key);
else
temp->right = insert(temp->right, key);
return temp;
}
まず、挿入タスクを実行する主力関数を呼び出すラッパー関数があります。 ラッパー関数を作成する理由は、セキュリティ上の理由から、クラス外の root ノードへのアクセスを許可したくないからです。
ラッパー関数について知りたい場合は、ラッパー関数をクリックしてください。
私たちの主力関数には、再帰的な実装があり、基本ケースは NULL ノードです。ここで、新しいノードを作成し、そのアドレスを呼び出し元に返します。呼び出し元は、このアドレスを左または右の子に割り当ててリンクします。 ツリーの新しいノード。
NULL ノードがない場合は、データを比較し、現在のノードの値が小さいか大きいかに応じて、右または左に移動します。これについては、検索戦略について既に説明しました。
C++ の二分探索木の削除
挿入と同様に、BST の要素の削除には 2つのケースが考えられます。 現在のノードの削除後にツリーが空にならないように、最後のノード、ルート ノードを削除するか、ツリー内に複数のノードがあるノードを削除します。
最初のケースでは、ノードを削除し、NULL をルート ノードに割り当てます。 2 番目のケースでは、次の 3つの可能性があります。
- ノードには子ノードがありません
- ノードには子ノードが1つしかありません
- ノードには左右の子ノードがあります
最初の 2つのスキームは非常に単純です。 子ノードがない場合。
ノードを削除して NULL を返す (再帰的な定義があるため) 関数を呼び出す際に、親ノードが NULL をその右または左のポインターに割り当てるようにします。
ノードに子ノードが 1つある場合は、子ノードを現在のノードに置き換え、現在のノードを削除します。 その結果、父親が死ぬため、子ノードは父親ではなく祖父に割り当てられます (この類推で申し訳ありません)。
最後のケースはトリッキーで、ノードに左右両方の子があります。 この場合、2つの選択肢があります。
最初に、現在のノードの右サブツリーから最も左の子孫ノードを選択するか、左サブツリーから最も右の子孫ノードを選択します。 どちらの場合も、選択ノードの値を現在のノードにコピーします。
これで、BST に同じ値を持つ 2つのノードができました。 したがって、現在のノードの左側のサブツリーまたは右側のサブツリーで再帰的な delete 関数を再度呼び出します。
例を考えてみましょう。 ルートノードから 5 を削除したいとします。 5 の右サブツリーの一番左のノードである右サブツリーからノード 6 を選択するか、左サブツリーからノード 3 を選択することができます。 5 の左部分木。
5 3 6 / \ / \ / 2 8 2 8 2 8 / \ / \ / / \ / \ 1 3 6 9 1 6 9 1 3 9
delete 関数の実装を見てみましょう。
Node<T>* deleteNode(T key) { root = deleteNode(root, key); }
Node<T>* deleteNode(Node<T>* temp, T key) {
if (temp == NULL) return temp;
if (temp->data > key)
temp->left = deleteNode(temp->left, key);
else if (temp->data < key)
temp->right = deleteNode(temp->right, key);
else {
if (temp->left == NULL && temp->right == NULL) {
delete temp;
temp = NULL;
} else if (temp->left == NULL) {
Node<T>* curr = temp;
temp = temp->right;
delete curr;
} else if (temp->right == NULL) {
Node<T>* curr = temp;
temp = temp->left;
delete curr;
} else {
Node<T>* toBeDeleted = findMinNode(temp->right);
temp->data = toBeDeleted->data;
temp->right = deleteNode(temp->right, toBeDeleted->data);
}
}
return temp;
}
繰り返しますが、最初にラッパー関数があります。 次に、主力機能があります。
最初の 3 行では、ターゲット ノードを検索しています。 この場合、ターゲット値はツリーに存在しません。 最終的に、NULL ノードに到達します。
それ以外の場合は、現在のノードがキーよりも大きいかキーよりも小さいか、または現在のノードがターゲット ノードである (この場合、他の部分に移動します) の 3つのケースがあります。
他の部分では、3つのケースを扱っています。 ターゲット ノードには子ノードがなく、右の子ノードのみ、左の子ノードのみ、左右の子ノードの両方があることは既に説明しました (別の部分で処理されます)。
この部分では、関数 findMinNode を使用して、現在/ターゲット ノードの右側のサブツリーから最小のノードを選択します。 それでは、BST のクラス全体を見てください。
#include <iostream>
using namespace std;
template <class T>
class Node {
public:
T data;
Node* left;
Node* right;
Node(T data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
template <class T>
class BST {
Node<T>* root;
public:
BST() { root = NULL; }
Node<T>* insert(T key) { root = insert(root, key); }
Node<T>* insert(Node<T>* temp, T key) {
if (temp == NULL) return new Node<T>(key);
if (temp->data > key)
temp->left = insert(temp->left, key);
else
temp->right = insert(temp->right, key);
return temp;
}
Node<T>* findMinNode(Node<T>* temp) {
while (temp->left != NULL) temp = temp->left;
return temp;
}
Node<T>* deleteNode(T key) { root = deleteNode(root, key); }
Node<T>* deleteNode(Node<T>* temp, T key) {
if (temp == NULL) return temp;
if (temp->data > key)
temp->left = deleteNode(temp->left, key);
else if (temp->data < key)
temp->right = deleteNode(temp->right, key);
else {
if (temp->left == NULL && temp->right == NULL) {
delete temp;
temp = NULL;
} else if (temp->left == NULL) {
Node<T>* curr = temp;
temp = temp->right;
delete curr;
} else if (temp->right == NULL) {
Node<T>* curr = temp;
temp = temp->left;
delete curr;
} else {
Node<T>* toBeDeleted = findMinNode(temp->right);
temp->data = toBeDeleted->data;
temp->right = deleteNode(temp->right, toBeDeleted->data);
}
}
return temp;
}
void preOrder() {
preOrder(root);
cout << '\n';
}
void preOrder(Node<T>* temp) {
if (temp == NULL) return;
cout << temp->data << " ";
preOrder(temp->left);
preOrder(temp->right);
}
void inOrder() {
inOrder(root);
cout << '\n';
}
void inOrder(Node<T>* temp) {
if (temp == NULL) return;
inOrder(temp->left);
cout << temp->data << " ";
inOrder(temp->right);
}
};
int main() {
BST<int> tree;
tree.insert(40);
tree.insert(22);
tree.insert(15);
tree.insert(67);
tree.insert(34);
tree.insert(90);
tree.preOrder();
tree.inOrder();
tree.deleteNode(40);
cout << "After deleting 40 temp from the tree\n";
tree.preOrder();
tree.inOrder();
return 0;
}
inOrder と preOrder トラバーサル関数を備えた BST クラス全体があり、ツリーの形状を確認できます。 BST は、インオーダーおよびプリオーダー トラバーサル、またはインオーダーおよびポストオーダー トラバーサルから構築できます。 この記事を読むことができます。
コードの出力を見てみましょう。
40 22 15 34 67 90
15 22 34 40 67 90
After deleting 40 temp from the tree
67 22 15 34 90
15 22 34 67 90
この出力では、1 行目には事前順序走査があり、2 行目には順序走査があります。 まず第一に、インオーダー BST は常にソートされた要素を提供します。
したがって、2 行目で、コードが適切に挿入を行っていることが何らかの形で確認されます。
最初の 2 行 (トラバーサル) から二分木を構築できます。 事前注文は常にルート ノードから走査を開始します。 したがって、40 がルート ノードです。
40 が順番にトラバーサルされている場合 (2 行目)、バイナリ ツリーを左右のサブツリーに分割できます。ここで、67 と 90 は右のサブツリーにあり、15 はサブツリーにあります。 、22、および 34 は左サブツリーにあります。 同様に、残りの二分木を完成させることができます。 最後に、二分木は次のとおりです。
40 / 22 67 / \ 15 34 90
このバイナリ ツリーには BST のプロパティがあり、コードが正常に動作していることを示しています。 同様に、40 を削除した後、二分木を構築できます。
67 / 22 90 / 15 34
ノード 40 はターゲット ノードで、左右両方の子ノードがあります。 67 には左の子がないため、右のサブツリーから最も左にある 67 を選択しました。 したがって、ターゲットノードで値67をコピーし、delete関数を再度呼び出して、ルートの右側のサブツリーから67を削除しました。
ここで、67 が唯一の右の子 90 を持つ場合があります。 したがって、90 を 67 に置き換えます。 その結果、90 は 67 の右の子になります。
ファイルを C++ の二分探索木に読み込む
最後に、BST へのファイルの読み取りについて説明します。 繰り返しますが、段階的に実行します。
まず、次のファイルを考えます。
This is first line.
This is second line.
This is third line.
This is fourth line.
This is fifth line.
This is sixth line.
This is seventh line.
This is eighth line.
getline 関数を使用して、C++ でこのファイルを簡単に読み取ることができます。 コードを参照してください：
#include <fstream>
#include <iostream>
using namespace std;
int main() {
ifstream in("sample.txt");
string s;
while (getline(in, s)) cout << s << '\n';
in.close();
}
前のボックスのファイルの内容と同じ出力が得られます。 ただし、私たちの目的は、テキストを BST に配置して、より高速な検索を実行できるようにすることです。
簡単です。 クラス テンプレートには既に BST が実装されており、文字列にも使用できます。 それに応じて BST のオブジェクトを作成するだけです。
ファイル sample.txt にコンテンツを保存して、コードを介してファイルを読み取ることができます。 ここに、ファイルを二分探索木に読み込むコードがあります。
#include <fstream>
#include <iostream>
using namespace std;
template <class T>
class Node {
public:
T data;
Node* left;
Node* right;
Node(T data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
template <class T>
class BST {
Node<T>* root;
public:
BST() { root = NULL; }
Node<T>* insert(T key) { root = insert(root, key); }
Node<T>* insert(Node<T>* temp, T key) {
if (temp == NULL) return new Node<T>(key);
if (temp->data > key)
temp->left = insert(temp->left, key);
else
temp->right = insert(temp->right, key);
return temp;
}
Node<T>* findMinNode(Node<T>* temp) {
while (temp->left != NULL) temp = temp->left;
return temp;
}
Node<T>* deleteNode(T key) { root = deleteNode(root, key); }
Node<T>* deleteNode(Node<T>* temp, T key) {
if (temp == NULL) return temp;
if (temp->data > key)
temp->left = deleteNode(temp->left, key);
else if (temp->data < key)
temp->right = deleteNode(temp->right, key);
else {
if (temp->left == NULL && temp->right == NULL) {
delete temp;
temp = NULL;
} else if (temp->left == NULL) {
Node<T>* curr = temp;
temp = temp->right;
delete curr;
} else if (temp->right == NULL) {
Node<T>* curr = temp;
temp = temp->left;
delete curr;
} else {
Node<T>* toBeDeleted = findMinNode(temp->right);
temp->data = toBeDeleted->data;
temp->right = deleteNode(temp->right, toBeDeleted->data);
}
}
return temp;
}
void preOrder() {
preOrder(root);
cout << '\n';
}
void preOrder(Node<T>* temp) {
if (temp == NULL) return;
cout << temp->data << " ";
preOrder(temp->left);
preOrder(temp->right);
}
void inOrder() {
inOrder(root);
cout << '\n';
}
void inOrder(Node<T>* temp) {
if (temp == NULL) return;
inOrder(temp->left);
cout << temp->data << " ";
inOrder(temp->right);
}
};
int main() {
BST<string> tree;
ifstream in("sample.txt");
string s;
while (getline(in, s)) tree.insert(s);
tree.preOrder();
tree.inOrder();
in.close();
return 0;
}
出力：
繰り返しますが、最初に、ルート ノードが This is the first line であることを示す preorder traversal があります。 ただし、順序通りのトラバーサルが見られる場合は、ソートされた順序で出力されます。
つまり、first、second、third、fourth、fifth、sixth、seventh、eighth のうち最小の文字 e から始まる eightth に対して、 次に、fifth の f が first の r よりも小さいため、fifth は first よりも小さいです。