tree_avl.cpp

/*
 * ============================================================================
 *  AVL Tree（平衡二元搜尋樹）— 完整實作
 *  File: tree_avl.cpp
 *
 *  AVL Tree 由 Adelson-Velsky & Landis 於 1962 年提出。
 *  它是一棵 BST，且對每個節點：|height(left) - height(right)| ≤ 1
 *  這保證了高度 h = O(log N)，所有操作最壞 O(log N)。
 *
 *  涵蓋：
 *    1.  節點結構（含高度欄位）
 *    2.  高度與 Balance Factor 計算
 *    3.  四種旋轉：LL(右旋), RR(左旋), LR(先左後右), RL(先右後左)
 *    4.  Insert（插入 + 自動平衡）
 *    5.  Delete（刪除 + 自動平衡）
 *    6.  Search / FindMin / FindMax
 *    7.  Traversals (Inorder, Preorder, Level-order)
 *    8.  視覺化輸出（含 BF 標記）
 *    9.  逐步插入示範（展示每次旋轉）
 *
 *  Compile: g++ -std=c++11 -Wall -o tree_avl tree_avl.cpp
 * ============================================================================
 */

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>

using namespace std;

/* ============================================================================
 *  1. 節點結構
 *
 *  與普通 BST 相比，多存一個 height 欄位。
 *  height 用來計算 Balance Factor (BF) = height(left) - height(right)。
 *  合法的 BF 值：-1, 0, +1。
 * ============================================================================ */
struct AVLNode {
    int data;
    AVLNode* left;
    AVLNode* right;
    int height;  // 以此節點為根的子樹高度

    AVLNode(int val)
        : data(val), left(nullptr), right(nullptr), height(0) {}
};

/* ============================================================================
 *  2. 高度與 Balance Factor
 * ============================================================================ */

// 取得節點高度（nullptr 的高度定義為 -1）
int getHeight(AVLNode* node) {
    if (node == nullptr) return -1;
    return node->height;
}

// 更新節點的高度（根據左右子樹高度）
void updateHeight(AVLNode* node) {
    if (node == nullptr) return;
    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
}

// 計算 Balance Factor
// BF > 0 → 左邊重（left-heavy）
// BF < 0 → 右邊重（right-heavy）
// |BF| > 1 → 需要旋轉
int getBalanceFactor(AVLNode* node) {
    if (node == nullptr) return 0;
    return getHeight(node->left) - getHeight(node->right);
}

/* ============================================================================
 *  3. 四種旋轉
 *
 *  旋轉是 AVL 的核心操作，用來在插入/刪除後恢復平衡。
 *  旋轉的關鍵：改變父子關係，但保持 BST 的排序性質。
 * ============================================================================ */

/*
 * LL Case → 右旋 (Right Rotation)
 *
 * 何時觸發：不平衡節點 BF = +2，其左子 BF ≥ 0
 *
 *       z (+2)           y
 *      / \              / \
 *     y   T4    →      x   z
 *    / \              /   / \
 *   x   T3           T1  T3  T4
 *  / \
 * T1  T2
 *
 * 步驟：
 *   1. y 成為新的 root
 *   2. z 變成 y 的右子
 *   3. y 的原右子 (T3) 變成 z 的左子
 */
AVLNode* rotateRight(AVLNode* z) {
    AVLNode* y  = z->left;     // y = z 的左子，將成為新 root
    AVLNode* T3 = y->right;    // T3 = y 的右子樹，將轉移給 z

    // 執行旋轉
    y->right = z;              // z 變成 y 的右子
    z->left  = T3;             // y 的原右子變成 z 的左子

    // 先更新 z 的高度（因為 z 現在是 y 的子節點）
    updateHeight(z);
    // 再更新 y 的高度
    updateHeight(y);

    return y;  // y 是旋轉後的新 root
}

/*
 * RR Case → 左旋 (Left Rotation)
 *
 * 何時觸發：不平衡節點 BF = -2，其右子 BF ≤ 0
 *
 *   z (-2)               y
 *  / \                  / \
 * T1  y        →       z   x
 *    / \              / \   \
 *   T2  x            T1  T2  T3
 *      / \
 *     T3  T4
 *
 * 步驟：
 *   1. y 成為新的 root
 *   2. z 變成 y 的左子
 *   3. y 的原左子 (T2) 變成 z 的右子
 */
AVLNode* rotateLeft(AVLNode* z) {
    AVLNode* y  = z->right;    // y = z 的右子，將成為新 root
    AVLNode* T2 = y->left;     // T2 = y 的左子樹，將轉移給 z

    // 執行旋轉
    y->left  = z;              // z 變成 y 的左子
    z->right = T2;             // y 的原左子變成 z 的右子

    updateHeight(z);
    updateHeight(y);

    return y;
}

