> For the complete documentation index, see [llms.txt](https://linlh.gitbook.io/cs-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://linlh.gitbook.io/cs-notes/yu-yan-suan-fa-xiang-guan/ping-heng-er-cha-shu-avl.md).

# 平衡二叉树AVL

很多时候学习数据结构的时候，刚开始觉得还可以接受，到了树和图的话，就慢慢劝退了。很多时候我们觉得这个东西很难，但是实际情况呢，嗯。。它真的挺难的，但是因为它难，学习上没有及时的收获感，导致我们学而止步了。但是呢，有阻力才代表我们在上升。王强老师之前在演讲的时候说到一个例子，形式逻辑的三段论来验证他可以学好计算机，大前提是计算机是人发明的东西，小前提是人都应该懂人发明的东西，王强搞不懂计算机，结论：王强肯定不是人。虽然不是真理哈，但是也表明了我们对于学习的态度问题，既然难，说明这个内容它是包含了更多前人的智慧，老一辈花了几年几十年总结出来的内容，我们如果要求自己一两遍就弄懂，其实也不太现实（排除特别优秀的同学），所以要多给自己一点耐心，没弄懂，不是自己没有天赋，而是自己花的时间还不够多。

AVL树的难点在于旋转问题，保证整棵树是平衡的，关于AVL树相关的概率这里不再重复，相关的数据都可以找到介绍。

旋转分为四种情况：

1. 左旋
2. 右旋
3. 先左旋后右旋
4. 先右旋后左旋

## 代码实现

### 结点

```cpp
// 定义结点，内容很清晰，结点值，左右结点指针
struct node {
    int val;
    struct node *left, *right;
};
```

### 左旋

左旋图示：

![](/files/-M92fr0Pnij-xSo0qlAx)

左旋代码：

```cpp
// root为上图的结点1，t为上图的结点2，t为旋转后的新的root结点
node *rotateLeft(node *root) {
    node *t = root->right; // 当前root的右孩子作为新的root，t为新的root结点
    // 由于结点2的左旋上去后，root作为它的左孩子，那么原来结点2的左孩子放到root的右孩子上
    root->right = t->left; 
    t->left = root; // 原来的root结点放到新root结点t的左孩子上
    return t;
}
```

### 右旋

右旋图示：

![](/files/-M92chAlHPYXayWlzmnd)

右旋代码：

```cpp
// root为上图的结点3，t为上图的结点2，t为旋转后的新的root结点
node *rotateRight(node *root) {
    node *t = root->left;  // 右旋是root的左孩子作为新的root
    // 由于结点2的右旋上去后，root作为它的右孩子，那么原来结点2的右孩子放到root的左孩子上
    root->left = t->right; 
    t->right = root; // 原来的root结点放到新root结点t的右孩子上
    return t;
}
```

### 先左旋后右旋

图示：

![](/files/-M92nZlCEflrph2IHRql)

代码：

```cpp
// 代码很明确的，先将root的左孩子左旋，然后root再右旋
node *rotateLeftRight(node *root) {
    root->left = rotateLeft(root->left);
    return rotateRight(root);
}
```

### 先右旋后左旋

图示：

![](/files/-M92mDfah8hgcQgsVkZ0)

代码：

```cpp
// 代码很明确的，先将root的右孩子右旋，然后root再左旋
node *rotateRightLeft(node *root) {
    root->right = rotateRight(root->right);
    return rotateLeft(root);
}
```

我们可以看到，在对于旋转的代码上实现是比较明确的，结合图例很好理解，难点在于我们插入的时候根据什么来判断要进行何种旋转，下面我们来看下插入代码的实现：

### 插入代码

```cpp
node *insert(node *root, int val) {
    if (root == NULL) { // root为空则创建新结点
        root = new node();
        root->val = val;
        root->left = root->right = NULL;
    }
    else if (val < root->val){ // 插入结点的值小于root，则插入root的左子树上
        root->left = insert(root->left, val); // 递归调用，直到插入到叶子结点上
        if (getHeight(root->left) - getHeight(root->right) == 2) // 插入完成后，判断树是否失衡
            // 插入值小于root结点左孩子的值，只需要右旋，否则先左旋后右旋
            root = val < root->left->val ? rotateRight(root):rotateLeftRight(root);
    }
    else { // 插入结点的值大于等于root，则插入root的右子树上
        root->right = insert(root->right, val);
        if (getHeight(root->left) - getHeight(root->right) == -2) 
            // 插入值大于root结点右孩子的值，只需要左旋，否则先右旋后左旋
            root = val > root->right->val ? rotateLeft(root):rotateRightLeft(root);
    }
    return root;
}
```

这里的核心代码是判断什么时候进行何种旋转的代码，总结：

* 插入到左子树
  * 插入值小于最小子树root结点的左孩子的值，只需要右旋
  * 插入值大于最小子树root结点的左孩子的值，先左旋有右旋
* 插入到右子树
  * 插入值大于最小子树root结点的左孩子的值，只需要左旋
  * 插入值小于最小子树root结点的左孩子的值，先右旋后左旋

可以看到，如果插入是左子树，那么最终一定是要右旋；插入是右子树，一定最后是左旋。这就很好记了。

这里提到了最小子树，那么是什么意思呢，我们上图的图示中只画了三个结点的树，实际情况中，树的规模肯定不止三个结点，那么最小子树就是要找到插入结点后，导致不平衡的那三个结点构成的最小子树。

总结简记：

插左树，大于左，则右旋，小于左，先左后右；

插右树，小于右，则左旋，大于右，先右后左；

以上，我们则可以完美地拿下AVL树了，如果还不是很明白，那就多找几篇文章来看下吧，多花点时间琢磨琢磨，一定可以把AVL树学明白的！

绘图文件，请参考[这里](https://github.com/linlih/CS-Notes/blob/master/AVL.drawio)。使用的是[draw.io](http://draw.io)平台，可以直接导入该文件。

## Reference

参考代码来源：<https://github.com/liuchuo/PAT/blob/master/AdvancedLevel_C%2B%2B/1066.%20Root%20of%20AVL%20Tree%20(25).cpp>


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://linlh.gitbook.io/cs-notes/yu-yan-suan-fa-xiang-guan/ping-heng-er-cha-shu-avl.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.