二叉树的双旋

二叉树的双旋（左右双旋，右左双旋）

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

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

二叉树进行只进行单旋操作，当唯一的最深分支为变化分支时，仅进行相同的单旋操作，始终无法使二叉树达到平衡。

将黄色框图中的二叉树进行右旋，右旋之后再进行左旋，使二叉树达到平衡

function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

let node2 = new Node("2");
let node5 = new Node("5");
let node6 = new Node("6");
let node7 = new Node("7");
let node8 = new Node("8");

node8.left = node7;
node7.left = node6;
node6.left = node5;
node5.left = node2;

function getDeep(root) {
    if (root == null) {
        return 0;
    }
    let leftDeep = getDeep(root.left);
    let rightDeep = getDeep(root.right);
    return Math.max(leftDeep, rightDeep) + 1;
}

function isBalance(root) {
    if (root == null) {
        return true;
    }
    let leftDeep = getDeep(root.left);
    let rightDeep = getDeep(root.right);
    if (Math.abs(leftDeep - rightDeep) > 1) {
        return false;
    }
    return isBalance(root.left) && isBalance(root.right);
}


function leftRotate(root) {
    // 1. 找到新根
    let newRoot = root.right;
    // 2. 找到变化分支
    let changeTree = root.right.left;
    // 3. 当前旋转节点的右孩子为变化分支
    root.right = changeTree;
    // 4. 新根的左孩子为旋转节点
    newRoot.left = root;
    // 5. 返回新的根节点
    return newRoot;
}

function rightRotate(root) {
    // 1. 找到新根
    let newRoot = root.left;
    // 2. 找到变化分支
    let changeTree = root.left.right;
    // 3. 当前旋转节点的左孩子为变化分支
    root.left = changeTree;
    // 4. 新根的右孩子为旋转节点
    newRoot.right = root;
    // 5. 返回新的根节点
    return newRoot;
}

function change(root) {  //   返回平衡之后的根节点
    if (isBalance(root)) {
        return root;
    }
    if (root.left != null) {
        root.left = change(root.left);
    }
    if (root.right != null) {
        root.right = change(root.right);
    }

    let leftDeep = getDeep(root.left);
    let rightDeep = getDeep(root.right);
    if (Math.abs(leftDeep - rightDeep) < 2) {
        return root;
    } else if (leftDeep > rightDeep) { // 不平衡，左边深，需要右旋
        let changeTreeDeep = getDeep(root.left.right);
        let noChangeTreeDeep = getDeep(root.left.left);
        if(changeTreeDeep > noChangeTreeDeep){
            root.left = leftRotate(root.left);
        }
        return rightRotate(root);
    } else {  // 不平衡，右边深，需要左旋
        let changeTreeDeep = getDeep(root.right.left);
        let noChangeTreeDeep = getDeep(root.right.right);
        if(changeTreeDeep > noChangeTreeDeep){
            root.right = rightRotate(root.right);
        }
        return leftRotate(root);
    }
}

console.log(node8);

console.log(isBalance(node8));

let newRoot = change(node8);

console.log(isBalance(newRoot));

console.log(newRoot);