chapter_tree/avl_tree/

[giscus[bot]]

chapter_tree/avl_tree/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_tree/avl_tree/

[hello-ikun]

这部分确实是有点难度

[krahets]

很是同意，所以本章标了选读符号 doge

[hello-ikun]

k宝 你说的并查集什么时候更新呢

[krahets]

并查集近期不会更新 T T

[zrcoder]

@xia-Sang 之前写过一篇并查集，虚构程序员写武侠游戏的故事来说： https://rdcode.netlify.app/docs/graph/union-find/index.html

[hello-ikun]

感谢你的回复！

[symbolworld]

K神有时间可以更新一章红黑树的区别吗？想看看它们的区别和各自的应用场景，感谢！

[krahets]

红黑树暂时不在内容大纲里，抱歉哇！近期应该不会更新

[Mahaotian1]

您好，请问python的会更新吗

[krahets]

已更新～

[anzhen3531]

K神会更新图数据结构嘛 ？

[krahets]

必须的！

[GarveyH]

大佬，请问这一节中哪些函数归在private，哪些函数归在public中，这方面有什么考量吗？比如为什么要将 height 函数和 updateHeight 函数 分别放在 public 和 private 中呢？

[krahets]

Hi! 主要看方法的使用范围，如果方法只在类内部使用（一般也不希望用户调用），那么就设计为 private ，比如用户单独调用 updateHeight() 是没有意义的，它只是插入、删除操作中的一步。而 height() 是访问结点高度，类似于 vector.size() ，可以设置成 public 以便使用。

[TujinLee]

有个疑问，我看右旋操作是处理失衡节点node、child、grandchild之间的关系，那node的父级和node原来的连接不需要维护吗？右旋操作后岂不是断掉了？

[krahets]

@jiangyuxustore Bingo! 或者可以把“该节点的左子树中的最大节点”替换到删除节点上，本质上是不希望破坏二叉搜索树“左<根<右”的性质。

[plwater]

removeHelper(TreeNode node, int val) 方法（Java代码）的注释我觉得写得不是很规范，导致这部分代码有点晦涩难懂（也有可能是我太菜了ww），需要花很多时间和翻看评论区的讨论才能逐渐消化，如果把算法的方法注释（特别是方法入口处的注释）写得规范一点，我想对于帮助读者自行消化可能会起到很大的帮助，也会让这个项目价值更高。
特别感谢K老师和其他人的开源贡献，最近复习算法，收获特别大。
下面是根据我的理解补充的注释，可能不准确，仅为参考。

 /**
     * 递归删除节点（辅助方法）
     * @param node 二叉树的根节点（也可能是二叉树子树的根节点）
     * @param val 要删除的节点的值
     * @return 删除对应节点后的子树的根节点
     */
    private TreeNode removeHelper(TreeNode node, int val) {
    }

[krahets]

@plwater Hi，谢谢建议！建议前往代码仓库下载完整代码并运行，在调试过程中理解复杂代码。本书为了提升篇幅的紧凑性，部分放弃了代码注释的规范性

[plwater]

感谢建议，我会尝试在本地调试，理解你的用意了。

[xlyyddy]

       # 先左旋后右旋
        node.left = self.left_rotate(node.left)
        return self.right_rotate(node)

那这个是不是应该在左旋函数返回之后进行子树的根节点和其父节点的连接啊

[CAgent05]

k神，这部分还会介绍红黑树吗？

[krahets]

正在考虑～！

[fallenleavesguy]

一定要介绍啊，我的大佬，嘿嘿

[limuzi9806]

加一

[Hutu-666]

大佬，想问一下，updateHeight()方法里为啥要 + 1 操作？

[krahets]

Hi，这个公式的含义是 高度 = max(左子树高度, 右子树高度) + 1 。其中，左子树高度和右子树高度是不包含该节点的高度的，因此要加 1 。

[UFO583]

