<!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 =https://www.cnblogs.com/lanshanxiao/p/ 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 = node3;
node3.left = node2;
node2.left = node1;
node3.right = node4;
node4.right = node5;
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 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 = 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 = change(newRoot);//左旋后可能會導致樹不平衡，所以再次平衡
return newRoot;
}
}
//左旋
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>
非平衡樹的雙旋
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/36581.html
標籤：其他