/*
 * 根據 Balance Factor 自動選擇旋轉方式
 *
 * 判斷表：
 * ┌─────────────┬──────────────┬─────────────────────┐
 * │ 節點 BF     │ 子節點 BF    │ 旋轉方式            │
 * ├─────────────┼──────────────┼─────────────────────┤
 * │ +2 (左重)   │ ≥ 0 (左子左重)│ LL → 右旋           │
 * │ +2 (左重)   │ < 0 (左子右重)│ LR → 左旋左子+右旋  │
 * │ -2 (右重)   │ ≤ 0 (右子右重)│ RR → 左旋           │
 * │ -2 (右重)   │ > 0 (右子左重)│ RL → 右旋右子+左旋  │
 * └─────────────┴──────────────┴─────────────────────┘
 */
AVLNode* balance(AVLNode* node) {
    if (node == nullptr) return nullptr;

    updateHeight(node);
    int bf = getBalanceFactor(node);

    // 左邊太重 (BF = +2)
    if (bf > 1) {
        if (getBalanceFactor(node->left) >= 0) {
            // LL Case: 左子也是左重或平衡 → 單右旋
            cout << "    [LL rotation at " << node->data << "]" << endl;
            return rotateRight(node);
        } else {
            // LR Case: 左子是右重 → 先對左子左旋，再對自己右旋
            cout << "    [LR rotation at " << node->data << "]" << endl;
            node->left = rotateLeft(node->left);
            return rotateRight(node);
        }
    }

    // 右邊太重 (BF = -2)
    if (bf < -1) {
        if (getBalanceFactor(node->right) <= 0) {
            // RR Case: 右子也是右重或平衡 → 單左旋
            cout << "    [RR rotation at " << node->data << "]" << endl;
            return rotateLeft(node);
        } else {
            // RL Case: 右子是左重 → 先對右子右旋，再對自己左旋
            cout << "    [RL rotation at " << node->data << "]" << endl;
            node->right = rotateRight(node->right);
            return rotateLeft(node);
        }
    }

    // |BF| ≤ 1 → 已平衡，不需要旋轉
    return node;
}

/* ============================================================================
 *  4. Insert（插入 + 自動平衡）
 *
 *  流程：
 *    1. 像普通 BST 一樣遞迴插入（新節點成為 leaf）
 *    2. 回溯時更新高度、檢查 BF
 *    3. 若 |BF| > 1 → 執行旋轉
 *    4. 插入最多只需要一次旋轉（單旋或雙旋）
 *
 *  時間：O(log N)
 * ============================================================================ */
AVLNode* insert(AVLNode* node, int key) {
    // 標準 BST 插入
    if (node == nullptr) {
        return new AVLNode(key);
    }

    if (key < node->data) {
        node->left = insert(node->left, key);
    } else if (key > node->data) {
        node->right = insert(node->right, key);
    } else {
        return node;  // 不允許重複
    }

    // 回溯時：更新高度 + 平衡檢查 + 旋轉
    return balance(node);
}

/* ============================================================================
 *  5. Delete（刪除 + 自動平衡）
 *
 *  流程：
 *    1. 像普通 BST 一樣刪除（三種情況）
 *    2. 回溯時更新高度、檢查 BF
 *    3. 若 |BF| > 1 → 執行旋轉
 *    4. 與插入不同：刪除可能需要多次旋轉（沿路徑回溯每層都可能旋轉）
 *
 *  時間：O(log N)
 * ============================================================================ */

