二分探索木（BST）
ランダムな二分探索木から始めて、値の挿入・検索・削除をステップごとに確認します。配列表現とハイライトされたC++コードも表示します。
すべてこのブラウザ内でシミュレートされ、サーバーには一切送信されません。
ステップなし
ステップなし
二分探索木
配列インデックス
配列表現
インデックスiの子は2i+1と2i+2にあります。
- 無関係
- 通過済み
- 比較中
- 発見
- 新規
- 削除対象
- 後続ノード
ステップなし
コード
#include <iostream>
using namespace std;
class Node { // ノードは値と2つの子へのポインタを保持します
private: // プライベート属性:メソッドだけが触れます
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
Node* insert(Node* root, int v) { // v を探索木に挿入し、根を返します
if (root == nullptr) // 空きの位置: 新しいノードはここに入ります
return new Node(v); // 新しいノードを作成します
if (v < root->getValue()) // 小さい値は左へ、大きい値は右へ進みます
root->setLeft(insert(root->getLeft(), v)); // 左の部分木を下ります
else
root->setRight(insert(root->getRight(), v)); // 右の部分木を下ります
return root;
}
int main() {
Node* root = buildTree(); // 表示中の木(構築済み)
root = insert(root, v); // main からの最初の呼び出し
return 0; // 操作の終了
}