How to turn an unbalanced binary tree into a balanced binary tree

This is the 18th day of my participation in the More text Challenge. For more details, see more text Challenge

Before we understand the balanced binary tree, and the js code to achieve the balanced binary tree judgment, so how do we turn an unbalanced binary tree into a balanced binary tree? We’re going to do an operation on the binary tree – rotation. It’s the transformation of two nodes. Binary tree rotations, single and double rotations, let’s look at that first.

Monospin of binary trees (left and right monospin)

Left single

If a node is out of balance, and the left is shallow and the right is deep, we do a left monospin. Rotation node: the unbalanced node as the rotation node New root: the point after rotation called the root node change saving: the branch where the parent node changes branch: the branch where the parent node does not change Left single rotation: rotation node: the current unbalanced node New root: the root node of the right subtree change saving: The left subtree of the right subtree of the rotating node does not branch: if a node of the right subtree of the rotating node is unbalanced, if the right side is shallow and the left side is deep, we perform a right single rotation. New root: The root node of the left subtree changes. Saving: The right subtree of the left subtree of the rotating node remains unchanged. Branch: the left subtree of the right subtree of the rotating node

Binary tree (left/right, right/left, left/right, right/right)

Left/right double spin: When a node is to be right monospin, if the changing branch is the only deepest branch, then the new root is to be left monospin, and then right monospin, such a rotation is called left/right double spin. Right-left double spin: When a node is to be left monospin, if the changing branch is the only deepest branch, then we are to right monospin the new root, and then left monospin again, such a rotation is called right-left double spin. Left-left double rotation: If the height of the changing branch is more than 2 different from the height of the other side of the rotating node, the left single rotation is performed first. After left single rotation, the left subtree is performed left single rotation, and then the whole binary tree is judged to be a balanced binary tree. Right-right double rotation: If the height of the changing branch is more than 2 different from that of the other side of the rotating node, a right single rotation is performed first. After the right single rotation, a right single rotation is performed on the right subtree, and then the whole binary tree is judged as a balanced binary tree.

Code to achieve an unbalanced binary tree into a balanced binary tree

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

function getDeep(root) {// Get the deepest layer
    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);// Get the left side depth
    var rightDeep = getDeep(root.right);// Get the depth on the right
    if (Math.abs(leftDeep - rightDeep) > 1) {// If the absolute value is greater than 1, there is an imbalance
        return false;
    } else {
        returnisBalance(root.left) && isBalance(root.right); }}function leftRotate(root) {
    // Find the new root
    var newRoot = root.right;
    // Find the change branch
    var changeTree = root.right.left;
    // The right child of the current rotation node is the change branch
    root.right = changeTree;
    // The left child of the new root is the rotation node
    newRoot.left = root;
    // Return the new root node
    return newRoot;
}

function rightRotate(root) {
    // Find the new root
    var newRoot = root.left;
    // Find the change branch
    var changeTree = root.left.right;
    // The left child of the current rotation node is the change branch
    root.left = changeTree;
    // The right child of the new root is the rotation node
    newRoot.right = root;
    // Return the new root node
    return newRoot;
}

function change(root) {// Return the balanced root node
    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) {// Unbalance, deep left, need to turn right
        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 {// Unbalance, deep on the right, need to turn left
        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) {// The target value is larger than the current node
        if (root.right == null) root.right = new Node(num);// If the right is empty, the node is created
        else addNode(root.right, num);// Recurse to the right if the right side is not empty
    } else {// The target value is smaller than the current node
        if (root.left == null) root.left = new Node(num);
        elseaddNode(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));

Copy the code

In this way, we use JS code to achieve an unbalanced binary tree into a balanced binary tree, we can find that the performance of the binary search tree into a balanced binary search tree has been optimized.