【前端】自学基础算法 -- 17.不平横二叉树的左、右单旋

不平横二叉树的左、右单旋

简介

主要用于调整二叉搜索树的平衡，保持二叉搜索树的性质，使得树的高度相对平衡，从而提高搜索、插入和删除等操作的效率。

左单旋

右单旋

实现方法

class Node {
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
}

let a = new Node('a')
let b = new Node('b')
let c = new Node('c')
let d = new Node('d')
let e = new Node('e')
let f = new Node('f')
let g = new Node('g')
let h = new Node('h')
let i = new Node('i')

a.left = b
a.right = c
b.left = d
b.right = e
c.left = f
c.right = g
d.left = h
// e.right = i // true
h.left = i // false

// 获取二叉树的深度
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 isBalanced(root) {
  if (root === null) return true
  let leftDeep = getDeep(root.left)
  let rightDeep = getDeep(root.right)
  // 如果左右子树的高度差大于1，则不是平衡二叉树
  if (Math.abs(leftDeep - rightDeep) > 1) return false
  // 如果左右子树的高度差小于等于1，则继续判断左右子树是否是平衡二叉树
  return isBalanced(root.left) && isBalanced(root.right)
}

console.log(isBalanced(a))

/**
 * 辅助函数 - 左旋
 * @param {*} root
 * @returns
 */
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
}

/**
 * 辅助函数 - 右旋
 * @param {*} root
 * @returns
 */
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 (root == null) return root
  if (isBalanced(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)
  }
}

let newRoot = change(a)
console.log(isBalanced(newRoot))