AVL树

[YBFACC]

AVL树

能够保持平衡的BST

分析

旋转

根据左右子树的高度差（大于2），来解决旋转的类型。

旋转类似链表的操作（断链插入）

删除

将目标元素的值与比目标元素大一位的元素进行替换=>更新目标:删除目标元素大一位的元素

图

大小顺序： a < b < c < d < f < g

矩形的高度代表了树的高度

红色=>蓝色：代表了节点的变化

LL

转化前：

转化后：

RR

转化前：

转化后：

LR

转化1前：

转化1后：

转化2前：

转化2后：

RL

转化1前：

转化1后：

转化2前：

转化2后：

代码实现

参考修改代码：

class AVLNode {
  constructor(val) {
    this.val = val
    this.left = null
    this.right = null
    this.height = 1
  }
  getKey() {}
}
const BLANCE_STATE = {
  UNBALANCE_LEFT: 2,
  UNBALANCE_RIGHT: -2,
  SLIGHT_UNBALANCE_LEFT: 1,
  SLIGHT_UNBALANCE_RIGHT: -1,
  BALANCE: 0
}
class AVLTree {
  constructor() {
    this.root = null
  }
  //RR
  _leftRotate(node) {
    const res = node.right
    ;[res.left, node.right] = [node, res.left]
    this._updateHeigh(node)
    return res
  }
  //LL
  _rightRotate(node) {
    const res = node.left
    ;[res.right, node.left] = [node, res.right]
    this._updateHeigh(node)
    return res
  }

  //LR
  _leftRightRotate(node) {
    node.left = this._updateHeigh(this._leftRotate(node.left))
    return this._rightRotate(node)
  }
  //RL
  _rightLeftRotate(node) {
    node.right = this._updateHeigh(this._rightRotate(node.right))
    return this._leftRotate(node)
  }
  _getHeight(node) {
    return node !== null ? node.height : 0
  }
  _updateHeigh(node) {
    node.height =
      Math.max(this._getHeight(node.left), this._getHeight(node.right)) + 1
    return node
  }
  insert(val) {
    this.root = this._insertNode(this.root, val)
  }
  _insertNode(node, val) {
    if (node === null) return new AVLNode(val)
    if (node.val === val) return node
    if (node.val < val) {
      node.right = this._insertNode(node.right, val)
    } else if (node.val > val) {
      node.left = this._insertNode(node.left, val)
    }
    return this._toBalance(node)
  }
  _toBalance(node) {
    if (node === null) return null
    const BalanceState = this._getBalanceState(node)

    if (BalanceState === BLANCE_STATE.UNBALANCE_LEFT) {
      const leftNodeBalanceState = this._getBalanceState(node.left)
      if (leftNodeBalanceState == BLANCE_STATE.SLIGHT_UNBALANCE_RIGHT) {
        return this._updateHeigh(this._leftRightRotate(node))
      } else {
        return this._updateHeigh(this._rightRotate(node))
      }
    } else if (BalanceState === BLANCE_STATE.UNBALANCE_RIGHT) {
      const rightNodeBalanceState = this._getBalanceState(node.right)
      if (rightNodeBalanceState == BLANCE_STATE.SLIGHT_UNBALANCE_LEFT) {
        return this._updateHeigh(this._rightLeftRotate(node))
      } else {
        return this._updateHeigh(this._leftRotate(node))
      }
    }
    return this._updateHeigh(node)
  }
  _getBalanceState(node) {
    return this._getHeight(node.left) - this._getHeight(node.right)
  }
  remove(val) {
    if (this.search(val) === null) return false
    this.root = this._removeNode(this.root, val)
    return true
  }
  _removeNode(node, val) {
    if (node.val > val) node.left = this._removeNode(node.left, val)
    else if (node.val < val) node.right = this._removeNode(node.right, val)
    else if (node.val == val) {
      if (node.left == null) return node.right
      else if (node.right == null) return node.left
      else {
        let next = this.getNext(val)
        node.val = next.val
        // 转为删除next节点
        node.right = this._removeNode(node.right, node.val)
      }
    }
    return this._doBalance(node)
  }
  search(val) {
    let node = this.root
    while (node) {
      if (node.val === val) return node
      else if (node.val > val) node = node.right
      else node = node.left
    }
    return null
  }
  getNext(val) {
    let res = null,
      node = this.root
    while (node) {
      if (node.val <= val) node = node.right
      else if (node.val > val) {
        res = node
        node = node.left
      }
    }
    return res
  }
}

function arrayToBBST(nums) {
  let avlTree = new AVLTree()
  for (let i = 0; i < nums.length; i++) {
    avlTree.insert(nums[i])
  }
  return avlTree
}

参考

ES6的JavaScript数据结构实现之树（二叉搜索树、AVL树、红黑树）

JS 二分递归 + AVL树