平衡二叉树问题

发布网友发布时间：2022-05-07 01:23

共1个回答

热心网友时间：2023-10-10 18:27

平衡因子一般是左子树的高度减去右子树的高度，因此从图上看，应刚插入的是31
从这个结点向根回溯，直到找到一个平衡因子的绝对值大于1的就停止（如果到根都没有就不用旋转）
然后向来路回退，根据来路连续三个结点的形状决定旋转的类型
你的图上32是+1、35是+1，30是-2，注意30、35、32这三个结点的路线是先右后左，因此旋转类型为先左后右双旋转
具体步骤如下：首先32和35向右旋转，35成为32的右子树，32的右子树给35
然后30和32向左旋转，30成为32的左子树，32的左子树成为30的右子树追问实际找平衡因子的时候还是不明白，这个题为什么32和35都是+1 30就是-2了呢

追答子树的深度（也就是高度，也就是有几层）：30左子树高度1，右子树高度3，1-3=-2
32：1-0=+1
35：2-1=+1

来自：求助得到的回答