基于bal平衡因子的AVL树InsertNode函数switch分支逻辑详解

1. InsertNode中switch分支逻辑 #

1.1 向左子树插入后的switch（tree->Key > x分支下） #

触发前提：左子树插入成功且左子树高度增加（res=2），需要更新当前节点的平衡状态：

• case 0：当前节点原本平衡，左子树高度+1后变为左重1，bal设为1；当前子树高度整体+1，返回2通知上层节点更新
• case 1：当前节点原本就左重1，左子树再+1触发左失衡，调用LeftBalance做平衡调整；调整后当前子树高度恢复到插入前的高度，返回1通知上层无需更新
• case 2：当前节点原本右重1，左子树+1后左右高度相等，bal设为0；当前子树高度和插入前一致，返回1通知上层无需更新

1.2 向右子树插入后的switch（tree->Key < x分支下） #

触发前提：右子树插入成功且右子树高度增加（res=2），需要更新当前节点的平衡状态：

• case 0：当前节点原本平衡，右子树高度+1后变为右重1，bal设为2；当前子树高度整体+1，返回2通知上层节点更新
• case 1：当前节点原本左重1，右子树+1后左右高度相等，bal设为0；当前子树高度和插入前一致，返回1通知上层无需更新
• case 2：当前节点原本就右重1，右子树再+1触发右失衡，调用RightBalance做平衡调整；调整后当前子树高度恢复到插入前的高度，返回1通知上层无需更新

2. LeftBalance左失衡调整的switch分支逻辑 #

触发前提：节点P的左子树比右子树高2，需要做左失衡调整，根据P的左孩子的平衡状态分两类处理：

• case 1：P的左孩子本身是左重状态，属于LL型失衡（新节点插在P的左孩子的左子树）。直接对P做右旋操作，右旋后P和原左孩子的平衡因子都重置为0即可
• case 2：P的左孩子本身是右重状态，属于LR型失衡（新节点插在P的左孩子的右子树）。需要先对P的左孩子做左旋，再对P做右旋（双旋）。双旋后新的根节点（原P左孩子的右孩子）的平衡因子决定了左右孩子的平衡状态：
  • case 0：新根原本平衡，左右孩子（原P和原P左孩子）插入后都平衡，均设为0
  • case 1：新根原本左重，原左孩子平衡，原P节点右重设为2
  • case 2：新根原本右重，原左孩子左重设为1，原P节点平衡
    最后将新根P的平衡因子设为0

3. RightBalance右失衡调整的switch分支逻辑 #

触发前提：节点P的右子树比左子树高2，需要做右失衡调整，根据P的右孩子的平衡状态分两类处理：

• case 2：P的右孩子本身是右重状态，属于RR型失衡（新节点插在P的右孩子的右子树）。直接对P做左旋操作，左旋后P和原右孩子的平衡因子都重置为0即可
• case 1：P的右孩子本身是左重状态，属于RL型失衡（新节点插在P的右孩子的左子树）。需要先对P的右孩子做右旋，再对P做左旋（双旋）。双旋后新的根节点（原P右孩子的左孩子）的平衡因子决定了左右孩子的平衡状态：
  • case 0：新根原本平衡，左右孩子（原P和原P右孩子）均设为0
  • case 1：新根原本左重，原P节点左重设为1，原右孩子平衡
  • case 2：新根原本右重，原P节点平衡，原右孩子右重设为2
    最后将新根P的平衡因子设为0

内容的提问来源于stack exchange，提问作者pepoo20