如下图

单旋的弊端详细版.gif

你会发现使用右单旋与左单旋无法让其恢复为二叉平衡树
那是因为 节点6 与 节点7 这两个节点是变化分支。且是唯一的最深分支

左右双旋

当要对某个节点进行右单旋时
如果变化分支是唯一的最深分支，那么我们要对新根进行左单旋
然后再进行右单旋
这样的旋转叫做左右双旋

示例

图示

image.png

左右双旋过程动态图

双旋.gif

最终图示

image.png

右左双旋

当要对某个节点进行左单旋时
如果变化分支是唯一的最深分支，那么我们要对新根进行右单旋
然后再进行左单旋
这样的旋转叫做右左双旋

左右双旋与右左双旋代码

  1. class Node {
  2.     constructor(value) {
  3.         this.value = value;
  4.         this.left = null;
  5.         this.right = null;
  6.     }
  7. }
  9. let node2 = new Node('2');
  10. let node5 = new Node('5');
  11. let node6 = new Node('6');
  12. let node7 = new Node('7');
  13. let node8 = new Node('8');
  15. node8.left = node7;
  16. node7.left = node6;
  17. node6.left = node5;
  18. node5.left = node2;
  20. /**
  21.  * 判断是否为二叉平衡树
  22.  * 平衡二叉的满足条件
  23.  * 根节点的左子树与右子树的高度差不能超过1
  24.  * 这棵二叉树的每个子树的符合第一条
  25.  * @param {*} root 根节点
  26.  * @returns Boolean
  27.  */
  28. function isBalanceTree(root) {
  29.     if (!root) return true;
  30.     // 获取左右子树的深度
  31.     let left = getDeep(root.left);
  32.     let right = getDeep(root.right);
  33.     // 当左子树与右子树的深度差大于1说明不是二叉平衡树
  34.     if (Math.abs(left - right) > 1) return false;
  35.     // 遍历这个二叉树的每一个子树
  36.     else return isBalanceTree(root.left) && isBalanceTree(root.right);
  39. }
  40. /**
  41.  * 获取二叉树的深度
  42.  * @param {*} root 节点
  43.  * @returns Number 返回左右子树中最深的层数
  44.  */
  45. function getDeep(root) {
  46.     if (!root) return 0;
  47.     let left = getDeep(root.left);
  48.     let right = getDeep(root.right);
  49.     return Math.max(left, right) + 1;
  51. }
  52. /**
  53.  * 利用单旋将二叉不平衡树变为二叉平衡树
  54.  * @param {*} root 跟节点
  55.  * @returns 返回平衡之后的根节点
  56.  */
  57. function change(root) {
  58.     if (isBalanceTree(root)) return root; // 返回平衡之后的根节点
  59.     // 走到这说明不是二叉平衡树
  60.     // 判断平不平衡需要从下往上判断
  61.     // 判断对二叉树进行平衡操作要按照后序遍历的顺序
  62.     // 后序遍历 先左子树 后右子树 最后自己
  63.     // 为何进行后序遍历，当根节点不是二叉平衡树，可能对子树进行单旋操作就成为二叉平衡树
  64.     if (root.left != null) root.left = change(root.left); // change函数会返回平衡之后的跟节点，故需要接收返回的的根节点
  65.     if (root.right != null) root.right = change(root.right);// change函数会返回平衡之后的跟节点，故需要接收返回的的根节点
  66.     // 获取深度
  67.     let leftTree = getDeep(root.left);
  68.     let rightTree = getDeep(root.right);
  69.     // 判断那里不符合二叉平衡树的要求
  70.     if (Math.abs(leftTree - rightTree) < 2) return root;
  71.     if (leftTree < rightTree) { //左浅 右深 左单旋
  72.         // 获取变化分支的深度
  73.         let changeTree = getDeep(root.right.left)
  74.         // 获取不变分支的深度
  75.         let noChangeTree = getDeep(root.right.right)
  76.         // 当变化分支的深度大于不变化的分支时需要右左双旋
  77.         if (changeTree > noChangeTree) {
  78.             //将右子树进行右单旋
  79.             root.right = rightRotate(root.right)
  80.         }
  81.         return leftRotate(root)
  82.     } else if (leftTree > rightTree) { //左深 右浅 右单旋
  83.         // 获取变化分支的深度
  84.         let changeTree = getDeep(root.left.right)
  85.         // 获取不变分支的深度
  86.         let noChangeTree = getDeep(root.left.left)
  87.         // 当变化分支的深度大于不变化分支的深度将进行左右单旋
  88.         if (changeTree > noChangeTree) {
  89.             // 将其左子树进行单旋
  90.             root.left = leftRotate(root.left)
  91.         }
  92.         return rightRotate(root)
  93.     }
  94. }
  95. /**
  96.  * 左单旋
  97.  * 旋转节点：不平衡的节点为旋转节点
  98.  * 新根：旋转节点的右子树的根节点
  99.  * @param {*} root 旋转节点
  100.  * @returns 新的根节点
  101.  */
  102. function leftRotate(root) {
  103.     // 找到新根
  104.     let newNode = root.right;
  105.     // 找到变化分支
  106.     let changeNode = newNode.left;
  107.     // 当前旋转节点的右孩子为变化分支
  108.     root.right = changeNode;
  109.     // 新根的左孩子为旋转节点
  110.     newNode.left = root;
  111.     // 返回新的根节点
  112.     console.log('l')
  113.     return newNode;
  115. }
  116. /**
  117.  * 右单旋
  118.  * 旋转节点：不平衡的节点为旋转节点
  119.  * 新根：旋转节点的左子树的根节点
  120.  * @param {*} root 旋转节点
  121.  * @returns 新的根节点
  122.  */
  123. function rightRotate(root) {
  124.     // 找到新根
  125.     let newNode = root.left;
  126.     // 找到变化分支
  127.     let changeNode = newNode.right;
  128.     // 当前旋转节点的左孩子为变化分支
  129.     root.left = changeNode
  130.     // 新根的右孩子为旋转节点
  131.     newNode.right = root;
  132.     // 返回新的根节点
  133.     console.log('r')
  134.     return newNode;
  136. }
  137. // 测试左右双旋
  138. let root = change(node8);
  139. console.log(root)