14.非平衡树的双旋(左右双旋和右左双旋)代码实现(JavaScript版) 算法 第1张
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        //非平衡二叉树的双旋(左右双旋,右左双旋)
        //当要对某个节点进行左单旋时,若变化分支是唯一的最深分支,那么要对新根进行右单旋,然后在进行左单旋,这样的旋转叫做右左双旋
        //当要对某个节点进行右单旋时,若变化分支是唯一的最深分支,那么要对新根进行左单旋,然后在进行右单旋,这样的旋转叫做左右双旋
        function Node(value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }

        var node1 = new Node(1);
        var node2 = new Node(2);
        var node3 = new Node(3);
        var node4 = new Node(4);
        var node5 = new Node(5);
        var node6 = new Node(6);
        
        node6.left = node5;
        node5.left = node4;
        node4.left = node3;
        node3.left = node2;
        node2.left = node1;

        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 getDeep(root){
            if(root == null) return 0;
            var leftDeep = getDeep(root.left);//获取左子树深度
            var rightDeep = getDeep(root.right);//获取右子树深度
            return Math.max(leftDeep, rightDeep) + 1;//左右子树深度最大的值 + 1;
        }

        //非平衡树要旋转,变成平衡树
        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 true;
            }else if(leftDeep > rightDeep){//左深右浅,要右旋
                var changeTreeDeep = getDeep(root.left.right);//变化分支的深度
                var noChangeTreeDeep = getDeep(root.left.left);//不变化分支的深度
                if(changeTreeDeep > noChangeTreeDeep    ){//变化分支深度 大于 不变化分支深度,要将左子树先进行左旋
                    root.left = leftRotate(root.left);
                }
                return rightRotate(root);
            }else{//左浅右深,要左旋
                var changeTreeDeep = getDeep(root.right.left);//变化分支的深度
                var noChangeTreeDeep = getDeep(root.right.right);//不变化分支的深度
                if(changeTreeDeep > noChangeTreeDeep){//变化分支深度 大于 不变化分支深度,要将右子树先进行右旋
                    root.right = rightRotate(root.right);
                }
                return leftRotate(root);
            }
        }

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

        //右旋
        function rightRotate(root){
            //找到新根
            var newRoot = root.left;
            //找到变化的分支
            var changeTree = root.left.right;
            //将当前节点赋值到新根的右节点
            newRoot.right = root;
            //将变化分支赋值到当前节点的左节点
            root.left = changeTree;
            
            return newRoot;//返回新根
        }

        console.log(isBalance(node6));
        var newRoot = change(node6);
        console.log(isBalance(newRoot));
        console.log(newRoot);
    </script>
</body>
</html>
非平衡树的双旋

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。