算法

二叉树的单旋

updated on

二叉树的单旋操作（左单旋、右单旋）

进行左单旋：

  1. 找到新根
  2. 找到变化分支
  3. 当前旋转节点的右孩子为变化分支
  4. 新根的左孩子为旋转节点
  5. 返回新的根节点

左单旋时：
1. 旋转节点：当前不平衡的节点
2. 新根： 右子树的根节点
3. 变化分支：旋转节点右子树的左子树
4. 不变分支：旋转节点右子树的右子树

进行右单旋

  1. 找到新根
  2. 找到变化分支
  3. 当前旋转节点的左孩子为变化分支
  4. 新根的右孩子为旋转节点
  5. 返回新的根节点

右单旋时：
1. 旋转节点： 当前不平衡的节点
2. 新根： 左子树的根节点
3. 变化分支： 旋转节点左子树的右子树
4. 不变分支： 旋转节点右子树的左子树


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

let node2 = new Node("2");
let node3 = new Node("3");
let node5 = new Node("5");
let node6 = new Node("6");

node2.right = node5;
node5.left = node3;
node5.right = node6;


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) { // 不平衡，左边深，需要右旋
        return rightRotate(root);
    } else {  // 不平衡，右边深，需要左旋
        return leftRotate(root);
    }
}

console.log(node2);
console.log(isBalance(node2));

let newRoot = change(node2);

console.log(isBalance(newRoot));
console.log(newRoot);

其他内容