AVL木
ランダムなAVL木から始めて、値の挿入・検索・削除をステップごとに確認します。各ノードの平衡係数、LL・RR・LR・RL回転、配列表現、ハイライトされたC++コードを表示します。
すべてこのブラウザ内でシミュレートされ、サーバーには一切送信されません。
ステップなし
ステップなし
AVL木
配列インデックス · 平衡係数
配列表現
インデックスiの子は2i+1と2i+2にあります。
- 無関係
- 通過済み
- 比較中
- 発見
- 新規
- 削除対象
- 後続ノード
- 不均衡
- ピボット
ステップなし
コード
#include <iostream>
#include <algorithm>
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; }
};
int height(Node* n) { // 高さ: 葉は 1、空きの位置(nullptr)は 0
if (n == nullptr) return 0;
return 1 + max(height(n->getLeft()), height(n->getRight()));
}
int balanceFactor(Node* n) { // バランス係数: 左の高さ - 右の高さ
return height(n->getLeft()) - height(n->getRight());
}
Node* rotateRight(Node* y) { // 右単回転: 左の子 x が上がり、y が下がります
Node* x = y->getLeft();
y->setLeft(x->getRight());
x->setRight(y);
return x;
}
Node* rotateLeft(Node* x) { // 左単回転: 右の子 y が上がり、x が下がります
Node* y = x->getRight();
x->setRight(y->getLeft());
y->setLeft(x);
return y;
}
Node* rebalance(Node* n) { // バランスを取った部分木の根を返します
int bf = balanceFactor(n); // ノードのバランス係数を計算します
if (bf > 1) { // 左に偏っています。左の子が右に偏っていなければ LL ケースです
if (balanceFactor(n->getLeft()) < 0) // 左の子が右に偏っています: LR ケース、先に左回転します
n->setLeft(rotateLeft(n->getLeft())); // LR ケースの1回目の回転
return rotateRight(n); // 右回転: LL と LR の後半を解決します
}
if (bf < -1) { // 右に偏っています。右の子が左に偏っていなければ RR ケースです
if (balanceFactor(n->getRight()) > 0) // 右の子が左に偏っています: RL ケース、先に右回転します
n->setRight(rotateRight(n->getRight())); // RL ケースの1回目の回転
return rotateLeft(n); // 左回転: RR と RL の後半を解決します
}
return n; // 係数が -1 から 1 の間: 回転は不要です
}
Node* insert(Node* root, int v) { // v を AVL 木に挿入し、根を返します
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 rebalance(root); // 各呼び出しから戻る際に、ノードのバランスを確認します
}
int main() {
Node* root = buildTree(); // 表示中の木(構築済み)
root = insert(root, v); // main からの最初の呼び出し
return 0; // 操作の終了
}