/* 右旋操作 */
TreeNode *rightRotate(TreeNode *node) {
TreeNode *child = node->left;
TreeNode *grandChild = child->right;
// 以 child 为原点，将 node 向右旋转
child->right = node;
node->left = grandChild;
// 更新节点高度
updateHeight(node);
updateHeight(child);
// 返回旋转后子树的根节点
return child;
}
K神为什么这里没有更新 grandChild 的高度呢

[krahets]

Hi ，这是因为执行右旋（或左旋）后，节点 grandChild 的高度不会改变，可以观察文中配图来验证一下

[bethewind]

讲的不错,经过你的讲解感觉AVL树只有红黑树10%的难度

[hello-ikun]

复刻了一下 感觉可以的

[riiyn]

大佬，先左旋再右旋那张图，child.left=node, node.left=null也可以达到平衡吧，只是破坏了二叉搜索树的规则，这种做法属于左旋吗？左旋的时候child既可以取node左子节点也可以取右子节点吧，右旋同理

[krahets]

是的，这样会破坏二叉搜索树的性质，所以不能称为旋转操作了。旋转操作的意义就是在保持二叉搜索树性质的基础上，恢复二叉树的平衡性。两者缺一不可

[riiyn]

@krahets 明白了，谢谢大佬，还有个疑问，rotate那个方法，node的平衡因子判断应该是>0和<0吧，要不然不是忽略了1和-1的情况

[krahets]

@riiyn 客气啦，平衡因子判断是 $&gt; 1$ 和 $&lt; -1$ ，因为子树在这种情况下才是失衡的，${-1, 0, 1}$ 这三种情况是平衡状态，无需旋转。

[bukexiusi]

if t.balanceFactor(node.Left) >= 0 {
// 右旋
return t.rightRotate(node)
} else {
// 先左旋后右旋
node.Left = t.leftRotate(node.Left)
return t.rightRotate(node)
}

为什么判断条件是 >= 0，是不是 > 0 也可以，因为左右高度差不可能为 0

[krahets]

Hi，node.left 的左右高度差可能为 0 哈。例如在文中的 grandChild 底下再添加一个子节点。

[Liuhyi]

=0的时候可以直接右旋，也可以先左旋在右旋

[wanlufun]

为什么不用 updateHeight(grandChild) 呀？

[wanlufun]

我懂了 我懂了 基础知识忘记啦

分析原因

节点的高度，只与这个节点的子节点高度有关，由于没有修改grandchild 的子节点， 所以不需要updateHeight(grandChild)

[jincet]

这里讲的真好，清楚易懂

[clxisclx]

感觉挺清楚的，期待加入红黑树

[KLYkl]

我个人对平衡二叉树旋转的理解：
（1）如果失衡的节点的树是一颗左偏树，得看他左子树：
①如果左子树是一颗左偏树或者平衡树，那么使用对失衡节点右旋的方法。
②如果左子树是一颗右偏树，那么对左子节点进行左旋，然后对失衡节点进行右旋。（我的理解是，先把这颗左子树是偏右的树左旋转变成左子树是偏左的树或者平衡的树，然后就可以使用①的方式来对失衡节点旋转，即右旋。）
（2）同理，如果失衡的节点的树是一颗右偏树，得看他右子树：
①如果右子树是一颗右偏树或者平衡树，那么使用对失衡节点左旋的方法。
②如果右子树是一颗左偏树，那么对右子节点进行右旋，然后对失衡节点进行左旋。（我的理解是，先把这颗右子树是偏左的树右旋转变成右子树是偏右的树或者平衡的树，然后就可以使用①的方式来对失衡节点旋转，即左旋。）
这个是我根据（表 7-3 四种旋转情况的选择条件）的个人理解，如果我的理解有问题，请大佬慷慨指出，认真向您学习，谢谢。

[chumingqian]

使失衡节点重新恢复平衡， 应该是使得 不平衡节点 恢复平衡？

[watermenlon-lon-lon]

