hangscer

AVL树的单双旋转操作

2017/04/19

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

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

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




最后show the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
}
}