把必须重新平衡的节点称为å.对于二叉树,å的两棵子树的高度最多相差2,这种不平衡可能有四种情况:

• 对å的左儿子的左子树进行插入节点(左-左)
• 对å的左儿子的右子树进行插入节点(左-右)
• 对å的右儿子的左子树进行插入节点(右-左)
• 对å的左儿子的右子树进行插入节点(右-右)

对于左-左和右-右需要单旋转(single rotation)即可完成调整.对于左-右和右-左则需要双旋转(souble rotation)即可完成调整.

最后show the code:

trait Tree{self=>

  import Tree.compare

  //AVL树 左左插入节点 左左单旋转

  def singleRotateWithLeft:Tree=self match {

    case Node(valueK2,leftK2,rightK2)=> leftK2 match {

      case Node(valueK1,leftK1,rightK1)  =>Node(valueK1,leftK1,Node(valueK2,rightK1,rightK2))

    }

  }

  def singleRotateWithRight:Tree=self match {

    case Node(valueK1,leftK1,rightK1) => rightK1 match {

      case Node(valueK2,leftK2,rightK2) => Node(valueK2,Node(valueK1,leftK1,leftK2),rightK2)

    }

  }

  //左右插入新节点

  def doubleRotateWithLeft:Tree=self match {

    case Node(valueK3,leftK3,rightK3) => Node(valueK3,leftK3.singleRotateWithRight,rightK3).singleRotateWithLeft

  }

  //右左插入数据节点

  def doubleRotateWithRight:Tree=self match {

    case Node(valueK1,leftK1,rightK1) =>Node(valueK1,leftK1,rightK1.singleRotateWithLeft).singleRotateWithRight

  }

}