有个问题，自己运行的时候。。会报错，然后删了如TreeNode | None 这些注释，就可以了
这个注释为啥会影响运行
def get_root(self) -> TreeNode | None:
TypeError: unsupported operand type(s) for |: 'type' and 'NoneType'

[krahets]

Hi，这个是 Python 近期引入的 type hints 语法，需要在 Python >= 3.10 的环境下运行

[GoGoGo13579]

在“图 7-27 有 grand_child 的右旋操作”示意图中,节点5应该不是不平衡节点吧，它的平衡因子应该是1吧

[GoGoGo13579]

不好意思,搞混了,我计算平衡因子时用“左子节点平衡因子” - “右子节点平衡因子”了

[Linjiangxian0203]

def update_height(self, node: TreeNode | None):
"""更新节点高度"""
# 节点高度等于最高子树高度 + 1
node.height = max([self.height(node.left), self.height(node.right)]) + 1
求大佬解答为什么这里节点高度等于最高子树高度加一，这里是把左右子树单独拎出来了吗

[ArvineKwok]

为了寻找根节点能到达最远的叶子节点呀，左右都往下找逐步递归

[Linjiangxian0203]

后面我理解了，加一我觉得可以理解为左右子树的高度加上左右子树的与根节点还需要加一，这样子理解应该没有问题吧

[EIG93]

"我们需要从这个节点开始，自底向上执行旋转操作，使所有失衡节点恢复平衡",在插入和删除的时候，这句话没有看懂，rotate(TreeNode node) 里面是往下去检查子节点的平衡因子？

[lynnlee0522]

这段话说的应该有问题, 不需要递归检查
事实上, 插入节点后如果导致多个祖先节点失衡, 只需调整距离插入节点最近的失衡节点, 其他失衡节点会自然平衡

[lynnlee0522]

前提是在 AVL 树上做插入

[ourssssss]

       // 子节点数量 = 0 ，直接删除 node 并返回
        if (child == null)
            return null;
        // 子节点数量 = 1 ，直接删除 node
        else
            node = child

这段可以修改为return child吗,因为我觉得只有一个子节点时不需要再更新子节点的高度和平衡了

[gopherHsu]

赞同

[gopherHsu]

求教各位，图 7-26 中节点“4” 和节点“3”都是失衡节点都是2，都是为什么执行节点“3”的右旋而不是节点“4”的右旋呢？

[gopherHsu]

看了后面insert的代码，递归实现；总是先旋转失衡的子节点，所以是先执行节点“3”的右旋，节点“3”右旋之后，节点“4”就不是失衡节点了。

[zhuiguang49]

是的，操作的是从底至顶看的第一个失衡节点

[gopherHsu]

删除节点的代码：

/* 递归删除节点（辅助方法） */
TreeNode removeHelper(TreeNode node, int val) {
    if (node == null)
        return null;
    /* 1. 查找节点并删除 */
    if (val < node.val)
        node.left = removeHelper(node.left, val);
    else if (val > node.val)
        node.right = removeHelper(node.right, val);
    else {
        if (node.left == null || node.right == null) {
            TreeNode child = node.left != null ? node.left : node.right;
            // 子节点数量 = 0 ，直接删除 node 并返回
            if (child == null)
                return null;
            // 子节点数量 = 1 ，直接删除 node
            else
                node = child;
        } else {
            // 子节点数量 = 2 ，则将中序遍历的下个节点删除，并用该节点替换当前节点
            TreeNode temp = node.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            node.right = removeHelper(node.right, temp.val);
            node.val = temp.val;
        }
    }
    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}

子节点数为0或1的时候，应该都可以直接返回吧，不需要执行后序的旋转操作。

 if(node.left == null) {
    return node.right;
}
if(node.right == null) {
    return node.left;
}

[easyhumor]

我也觉得子节点数量为1的时候，可以直接返回，而且这个子节点应该是叶子节点

[ferryboy001]

大家好，我是之前提问过有关二叉树概念的盲人。