// 找最小值（用於刪除 Case 3）
AVLNode* findMin(AVLNode* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

AVLNode* deleteNode(AVLNode* node, int key) {
    if (node == nullptr) return nullptr;

    if (key < node->data) {
        node->left = deleteNode(node->left, key);
    } else if (key > node->data) {
        node->right = deleteNode(node->right, key);
    } else {
        // 找到要刪除的節點

        // Case 1 & 2: 0 或 1 個 child
        if (node->left == nullptr || node->right == nullptr) {
            AVLNode* child = (node->left != nullptr) ? node->left : node->right;
            delete node;
            return balance(child);  // child 可能是 nullptr (leaf case)
        }

        // Case 3: 兩個 children → 用中序後繼取代
        AVLNode* successor = findMin(node->right);
        node->data = successor->data;
        node->right = deleteNode(node->right, successor->data);
    }

    // 回溯時平衡
    return balance(node);
}

/* ============================================================================
 *  6. Search
 * ============================================================================ */
bool search(AVLNode* node, int key) {
    if (node == nullptr) return false;
    if (key == node->data) return true;
    if (key < node->data) return search(node->left, key);
    return search(node->right, key);
}

/* ============================================================================
 *  7. Traversals
 * ============================================================================ */
void inorder(AVLNode* node) {
    if (node == nullptr) return;
    inorder(node->left);
    cout << node->data << " ";
    inorder(node->right);
}

void preorder(AVLNode* node) {
    if (node == nullptr) return;
    cout << node->data << " ";
    preorder(node->left);
    preorder(node->right);
}

void levelOrder(AVLNode* root) {
    if (root == nullptr) return;
    queue<AVLNode*> q;
    q.push(root);

    while (!q.empty()) {
        int sz = (int)q.size();
        for (int i = 0; i < sz; ++i) {
            AVLNode* cur = q.front();
            q.pop();
            cout << cur->data << "(h=" << cur->height
                 << ",bf=" << getBalanceFactor(cur) << ") ";
            if (cur->left)  q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        cout << "| ";
    }
    cout << endl;
}

/* ============================================================================
 *  8. 視覺化輸出（含高度和 BF）
 * ============================================================================ */
void printTree(AVLNode* node, const string& prefix = "", bool isLeft = true) {
    if (node == nullptr) return;

    if (node->right) {
        printTree(node->right, prefix + (isLeft ? "│   " : "    "), false);
    }

    cout << prefix;
    cout << (isLeft ? "└── " : "┌── ");
    cout << node->data
         << " [h=" << node->height
         << " bf=" << getBalanceFactor(node) << "]" << endl;

    if (node->left) {
        printTree(node->left, prefix + (isLeft ? "    " : "│   "), true);
    }
}

/* ============================================================================
 *  釋放記憶體
 * ============================================================================ */
void deleteTree(AVLNode* node) {
    if (node == nullptr) return;
    deleteTree(node->left);
    deleteTree(node->right);
    delete node;
}

/* ============================================================================
 *  9. 主程式 — 逐步插入示範
 * ============================================================================ */
int main() {
    cout << "============================================" << endl;
    cout << "  AVL Tree (Balanced BST) Complete Demo" << endl;
    cout << "============================================\n" << endl;

    AVLNode* root = nullptr;

    // ── 逐步插入，展示每次旋轉 ──
    cout << "--- Step-by-step Insertion ---\n" << endl;

    int keys[] = {10, 20, 30, 40, 50, 25};

    for (int key : keys) {
        cout << "Insert " << key << ":" << endl;
        root = insert(root, key);
        printTree(root);
        cout << endl;
    }

    /*
     * 插入過程的旋轉：
     *   Insert 10: 無旋轉
     *   Insert 20: 無旋轉
     *   Insert 30: 10 的 BF = -2 → RR 左旋 → root = 20
     *   Insert 40: 無旋轉
     *   Insert 50: 30 的 BF = -2 → RR 左旋
     *   Insert 25: 20 的 BF = -2, 右子 40 的 BF = +1 → RL 旋轉
     */

    // ── 遍歷 ──
    cout << "--- Traversals ---\n" << endl;

    cout << "Inorder (sorted): ";
    inorder(root);
    cout << endl;

    cout << "Preorder:          ";
    preorder(root);
    cout << endl;

    cout << "Level-order (with height & BF):" << endl;
    levelOrder(root);
    cout << endl;

    // ── 搜尋 ──
    cout << "--- Search ---\n" << endl;
    cout << "search(25) = " << (search(root, 25) ? "true" : "false") << endl;
    cout << "search(99) = " << (search(root, 99) ? "true" : "false") << endl;
    cout << endl;

    // ── 更多插入 ──
    cout << "--- Insert more: 15, 5, 35, 45, 55, 3, 7 ---\n" << endl;
    int more[] = {15, 5, 35, 45, 55, 3, 7};
    for (int key : more) {
        cout << "Insert " << key << ":" << endl;
        root = insert(root, key);
    }
    printTree(root);
    cout << endl;

    cout << "Inorder: ";
    inorder(root);
    cout << "\n" << endl;

    // ── 刪除 ──
    cout << "--- Deletion ---\n" << endl;

    // 刪除 leaf
    cout << "Delete 3 (leaf):" << endl;
    root = deleteNode(root, 3);
    printTree(root);
    cout << endl;

    // 刪除有一個 child 的節點
    cout << "Delete 55 (one child or leaf):" << endl;
    root = deleteNode(root, 55);
    printTree(root);
    cout << endl;

    // 刪除有兩個 children 的節點
    cout << "Delete 30 (two children, root-area):" << endl;
    root = deleteNode(root, 30);
    printTree(root);
    cout << endl;

    cout << "Inorder after deletions: ";
    inorder(root);
    cout << endl;

    // ── 驗證平衡 ──
    cout << "\n--- Verify Balance ---\n" << endl;
    cout << "Level-order (all BF should be -1, 0, or +1):" << endl;
    levelOrder(root);

    // 清理
    deleteTree(root);

    cout << "\n============================================" << endl;
    cout << "  Done." << endl;
    cout << "============================================" << endl;

    return 0;
}