目录前言一、为什么需要平衡二、两种旋转规则规则1.左旋规则2右旋三、需要旋转的四种场景1、LL型失衡右旋 (Right Rotation)2、LR型失衡先左旋再右旋 (Left-Right Rotation)3、RR型失衡左旋 (Left Rotation)4、RL型失衡先右旋再左旋 (Right-Left Rotation)前言在 Java 的集合框架中TreeSet和TreeMap拥有自动排序的能力这一切的根基都建立在一种数据结构之上——平衡二叉树AVL树。今天来介绍一下408最爱的平衡二叉树的四种旋转机制。一、为什么需要平衡在了解旋转之前我们先看看普通的二叉查找树BST有什么致命缺陷。二叉查找树的规则很简单左子节点 父节点 右子节点。 这看起来很完美每次查找都能排除一半的数据。但如果你按顺序插入一组数据它会一直往右边长彻底退化成一条单向链表为了防止这种的情况AVL树平衡二叉树诞生了。它给自己定下了一条规则任何节点的左子树和右子树的高度差绝对不能超过 1。一旦超过 1它就会触发修复机制——旋转。二、两种旋转规则旋转机制以及触发规则规则1左旋规则2右旋触发规则当添加一个节点后该二叉树不再是一个平衡二叉树。规则1.左旋普通场景当12这个节点加入这个平衡二叉树后破坏了二叉树的平衡状态确定支点从添加的节点开始往父节点找找到的第一个不平衡的节点即为支点。在本例中节点10为支点以10为支点向左旋转步骤1以不平衡的点作为支点。2把支点左旋降级变成左子节点。3晋升原来的右子节点。特殊场景步骤1以不平衡的点作为支点。2将根节点的右侧往左拉。3原先的右子节点变成新的父节点并把多出来的左子节点给已经降级的根节点当右子节点。规则2右旋步骤1以不平衡的点作为支点。2把支点右旋降级变成右子节点。3晋升原来的左子节点。三、需要旋转的四种场景1、LL型失衡右旋 (Right Rotation)场景在节点 A 的左孩子的左子树上插入了新节点导致 A 的左边太重了。一次右旋2、LR型失衡先左旋再右旋 (Left-Right Rotation)场景在节点 A 的左孩子的右子树上插入了新节点破坏了二叉树的平衡状态。3、RR型失衡左旋 (Left Rotation)场景在节点 A 的右孩子的右子树上插入了新节点导致 A 的右边太重了。4、RL型失衡先右旋再左旋 (Right-Left Rotation)场景在节点 A 的右孩子的左子树上插入了新节点。