scala 实现 AVL 树

1、具体实现

平衡因子： 某个结点的左子树的高度减去右子树的高度得到的差值。

AVL 树： 所有结点的平衡因子的绝对值都不超过 1 的二叉树。

AVL 树的节点定义：

class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null, _parent: TreeNode = null, _height: Int
  = 1) {
    var value = _value
    var left = _left
    var right = _right
    var parent = _parent
    var height = _height
  }

定义了节点的高度属性后，我们还需要编写函数计算某一个节点的高度，借由树的递归定义，我们很容易写出这一函数

//树的高度
  def treeHight(node: TreeNode): Int = {
    if (node == null) 0
    else scala.math.max(treeHight(node.left), treeHight(node.right)) + 1
  }

有了高度，计算平衡因子的操作就得以很简单的实现：

//平衡因子：某个结点的左子树的高度减去右子树的高度得到的差值。
  def treeGetheight(node: TreeNode): Int = {
    if (node == null) 0
    else treeHight(node.left) - treeHight(node.right)
  }

2、树的平衡化操作

右旋操作:

我们通常的操作是：抛弃右孩子，将之和旋转后的节点 C 相连，成为节点 C 的左孩子

//右旋操作:抛弃右孩子，将之和旋转后的节点 C 相连，成为节点 C 的左孩子
  def treeRotateRight(node: TreeNode): TreeNode = {
    val leftNode = node.left
    node.left = leftNode.right
    leftNode.right = node
    //树的高度
    leftNode.height = scala.math.max(treeHight(leftNode.left), treeHight(leftNode.right)) + 1
    node.height = scala.math.max(treeHight(node.left), treeHight(node.right)) + 1

    leftNode
  }

左旋操作:

左旋操作和右旋操作十分类似，唯一不同的就是需要将左右呼唤下。我们可以认为这两种操作是对称的

 //左旋操作
  def treeRotateLeft(node: TreeNode): TreeNode = {
    val rightNode = node.right
    node.right = rightNode.left
    rightNode.left = node
    //树的高度
    rightNode.height = scala.math.max(treeHight(rightNode.left), treeHight(rightNode.right)) + 1
    node.height = scala.math.max(treeHight(node.left), treeHight(node.right)) + 1

    rightNode
  }

3、需要平衡的四种情况

看链接：https://zhuanlan.zhihu.com/p/34899732

总结为：我们根据破坏树的平衡性（平衡因子的绝对值大于 1）的节点以及其子节点的平衡因子来判断平衡化类型。这样我们即可得出如下表格：左孩子右孩子类型+2+1-LL+2-1-LR-2-+1RL-2--1RR

4、平衡化操作的实现如下：

  // 规律 左孩子右孩子类型+2+1-LL +2-1-LR  -2-+1RL  -2--1RR
  def treeRebalance(node: TreeNode): TreeNode = {
    val factor = treeGetheight(node)
    if (factor > 1 && treeGetheight(node.left) > 0) { //LL
      treeRotateRight(node)
    } else if (factor > 1 && treeGetheight(node.left) <= 0) { //LR
      node.left = treeRotateLeft(node.left)
      treeRotateRight(node)
    } else if (factor < -1 && treeGetheight(node.right) <= 0) { //RR
      treeRotateLeft(node)
    } else if (factor < -1 && treeGetheight(node.right) > 0) { //RL
      node.right = treeRotateRight(node.right)
      treeRotateLeft(node)
    } else node
  }

## 4、AVL 树的插入实现平衡

实现：

```scala
def insertTreeBalannce(node: TreeNode, newNode: TreeNode): Unit = {
    if (node == null) return
    val nodeTmp = node
    if (newNode.value < nodeTmp.value) {
      if (nodeTmp.left == null) {
        nodeTmp.left = newNode
        newNode.parent = nodeTmp
      }
      else insertTreeBalannce(nodeTmp.left, newNode)

    } else if (newNode.value > nodeTmp.value) {
      if (nodeTmp.right == null) {
        nodeTmp.right = newNode
        newNode.parent = nodeTmp
      }
      else insertTreeBalannce(nodeTmp.right, newNode)
    } else return
    nodeTmp.height = treeHight(nodeTmp)

    root = treeRebalance(root)
    println("value =" + node.value + "\theight = " + node.height)

  }

  def insertBalannce(value: Int): Unit = {
    val newNode = new TreeNode(value)
    if (root == null) {
      root = newNode
      newNode.parent = null
    }
    else {
      insertTreeBalannce(root, newNode)
    }

  }