被裁的：

写 CRUD 的 → AI 直接替代
执行需求的 → AI 更快更便宜
不理解业务的外包 → 第一批走人
靠记忆力吃饭的 → AI 记得比你多

ai 给你加速

但判断是你的

---

真实情况

会提问的人 → 很多
看得懂答案的人 → 少一半
能验证对错的人 → 少一半
能改进落地的人 → 剩不多了

你今天让我改代码，每次我说错了你能指出来。

这才是值钱的地方。

---

AI 是工具，工具人人都有。

会用工具的人值钱，工具本身不值钱。

锤子人人买得到，但会盖房子的人还是稀缺。

include

include

include

// ====== Key-Value 对 ======
template
struct Pair
{
K first;
V second;

Pair() {}
Pair(const K& k, const V& v) : first(k), second(v) {}

bool operator< (const Pair& other) const { return first <  other.first; }
bool operator> (const Pair& other) const { return first >  other.first; }
bool operator==(const Pair& other) const { return first == other.first; }
bool operator!=(const Pair& other) const { return first != other.first; }

};

// ====== AVL 树节点 ======
template
struct CAVLNode
{
TYPE m_Element;
int m_nHeight;
CAVLNode* m_pLeft;
CAVLNode* m_pRight;
CAVLNode* m_pParent;

CAVLNode(const TYPE& data)
    : m_Element(data), m_nHeight(1),
      m_pLeft(nullptr), m_pRight(nullptr), m_pParent(nullptr) {}

};

