平衡二叉树旋转机制

概念

        平衡二叉树的旋转机制是一种通过对树进行旋转操作来保持其平衡的方法。

分类

 平衡二叉树的旋转机制包括两种基本类型的旋转：左旋和右旋，以及它们的组合。

左旋

        左旋是将一个节点的右子节点旋转到它的位置上，同时将该节点移到其左侧，并重新连接其子节点。

 简单左旋步骤

• 确定支点：从添加的节点开始，不断地往父节点找不平衡地节点
• 以不平衡的点作为支点
• 把支点左旋降级，变成左子节点
• 晋升原来的右子节点

复杂左旋步骤

• 确定支点：从添加的节点开始，不断地往父节点找不平衡地节点
• 以不平衡的点作为支点
• 将根节点的右侧往左拉
• 原来的右子节点变为新的根节点，并把多余的左子节点拿出来，给已降级的根节点当右子节点

右旋 

        右旋是将一个节点的左子节点旋转到它的位置上，同时将该节点移到其右侧，并重新连接其子节点。

 简单右旋步骤

• 确定支点：从添加的节点开始，不断地往父节点找不平衡地节点
• 以不平衡的点作为支点
• 把支点右旋降级，变成右子节点
• 晋升原来的左子节点

 复杂右旋步骤

• 确定支点：从添加的节点开始，不断地往父节点找不平衡地节点
• 以不平衡的点作为支点
• 将根节点的左侧往右拉
• 原来的左子节点变为新的根节点，并把多余的右子节点拿出来，给已降级的根节点当左子节点

 平衡二叉树需要旋转的情况

• 左左：根节点的左子树的左子树有节点插入，导致二叉树不平衡【一次旋转】
• 左右：根节点的左子树的右子树有节点插入，导致二叉树不平衡【先局部左旋，在整体右旋】
• 右右：根节点的右子树的右子树有节点插入，导致二叉树不平衡【一次旋转】
• 右左：根节点的右子树的左子树有节点插入，导致二叉树不平衡【先局部右旋，在整体左旋】