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

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



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);
        }
        let newRoot = rightRotate(root);
        newRoot.right = change(newRoot.right);
        newRoot = change(newRoot);
        return newRoot;
    } else {  // 不平衡，右边深，需要左旋
        let changeTreeDeep = getDeep(root.right.left);
        let noChangeTreeDeep = getDeep(root.right.right);
        if(changeTreeDeep > noChangeTreeDeep){
            root.right = rightRotate(root.right);
        }
        let newRoot = leftRotate(root);
        newRoot.left = change(newRoot.left);
        newRoot = change(newRoot);
        return newRoot;
    }
}




// 新增一个节点
function addNode(root, num) {
    if (root == null) {
        return;
    }
    if (root.value == num) {
        return;
    }
    if (root.value < num) {   // 目标值比当前节点大
        if (root.right == null) { // 当前节点右侧为空，则创建右侧节点
            root.right = new Node(num);
        } else {  // 如果右侧不为空，则右侧进行递归
            return addNode(root.right, num);
        }
    } else {
        if (root.left == null) {
            root.left = new Node(num);
        } else {
            return addNode(root.left, num);
        }
    }
    return root;
}

// 二叉树的搜索
let num2 = 0;
function searchByTree(root, target) {
    if (root == null) {
        return false;
    }
    num2 += 1;
    if (root.value == target) {
        return true;
    }
    if (root.value > target) {
        return searchByTree(root.left, target)
    } else {
        return searchByTree(root.right, target);
    }
}

//构建二叉树
function buildSearchTree(arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    let root = new Node(arr[0]);
    for (let i = 1; i < arr.length; i++) {
        addNode(root, arr[i]);
    }
    return root;
}

let arr = [];
for (let i = 0; i < 10000; i++) {
    arr.push(Math.floor(Math.random() * 10000));
}


let root = buildSearchTree(arr);
console.log(getDeep(root), isBalance(root), searchByTree(root, 1000));
console.log(num2);


num2 = 0;
let newRoot = change(root);
console.log(getDeep(newRoot), isBalance(newRoot), searchByTree(newRoot, 1000));
console.log(num2);