如何将一颗不平衡二叉树变成平衡二叉树

这是我参与更文挑战的第18天，活动详情查看：更文挑战

前面我们了解了平衡二叉树，并且用js代码实现将平衡二叉树的判断，那么我们如何将一颗不平衡二叉树变成平衡二叉树呢？
我们就要对二叉树进行一种操作-旋转。也就是两个结点的变换。
二叉树的旋转操作单旋和双旋，我们先来了解一下。

二叉树的单旋（左单旋和右单旋）

左单旋

某一节点不平衡，如果左边浅，右边深，我们就进行左单旋。
旋转节点：不平衡的节点作为旋转节点
新根：旋转之后称为根节点的那个点
变化节支：父级节点发生变化的那个分支
不变分支：父级节点不变的那个分支
左单旋时：
旋转节点：当前不平衡的节点
新根：右子树的根节点
变化节支：旋转节点的右子树的左子树
不变分支：旋转节点的右子树的右子树
某一节点不平衡，如果右边浅，左边深，我们就进行右单旋。
右单旋时：
旋转节点：当前不平衡的节点
新根：左子树的根节点
变化节支：旋转节点的左子树的右子树
不变分支：旋转节点的右子树的左子树

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

左右双旋：当要对某个节点进行右单旋时，如果变化分支是唯一的最深分支，那么我们要对新根进行左单旋，然后再进行右单旋，这样的旋转叫左右双旋 。
右左双旋：当要对某个节点进行左单旋时，如果变化分支是唯一的最深分支，那么我们要对新根进行右单旋，然后再进行左单旋，这样的旋转叫右左双旋。
左左双旋： 如果变化分支的高度比旋转节点的另一侧高度差距超过2，
先进行一次左单旋，当左单旋后将左子树进行左单旋，之后将整个二叉树判断为是否为平衡二叉树。
右右双旋： 如果变化分支的高度比旋转节点的另一侧高度差距超过2，
先进行一次右单旋，当右单旋后将右子树进行右单旋，之后将整个二叉树判断为是否为平衡二叉树。

代码实现将一颗不平衡二叉树变成平衡二叉树

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

function getDeep(root) {//获取最深的层
    if (root == null) return 0;
    var leftDeep = getDeep(root.left);
    var rightDeep = getDeep(root.right);
    return Math.max(leftDeep, rightDeep) + 1;
}

function isBalance(root) {
    if (root == null) return true;
    var leftDeep = getDeep(root.left);//获取左边的深度
    var rightDeep = getDeep(root.right);//获取右边的深度
    if (Math.abs(leftDeep - rightDeep) > 1) {//如果两者相减，绝对值大于1，说明不平衡
        return false;
    } else {
        return isBalance(root.left) && isBalance(root.right);
    }
}

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

function rightRotate(root) {
    // 找到新根
    var newRoot = root.left;
    // 找到变化分支
    var changeTree = root.left.right;
    // 当前旋转节点的左孩子为变化分支
    root.left = changeTree;
    // 新根的右孩子为旋转节点
    newRoot.right = root;
    // 返回新的根节点
    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);
    var leftDeep = getDeep(root.left);
    var rightDeep = getDeep(root.right);
    if (Math.abs(leftDeep - rightDeep) < 2) {
        return root;
    } else if (leftDeep > rightDeep) {//不平衡，左边深，需要右旋
        var changeTreeDeep = getDeep(root.left.right);
        var noChangeTreeDeep = getDeep(root.left.left);
        if (changeTreeDeep > noChangeTreeDeep) {
            root.left = leftRotate(root.left);
        }
        var newRoot = rightRotate(root);
        newRoot.right = change(newRoot.right);
        newRoot = change(newRoot);
        return newRoot;
    } else {//不平衡，右边深，需要左旋
        var changeTreeDeep = getDeep(root.right.left);
        var noChangeTreeDeep = getDeep(root.right.right);
        if (changeTreeDeep > noChangeTreeDeep) {
            root.right = rightRotate(root.right);
        }
        var newRoot = leftRotate(root);
        newRoot.left = change(newRoot.left);
        newRoot = change(newRoot);
        return newRoot;
    }
    return root;
}

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 addNode(root.right, num);//如果右侧不为空，则向右侧进行递归
    } else {//目标值比当前节点小
        if (root.left == null) root.left = new Node(num);
        else addNode(root.left, num);
    }
}

function buildSearchTree(arr) {
    if (arr == null || arr.length == 0) return null;
    var root = new Node(arr[0]);
    for (var i = 1 ; i < arr.length ; i ++) {
        addNode(root, arr[i]);
    }
    return root;
}

var 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);
}
var arr = [];
for (var i = 0 ; i < 10000 ; i ++) {
    arr.push(Math.floor(Math.random() * 10000));
}

var root = buildSearchTree(arr);
console.log(searchByTree(root, 1000));
console.log(num2);

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

复制代码