// ====== AVL 树（自平衡二叉搜索树）======
template
class CAVLTree
{
private:
CAVLNode* m_pRoot;
int m_nSize;

int Height(CAVLNode<TYPE>* pNode) const
{
    return pNode ? pNode->m_nHeight : 0;
}

int Max(int a, int b) const { return a > b ? a : b; }

// 获取平衡因子
int BalanceFactor(CAVLNode<TYPE>* pNode) const
{
    return pNode ? Height(pNode->m_pLeft) - Height(pNode->m_pRight) : 0;
}

// 更新节点高度
void UpdateHeight(CAVLNode<TYPE>* pNode)
{
    if (pNode)
        pNode->m_nHeight = 1 + Max(Height(pNode->m_pLeft), Height(pNode->m_pRight));
}

// ====== 旋转操作 ======

// LL 右单旋
CAVLNode<TYPE>* RotateLL(CAVLNode<TYPE>* pNode)
{
    CAVLNode<TYPE>* pLeft = pNode->m_pLeft;
    pNode->m_pLeft = pLeft->m_pRight;
    if (pLeft->m_pRight)
        pLeft->m_pRight->m_pParent = pNode;
    pLeft->m_pRight = pNode;
    pLeft->m_pParent = pNode->m_pParent;
    pNode->m_pParent = pLeft;
    UpdateHeight(pNode);
    UpdateHeight(pLeft);
    return pLeft;
}

// RR 左单旋
CAVLNode<TYPE>* RotateRR(CAVLNode<TYPE>* pNode)
{
    CAVLNode<TYPE>* pRight = pNode->m_pRight;
    pNode->m_pRight = pRight->m_pLeft;
    if (pRight->m_pLeft)
        pRight->m_pLeft->m_pParent = pNode;
    pRight->m_pLeft = pNode;
    pRight->m_pParent = pNode->m_pParent;
    pNode->m_pParent = pRight;
    UpdateHeight(pNode);
    UpdateHeight(pRight);
    return pRight;
}

// LR 双旋：先左旋左子，再右旋自身
CAVLNode<TYPE>* RotateLR(CAVLNode<TYPE>* pNode)
{
    pNode->m_pLeft = RotateRR(pNode->m_pLeft);
    return RotateLL(pNode);
}

// RL 双旋：先右旋右子，再左旋自身
CAVLNode<TYPE>* RotateRL(CAVLNode<TYPE>* pNode)
{
    pNode->m_pRight = RotateLL(pNode->m_pRight);
    return RotateRR(pNode);
}

// 平衡调整
CAVLNode<TYPE>* Balance(CAVLNode<TYPE>* pNode)
{
    UpdateHeight(pNode);

    int bf = BalanceFactor(pNode);

    // LL
    if (bf > 1 && BalanceFactor(pNode->m_pLeft) >= 0)
        return RotateLL(pNode);

    // LR
    if (bf > 1 && BalanceFactor(pNode->m_pLeft) < 0)
        return RotateLR(pNode);

    // RR
    if (bf < -1 && BalanceFactor(pNode->m_pRight) <= 0)
        return RotateRR(pNode);

    // RL
    if (bf < -1 && BalanceFactor(pNode->m_pRight) > 0)
        return RotateRL(pNode);

    return pNode;
}

// 插入（递归）
CAVLNode<TYPE>* Insert(CAVLNode<TYPE>* pNode, const TYPE& data, CAVLNode<TYPE>* parent)
{
    if (!pNode)
    {
        m_nSize++;
        return new CAVLNode<TYPE>(data);
    }

    if (data < pNode->m_Element)
    {
        pNode->m_pLeft = Insert(pNode->m_pLeft, data, pNode);
        if (pNode->m_pLeft) pNode->m_pLeft->m_pParent = pNode;
    }
    else if (data > pNode->m_Element)
    {
        pNode->m_pRight = Insert(pNode->m_pRight, data, pNode);
        if (pNode->m_pRight) pNode->m_pRight->m_pParent = pNode;
    }
    else
    {
        // 重复数据，不做任何操作
        return pNode;
    }

    return Balance(pNode);
}

// 找最小节点
CAVLNode<TYPE>* FindMin(CAVLNode<TYPE>* pNode) const
{
    if (!pNode) return nullptr;
    while (pNode->m_pLeft)
        pNode = pNode->m_pLeft;
    return pNode;
}

// 找最大节点
CAVLNode<TYPE>* FindMax(CAVLNode<TYPE>* pNode) const
{
    if (!pNode) return nullptr;
    while (pNode->m_pRight)
        pNode = pNode->m_pRight;
    return pNode;
}

// 删除（递归）
CAVLNode<TYPE>* Remove(CAVLNode<TYPE>* pNode, const TYPE& data)
{
    if (!pNode) return nullptr;

    if (data < pNode->m_Element)
    {
        pNode->m_pLeft = Remove(pNode->m_pLeft, data);
        if (pNode->m_pLeft) pNode->m_pLeft->m_pParent = pNode;
    }
    else if (data > pNode->m_Element)
    {
        pNode->m_pRight = Remove(pNode->m_pRight, data);
        if (pNode->m_pRight) pNode->m_pRight->m_pParent = pNode;
    }
    else
    {
        // 找到要删除的节点
        if (pNode->m_pLeft && pNode->m_pRight)
        {
            // 两个子节点：用右子树最小节点替换
            CAVLNode<TYPE>* pMin = FindMin(pNode->m_pRight);
            pNode->m_Element = pMin->m_Element;
            pNode->m_pRight = Remove(pNode->m_pRight, pMin->m_Element);
            if (pNode->m_pRight) pNode->m_pRight->m_pParent = pNode;
        }
        else
        {
            // 0或1个子节点
            CAVLNode<TYPE>* pChild = pNode->m_pLeft ? pNode->m_pLeft : pNode->m_pRight;
            delete pNode;
            m_nSize--;
            return pChild;
        }
    }

    return Balance(pNode);
}

void MakeEmpty(CAVLNode<TYPE>* pNode)
{
    if (!pNode) return;
    MakeEmpty(pNode->m_pLeft);
    MakeEmpty(pNode->m_pRight);
    delete pNode;
}

void PrintTree(CAVLNode<TYPE>* pNode, int depth = 0) const
{
    if (!pNode) return;
    PrintTree(pNode->m_pRight, depth + 1);
    for (int i = 0; i < depth; i++) printf("      ");
    printf("%d[%d]\n", pNode->m_Element, pNode->m_nHeight);
    PrintTree(pNode->m_pLeft, depth + 1);
}

public:
CAVLTree() : m_pRoot(nullptr), m_nSize(0) {}

~CAVLTree() { MakeEmpty(m_pRoot); }

void Insert(const TYPE& data)
{
    m_pRoot = Insert(m_pRoot, data, nullptr);
}

void Remove(const TYPE& data)
{
    m_pRoot = Remove(m_pRoot, data);
}

CAVLNode<TYPE>* Find(const TYPE& data) const
{
    CAVLNode<TYPE>* pCur = m_pRoot;
    while (pCur)
    {
        if (data == pCur->m_Element) return pCur;
        if (data < pCur->m_Element)
            pCur = pCur->m_pLeft;
        else
            pCur = pCur->m_pRight;
    }
    return nullptr;
}

CAVLNode<TYPE>* GetRoot() const { return m_pRoot; }
int Size() const { return m_nSize; }

void Print() const
{
    printf("  AVL 树 (元素[高度]):\n");
    if (m_pRoot)
        PrintTree(m_pRoot);
    else
        printf("    (空)\n");
    printf("  Size=%d, Height=%d\n\n", m_nSize, m_pRoot ? m_pRoot->m_nHeight : 0);
}

};

