C++によるスレッド化二分木の実装
スレッド化二分木（Threaded Binary Tree）は、特定の順序で木を走査する機能を提供する二分木の一種です。この構造を用いると、スタックや再帰を使用せずに中順走査（inorder traversal）を高速に行うことができます。
スレッド化二分木の種類
単一スレッド（Single Threaded）
各ノードが左または右のいずれか一方にスレッドを持つ構造です。つまり、中順走査における前駆ノード（inorder predecessor）または後続ノード（inorder successor）へのポインタを保持します。すべての右のNULLポインタが中順後続を指すか、またはすべての左のNULLポインタが中順前駆を指します。
二重スレッド（Double Threaded）
各ノードが左右両方にスレッドを持つ構造です。中順前駆と中順後続の両方へのポインタを保持します。すべての右のNULLポインタが中順後続を指し、すべての左のNULLポインタが中順前駆を指します。
主要関数と擬似コード
insert() 関数
木が完全に空の場合、ノードをルートとして挿入する。
それ以外の場合、newnode < 現在のノードなら
左スレッドへ進み、newnodeを左の子として設定する。
そうでなければ
右スレッドへ進み、newnodeを右の子として設定する。search() 関数
検索キー < ルートなら
左スレッドへ進む
そうでなければ
右スレッドへ進むdelete() 関数
対象ノードとその親ノードを特定します。削除対象のノードには以下の3つのケースがあります。
- 2つの子を持つノード
- 左の子のみを持つノード
- 右の子のみを持つノード
C++ 実装例
#include <iostream>
#include <cstdlib>
#define MAX_VALUE 65536
using namespace std;
class Node { // ノード宣言
public:
int key;
Node *left, *right;
bool leftThread, rightThread;
};
class ThreadedBinaryTree {
private:
Node *root;
public:
ThreadedBinaryTree() { // コンストラクタで変数を初期化
root = new Node();
root->right = root->left = root;
root->leftThread = true;
root->key = MAX_VALUE;
}
void makeEmpty() { // 木をクリア
root = new Node();
root->right = root->left = root;
root->leftThread = true;
root->key = MAX_VALUE;
}
void insert(int key) {
Node *p = root;
for (;;) {
if (p->key < key) { // 右スレッドへ移動
if (p->rightThread)
break;
p = p->right;
} else if (p->key > key) { // 左スレッドへ移動
if (p->leftThread)
break;
p = p->left;
} else {
return; // 重複キーは挿入しない
}
}
Node *temp = new Node();
temp->key = key;
temp->rightThread = temp->leftThread = true;
if (p->key < key) {
temp->right = p->right;
temp->left = p;
p->right = temp;
p->rightThread = false;
} else {
temp->right = p;
temp->left = p->left;
p->left = temp;
p->leftThread = false;
}
}
bool search(int key) {
Node *temp = root->left;
for (;;) {
if (temp->key < key) { // 右スレッドで検索
if (temp->rightThread)
return false;
temp = temp->right;
} else if (temp->key > key) { // 左スレッドで検索
if (temp->leftThread)
return false;
temp = temp->left;
} else {
return true;
}
}
}
void Delete(int key) {
Node *dest = root->left, *parent = root;
for (;;) { // ノードとその親を検索
if (dest->key < key) {
if (dest->rightThread)
return;
parent = dest;
dest = dest->right;
} else if (dest->key > key) {
if (dest->leftThread)
return;
parent = dest;
dest = dest->left;
} else {
break;
}
}
Node *target = dest;
// ケース1: 2つの子を持つ場合
if (!dest->rightThread && !dest->leftThread) {
parent = dest;
target = dest->left; // 左部分木の最大ノード
while (!target->rightThread) {
parent = target;
target = target->right;
}
dest->key = target->key; // キーを置き換え
}
// ケース2・3: 片方の子のみ、または子を持たない場合
if (parent->key >= target->key) { // 左の子として接続されていた場合
if (target->rightThread && target->leftThread) { // 子を持たない
parent->left = target->left;
parent->leftThread = true;
} else if (target->rightThread) { // 左の子のみ
Node *largest = target->left;
while (!largest->rightThread) {
largest = largest->right;
}
largest->right = parent;
parent->left = target->left;
} else { // 右の子のみ
Node *smallest = target->right;
while (!smallest->leftThread) {
smallest = smallest->left;
}
smallest->left = target->left;
parent->left = target->right;
}
} else { // 右の子として接続されていた場合
if (target->rightThread && target->leftThread) { // 子を持たない
parent->right = target->right;
parent->rightThread = true;
} else if (target->rightThread) { // 左の子のみ
Node *largest = target->left;
while (!largest->rightThread) {
largest = largest->right;
}
largest->right = target->right;
parent->right = target->left;
} else { // 右の子のみ
Node *smallest = target->right;
while (!smallest->leftThread) {
smallest = smallest->left;
}
smallest->left = parent;
parent->right = target->right;
}
}
}
void displayTree() { // 木を中順走査で表示
Node *temp = root, *prev;
for (;;) {
prev = temp;
temp = temp->right;
if (!prev->rightThread) {
while (!temp->leftThread) {
temp = temp->left;
}
}
if (temp == root)
break;
cout << temp->key << " ";
}
cout << endl;
}
};
int main() {
ThreadedBinaryTree tbt;
cout << "Threaded Binary Tree\n";
char ch;
int choice, value;
while (true) {
cout << "1. Insert\n";
cout << "2. Delete\n";
cout << "3. Search\n";
cout << "4. Clear\n";
cout << "5. Display\n";
cout << "6. Exit\n";
cout << "Enter Your Choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter integer element to insert: ";
cin >> value;
tbt.insert(value);
break;
case 2:
cout << "Enter integer element to delete: ";
cin >> value;
tbt.Delete(value);
break;
case 3:
cout << "Enter integer element to search: ";
cin >> value;
if (tbt.search(value))
cout << "Element " << value << " found in the tree" << endl;
else
cout << "Element " << value << " not found in the tree" << endl;
break;
case 4:
cout << "\nTree Cleared\n";
tbt.makeEmpty();
break;
case 5:
cout << "Display tree: \n ";
tbt.displayTree();
break;
case 6:
exit(0);
default:
cout << "\nInvalid choice! \n";
}
}
return 0;
}実行結果の例
Threaded Binary Tree
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 10
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 7
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 6
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 4
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 5
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 3
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 5
Display tree
3 4 5 6 7 10
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 3
Enter integer element to search: 7
Element 7 found in the tree
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 3
Enter integer element to search: 1
Element 1 not found in the tree
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 2
Enter integer element to delete: 3
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 5
Display tree
4 5 6 7 10
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 4
Tree Cleared
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 5
Display tree
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 6-
C++で二分木を剪定する：1を含まない部分木を削除する再帰アルゴリズム
問題概要二分木のルートノード root が与えられ、すべてのノードの値は 0 または 1 のいずれかであるとします。この木から、1 を含まないすべての部分木を削除した結果の木を求めるのが目的です。たとえば、次のような木が与えられた場合 −解決のためのアプローチこの問題は、再帰的な手法を用いて以下の手順で解決できます −ノードを引数として受け取る再帰メソッド solve() を定義します。処理の流れは次のとおりです −ノードが null の場合は、null を返しますノードの左の子に対して solve(左の子) を実行し、その結果を左の子に代入しますノードの右の子に対して solve(右の子)
-
C++でAVL木（AVLツリー）を実装する方法：回転操作とサンプルコードを徹底解説
AVL木とは AVL木（AVL Tree）は、自己平衡型二分探索木（Self-balancing Binary Search Tree）の一種です。すべてのノードにおいて、左部分木と右部分木の高さの差が「1以下」に保たれるという性質を持っています。この平衡条件により、木が片側に偏って成長することを防ぎ、検索・挿入・削除といった操作を常に効率的（O(log n)）に行うことができます。 木の回転（Tree Rotation）とは 木の回転とは、要素の順序（ソート順）を崩すことなく木の構造を変更する操作のことです。あるノードを一段上へ移動させ、別のノードを一段下へ移動させることで実現されます。 回