稍微叠个甲，当然如果有其他盲人小伙伴看到，不要介意我总是提起这点，实在是因为如果不说，其他小伙伴就不太好针对我的提问进行有效的回答。

之前学习数据结构，到树开始，就有点一知半解了，我其实很不喜欢这种感觉。我很希望能搞懂它。

不得不说，很多时候，图解真的可以让我们少走许多弯路。例如我之前理解树的前序遍历、中序遍历、后序遍历，我读到类似“先便利左子树，然后便利根节点，最后便利右子树”，或者“先便利根节点，然后便利左子树，然后是右子树”时，脑子里总是很混乱。

昨天突然在看使用递归方式进行前中后序遍历的代码时发现，使用递归和自相似性的思想理解二叉树便利会更好。
例如，单纯看便利顺序，我会觉得，这似乎不会从微小的顺序上对树的便利顺序产生影响，但细想发现，每种便利顺序都是在根本上改变了树的便利方式。
例如，要进行后序遍历，就需要从不停寻找左子树，直到找到叶子结点开始，然后在这个最小的结构上访问它的右叶子节点，然后是它的父节点……
因为访问的路径在整体上可能会很复杂，但我从一个小的结构上理解它之后，我就可以认为自己有了“见微知著”的能力。

好了，废话完毕，今天的问题是有关如何理解树的旋转的。主要是想让大家看看我的理解是否正确。

我根据表 7-3 脑补了如下失衡二叉树，由于我不太好用纯文本画二叉树，用语言描述可能啰嗦，我就写成数组形式：

[1,none,2,none,none,none,3]

其实，这就是一个退化的链表。此时，根节点的平衡因子是 $-2$，根据定义，左子树为空节点，高度为 $-1$，右子树的高度为 $1$，得到平衡因子为 $-2$。
根据表格，此时应该使用左旋操作。

根据代码，有：

/* 左旋操作 */
TreeNode *leftRotate(TreeNode *node) {    // 本例中为根节点 1
    TreeNode *child = node->right;    // 本例中为节点 2
    TreeNode *grandChild = child->left;    // nullptr
    // 以 child 为原点，将 node 向左旋转
    child->left = node;  // 1
    // 此时，child 已经成为一个结构为 [2,1,3] 的二叉树
    // 且此时 node->right->left <=> child->left <=> node
    node->right = grandChild;  // nullptr
    // 更新节点高度
    updateHeight(node);    // 2 -> 0
    updateHeight(child);    // 1 -> 1
    // 返回旋转后子树的根节点
    return child;
}

不知道理解有没有问题，但还是感觉有点没明白。

[hwmfyry]

关于左旋的代码应该是没有问题的。

关于遍历的问题，三种遍历其实在访问节点的顺序上是一样的，只是在记录节点的值时机有区别。每个节点遍历，都是从该节点先开始，然后遍历左子树，然后回到此节点，然后遍历右子树，然后回到此节点， 随后返回上级节点（如果为根节点则结束遍历）。

前序遍历是在一开始便记录该节点的值，因此该节点的值，位于左右子树的所有值之前。中序遍历是在遍历完左子树之后，记录该节点值，所以左子树的所有值位于该节点的值之前，右子树的所有值位于之后。后序遍历是遍历完左右子树之后，再记录该节点值，所以位于左右子树的所有值之后。

[yuechao4039]

图 7-26 右旋操作步骤

执行完方法，TreeNode rightRotate(TreeNode node) 后，根节点是哪个？还能宽度优先遍历么？

[yuechao4039]

忽略。

[xienumfirst]

C语言代码中AVLTree的结构体定义有吗

[CNiq527]

文章已经写的很清晰了，但是没有动图， 看了这篇文章更好理解 🫡

[CNiq527]

另外树旋转的图中，节点底下的数字描述的是平衡因子，对于新手可能不能第一时间反应过来

[0101qwe]

我想知道这个应该学到什么程度才算掌握啊，是不是要能凭借自己可以全敲出来才算掌握，然后在去学下一个结构啊