// ====== 测试学生结构体 ======
struct Student
{
int m_nID;
char m_szName[32];
float m_fScore;

Student(int id = 0, const char* name = "", float score = 0)
    : m_nID(id), m_fScore(score)
{
    sprintf(m_szName, "%s", name);
}

bool operator< (const Student& other) const { return m_nID <  other.m_nID; }
bool operator> (const Student& other) const { return m_nID >  other.m_nID; }
bool operator==(const Student& other) const { return m_nID == other.m_nID; }

};

void TestBasic()
{
printf(“=== 1. AVL 树基本操作 ===\n”);
CAVLTree tree;

int vals[] = {10, 20, 30, 40, 50, 25};
for (int i = 0; i < 6; i++)
{
    printf("  插入 %d:\n", vals[i]);
    tree.Insert(vals[i]);
}

tree.Print();

}

void TestBalance()
{
printf(“=== 2. 平衡验证 ===\n”);

// 最坏情况：有序插入 → 普通 BST 会退化为链表
// AVL 会自动平衡
CAVLTree<int> tree;
for (int i = 1; i <= 15; i++)
    tree.Insert(i);

printf("  插入有序 1~15:\n");
tree.Print();

printf("  树高: %d  (完全二叉树理论高=4, log2(15)+1)\n\n", tree.GetRoot()->m_nHeight);

}

void TestRemove()
{
printf(“=== 3. 删除操作 ===\n”);
CAVLTree tree;
for (int i = 1; i <= 10; i++)
tree.Insert(i);

tree.Remove(5);
tree.Remove(8);
tree.Remove(1);

printf("  删除 5,8,1 后:\n");
tree.Print();

}

void TestLargeScale()
{
printf(“=== 4. 大规模随机测试 ===\n”);
CAVLTree tree;

srand((unsigned)time(nullptr));
for (int i = 0; i < 10000; i++)
    tree.Insert(rand() % 100000);

printf("  插入 10000 随机数\n");
printf("  Size=%d, Height=%d\n", tree.Size(), tree.GetRoot()->m_nHeight);
printf("  Log2(10000)≈13.3, AVL 树高≈%d\n\n", tree.GetRoot()->m_nHeight);

}

void TestKeyValue()
{
printf(“=== 5. Key-Value 模式 ===\n”);
CAVLTree> tree;

// 按学号排序
Student stu1(101, "张三", 85.5);
Student stu2(102, "李四", 92.0);
Student stu3(103, "王五", 78.5);

tree.Insert(Pair<int, Student>(stu1.m_nID, stu1));
tree.Insert(Pair<int, Student>(stu2.m_nID, stu2));
tree.Insert(Pair<int, Student>(stu3.m_nID, stu3));

printf("  按学号排序:\n");
printf("  树高: %d  (平衡)\n\n", tree.GetRoot()->m_nHeight);

// 查找
auto* found = tree.Find(Pair<int, Student>(102, Student()));
if (found)
    printf("  查找到学号102: %s, 成绩=%.1f\n\n",
           found->m_Element.second.m_szName,
           found->m_Element.second.m_fScore);

}

int main()
{
printf(“=============================================\n”);
printf(” 第41课: AVL 树（自平衡二叉搜索树）\n”);
printf(“=============================================\n\n”);

printf("  平衡方式: 4种旋转\n");
printf("  LL: 右单旋   RR: 左单旋\n");
printf("  LR: 左右双旋 RL: 右左双旋\n\n");

TestBasic();
TestBalance();
TestRemove();
TestLargeScale();
TestKeyValue();

printf("=============================================\n");
printf("  AVL vs BST:\n");
printf("          BST           AVL\n");
printf("  插入    O(n)退化解    O(log n)始终\n");
printf("  删除    O(n)退化解    O(log n)始终\n");
printf("  查找    O(n)退化解    O(log n)始终\n");
return 0;

}